紧急！！！数据结构二叉树问题 C/C++高手请进

Question

题目：自己建立一个二叉树，树的节点表示一分子含氮碱基：A/G/C/T,对于某一节点碱基用随机数生成。输出二叉树的结构；输出二叉树的先序， 非递归 遍历序列，即为一条DNA单链；交换所有结点的左右子树，并用中序非递归的方式输出遍历序列，也是一条DNA单链；比较两条单链的相似度，结果用百分数表示。
二叉树的结构：
a
/ \
s d
/ \ / \
f g h j
/ \ / \
z x n m
(asdfg……应为相应的随机生成的碱基)
我写了一个程序，但是写的很乱，而且运行起来结果还差很多。所以希望高手帮我改一下代码，或重新给出一个程序的代码。
积分不多，只能给20分，虽然少点，但我实在没有更多的积分了。
注意是用非递归先序和后序遍历，请用C/C++。要输出二叉树的结构。

以下是我的运行不对的烂程序：

main.cpp:

#include <iostream>

using namespace std;

#include "Binarytree.h"
#include "compare.h"

int main()
{
BinTreeNode *root;
BinaryTree DNA;
char a[15];
char b[15];

BinaryTree myBinaryTree;
Compare myCompare;
char array[14] = {'/0'};
srand(time(NULL));
for(int i = 0 ; i < 11; i++)
{
int a =rand() % 4;
switch(a)
{
case 0:
{
array[i] = 'A';
break;
}
case 1:
{
array[i] = 'T';
break;
}
case 2:
{
array[i] = 'C';
break;
}
case 3:
{
array[i] = 'G';
break;
}
default:
break;
}
}
cout << " " << array[0] << " " << endl;
cout << " " << "/" << " " << " \\ " << endl;
cout << " " << array[1] << " " << array[2] << endl;
cout << " " << "/" << " " << "\\ " << " " << " / " << " " << "\\" << endl;
cout << " " << array[3] << " " << array[4] << " " << array[5] << " " << array[6] << endl;
cout << " " <<"/" <<" " << "\\ " << " " << " /" << " " << " \\ " << "/" << " " << "\\ " << " " << "/" ;
cout << " " << "\\ " << endl;
cout << " " << array[7] << " " << array[8] << " " << array[9] << " " << array[10] << " " << array[11];
cout << " " << array[12] << " " << array[13] << " " << array[14] << endl;
root=new BinTreeNode;
root->data=array[0];
剩余字数不够了，剩下的程序在http://wenwen.soso.com/z/q196998592.htm

Answer 1

template <class Type> class BinaryTree;
template <class Type> class BinTreeNode
{
friend class BinaryTree<Type>;
private:
Type data;
BinTreeNode<Type> * leftChild;
BinTreeNode<Type> * rightChild;
public:
BinTreeNode(): leftChild (NULL),rightChild (NULL){}
BinTreeNode(Type item,BinTreeNode<Type> * left= NULL, BinTreeNode<Type> *right =NULL): data (item),leftChild (left),rightChild (right){}
Type GetData() const {return data;}
BinTreeNode<Type> * GetLeft () const { return leftChild;}
BinTreeNode<Type> * GetRight () const {return rightChild;}
void SetData(const Type&item){data=item;}
void SetLeft (BinTreeNode <Type>* L) {leftChild =L;}
void SetRight (BinTreeNode<Type>* R ){rightChild =R;}
};
template <class Type>class BinaryTree
{
private :
BinTreeNode <Type> * root;
Type RefValue;
void CreateBinTree( ifstream& in, BinTreeNode<Type> * & current);
BinTreeNode<Type >*Parent (BinTreeNode<Type> * subTree, BinTreeNode<Type> * current);
int Insert (BinTreeNode<Type> * & subTree const Type & item);// insert
void Traverse (BinTreeNode<Type> * subTree,ostream &out )const // 遍历
int Find(BinTreeNode <Type>* subTree,constType &item)const// 搜索
void destory (BinTreeNode <Type> * subTree);
public:
virtual BinaryTree(): root(NULL){}
virtual BinaryTree(Type value): RefValue (value),root (NULL){}
virtual ~BinaryTree (){destory (root);}
virtual int IsEmpty() { return root==NULL?1:0;}//判断树是否为空

virtual BinTreeNode <Type>* Parent (BinTreeNode<Type> * current)
{
return root == NULL || root == current?
NULL : Parent (root, current);
}//找 curent结点 的双亲
virtual BinTreeNode<Type>*LeftChild (BinTreeNode<Type> * current)
{return root!=NULL? current-> leftChild:NULL; }//取 current 结点的左子女
virtual BinTreeNode<Type>* RightChild (BinTreeNode<Type> * current)
{return root!=NULL? current-> rightChild:NULL; }//取 current 结点的you子女
virtual int Insert (const Type&item);
virtual BinTreeNode <Type> * Find (const Type & item)const;//搜索
BinTreeNode<Type> * GetRoot() const { return root;}//取根
friend istream & operator >> (istream & in, BinaryTree <Type>&Tree)//重载操作：输入
friend ostream & operator <<(ostream&our, BinaryTree<Type>&Tree)//重载操作：输出

}；
//以上定义的二叉树部分成员函数的实现如下：
template <class Type> void BinaryTreee<Type>::destory
(BinTreeNode<Type> * subTree)
{
if (subTree!=NULL){
destory (subTree->leftChild);
destory (subTree->rightChild);
delete subTree;
}
}//若指针subTree 不为空，则删除根为subTree 子树

template <class Type> BinTreeNode <Type> * BinaryTree <Tree>::Parent(BinTreeNode<Type> * subTree ,BinTreeNode <Type> * current)
{
if(subTree==NULL)return NULL;
if(subTree->leftChild == current|| subTree->rightChild==current) return subTree;
BinTreeNode <Type>* p;
if((p=Parent(subTree->leftChild,current))!=NULL) return p;
else return Parent(subTree->rightChild,current);
}//私有函数：从结点subTree开始，搜索结点current的双亲结点。若找到结点current的双亲结点，则函数返回双亲结点地址，否则函数返回NUll

template <class Type> void BinaryTree<Type>::Traverse (BinTreeNode<Type> * subTree ,ostream & out)const
{
if(subTree!=NULL){
out<<subTree->data<<'';
Traverse(subTree->leftChild ,out);
Traverse(subTree->rightChild, out);
}
}//私有函数：搜索并输出根为subTree 的二叉树

template <class Type > istream&operator>>(istream&in,BinaryTree<Type>&Tree)
{
Type item;
in(filename ,ios::in|ios::nocreate);//打开文件
if (! in){
cerr<<"文件没被发现！"<<endl;
exit(1);
}
CreateBinTree(in, Tree.root);
in.close();// 关闭文件
}// 建立一颗二叉树Tree。 in是输入流对象
template<class Type>
ostream&operator<<(ostream& out,BinaryTree<Type>&Tree){
out <<"二叉树的前序遍历\n";
Tree.Traverse (Tree.root,out);
out<<endl;
return out;

}

这个是我现在学的数据结构-里头很多需要自己改动下-因为二叉树不同哈-但是前序中序 后续的 代码都对-缺一个main 函数-使用的是模板

Answer 2

为什么一定要非递归的方式输出遍历序列？
数据结构里一般都是用的递归。同等高手给出非递归的方式输出~~
全当我打酱油吧。