建立二叉树,层序,先序遍历
任务:要求能够输入树的各个结点,并能够输出用不同方法遍历的遍里序列;分别建立二叉树存储结构的输入函数.输出层序遍里的函数.输出先序遍里的函数

我写的怎么都不行啊。。。大家帮忙看看完整没有，程序可以运行，可是得不到结果，帮我改一下。。。。。先谢谢大家了，急啊 ，也帮我把思路理一下。。谢谢

#include<iostream.h>
#include<stdlib.h>
#include<strstrea.h>
typedef char ElemType;
struct BTreeNode{
ElemType data;
BTreeNode *left;
BTreeNode *right;
};

void InitBTree(BTreeNode* & BT)
{
BT=NULL;
}
void CreateBTree(BTreeNode*& BT,char* a)
{
BTreeNode* s[30];
int top=-1;
BT=NULL;
BTreeNode* p;
int k;
istrstream ins(a);
char ch;
ins>>ch;
while(ch!='@')
{
switch(ch)
{
case'(':
top++;s[top]=p;k=1;
break;
case')':
top--;
break;
case',':
k=2;
break;
default:
p=new BTreeNode;
p->data=ch;p->left=p->right=NULL;
if(BT==NULL)
BT=p;
else{
switch(k)
{
case 1:
s[top]->left=p;
break;
case 2:
s[top]->right=p;
}
}
}
ins>>ch;
}
}

//前序遍历
void Preorder(BTreeNode* BT)
{
if(BT!=NULL){
cout<<BT->data<<' ';
Preorder(BT->left);
Preorder(BT->right);
}

}
//输出二叉树
void PrintBTree(BTreeNode *BT)
{
if(BT!=NULL)
{
cout<<BT->data;
if(BT->left!=NULL||BT->right!=NULL)
{
cout<<'(';
PrintBTree(BT->left);
if(BT->right!=NULL)
cout<<',';
PrintBTree(BT->right);
cout<<')';
}
}
}

void main()
{
BTreeNode *bt;
InitBTree(bt);
char b[30];
cout<<"输入以'@'字符作为结束符的字符串:"<<endl;
cin.getline(b,sizeof(b));
CreateBTree(bt,b);

Preorder(bt);
}

#include\"BTree.h\"
#include\"SeqQueue.cpp\"

template<class T>
void BTree<T>::SetFlag()
{
    cin>>flag;
}

template<class T>
bool BTree<T>::IsEmpty()const
{
    return root==NULL;
}

template<class T>
bool BTree<T>::Root(T& x)const
{
    if(root){
        x=root->element;
        return true;
    }
    return false;
}

/*template<class T>
void BTree<T>::MakeTree(const T& e,BTree<T>&left,BTree<T>&right)
{
    BTNode<T>* p;
    p=new BTNode<T>(e,left.root,right.root);
    left.root=right.root=0;//释放空间
    root=p;
}*/

template<class T>
void BTree<T>::InputPerfTr(istream& in)
{
    BTNode<T> *p;
    T a;
    SeqQueue<BTNode<T>*> node(20);
    node.EnQueue(root);
    cout<<\"按层次输入数据(输入\\"\"<<flag<<\"\\"结束):\"<<endl;
    in>>a;
    while(a!=flag){
        p=node.Front()=new BTNode<T>(a);
        node.DeQueue();        
        in>>a;
        node.EnQueue(p->lchild);
        node.EnQueue(p->rchild);
    }
}

template<class T>
void BTree<T>::InputAnyTr(istream& in)
{
    BTNode<T> *p;
    T a;int b;
    SeqQueue<BTNode<T>*> node(20);
    node.EnQueue(root);
    cout<<\"以(数据  属性)格式按层次输入数据:\"<<endl;
    cout<<\"属性:0:无孩子 1:只有左孩子 2:只有右孩子 3:有两个孩子:\"<<endl;
    in>>a>>b;
    while(!node.IsEmpty()){
        p=node.Front()=new BTNode<T>(a);
        node.DeQueue();
        in>>a>>b;
        switch(b){
        case 3:node.EnQueue(p->lchild);
        case 2:node.EnQueue(p->rchild);break;
        case 1:node.EnQueue(p->lchild);break;
        case 0:
        default:break;
        }
    }
}

template<class T>
void BTree<T>::Output(ostream& out)
{
    cout<<\"请选择遍历顺序:\"<<endl;
    cout<<\"<1,先序 2,中序 3,后序 4,按层次 0,所有顺序 其他键返回>:\";
    int a;cin>>a;
    switch(a){
    case 1:out<<\"  先序:\";
        PreOrder(root);out<<endl;break;
    case 2:out<<\"  中序:\";
        InOrder(root);out<<endl;break;
    case 3:out<<\"  后序:\";
        PostOrder(root);out<<endl;break;
    case 4:out<<\"按层次:\";
        PostOrder(root);out<<endl;break;
    case 0:
        out<<\"  先序:\";PreOrder(root);out<<endl;
        out<<\"  中序:\";InOrder(root);out<<endl;
        out<<\"  后序:\";PostOrder(root);out<<endl;
        out<<\"按层次:\";PostOrder(root);
    default:out<<endl;break;
    }
}
/*template<class T>
void BTree<T>::BreakTree(T& e,BTree<T>&left,BTree<T>&right)
{
    BTNode<T>* p=root;
    if(p){
        e=p->element;
        left.root=p->lchild;
        right.root=p->rchild;
    }
    delete p;
}*/

template<class T>
int BTree<T>::Height(BTNode<T>* t)
{
    if(!t)return 0;
    static int lh=1,rh=1;
    if(t->lchild)lh+=Height(t->lchild);
    if(t->rchild)rh+=Height(t->rchild);
    return lh>rh?lh:rh;
}

template<class T>
int BTree<T>::LeafNum(BTNode<T>* t)
{
    if(!t)return 0;
    static int l=0;//在递归调用中这样的赋值执行几次?
    if(!t->lchild&&!t->rchild)return 1;
    if(t->lchild)l+=LeafNum(t->lchild);
    if(t->rchild)l+=LeafNum(t->rchild);
    return l;
}

template<class T>
void BTree<T>::Copy(BTNode<T>* r,BTNode<T>* t)
{
    if(r!=t){
        delete r;
        r=new BTNode<T>(t->element);
        if(t->lchild)Copy(r->lchild,t->lchild);
        if(t->rchild)Copy(r->lchild,t->lchild);
    } 
}
        

template<class T>
void BTree<T>::PermuteLR(BTNode<T>* t)
{
    BTNode<T> *temp;
    if(!t)return;
    if(t->lchild||t->rchild){
        temp=t->lchild;
        t->lchild=t->rchild;
        t->rchild=temp;
        if(t->lchild)PermuteLR(t->lchild);
        if(t->rchild)PermuteLR(t->rchild);
    }
}

template<class T>
void BTree<T>::PreOrder(BTNode<T>* t)
{
    if(t){
        cout<<t<<\"  \";
        if(t->lchild)PreOrder(t->lchild);
        if(t->rchild)PreOrder(t->rchild);
    }
}

template<class T>
void BTree<T>::InOrder(BTNode<T>* t)
{
    if(t){
        if(t->lchild)InOrder(t->lchild);
        cout<<t<<\"  \";
        if(t->rchild)InOrder(t->rchild);
    }
}
template<class T>
void BTree<T>::PostOrder(BTNode<T>* t)
{
    if(t){
        if(t->lchild)PostOrder(t->lchild);
        if(t->rchild)PostOrder(t->rchild);
        cout<<t<<\"  \";
    }
}
template<class T>
void BTree<T>::LayerOrdor(BTNode<T>* t)
{
    SeqQueue<BTNode<T>*> node(30);
    BTNode<T> *p=t;
    node.EnQueue(p);
    while(!node.Isempty()){
        p=node.Front();
        node.DeQueue();
        cout<<p<<\"  \";
        if(p->lchild)node.EnQueue(p->lchild);
        if(p->rchild)node.EnQueue(p->rchild);
    }
}
            
template<class T>
void BTree<T>::DestroyBTree(BTNode<T>* t)
{
    if(t){
        if(t->lchild)DestroyBTree(t->lchild);
        if(t->rchild)DestroyBTree(t->rchild);
        delete t;//delete t以后，t这个指针还存在吗？
    }
}

template<class T>
istream& operator>>(istream& in,BTree<T>& b)
{
    int a;
    cout<<\"选择要输入的二叉树的类型:0:完全二叉树 1:一般二叉树\"<<endl;
    cin>>a;
    if(a==0){
        cout<<\"设定输入停止符号:\";
        b.SetFlag();
        b.InputPerfTr(in);
    }
    else if(a==1)
        b.InputAnyTr(in);
    else return in;
    return in;
}

template<class T>
ostream& operator<<(ostream& out,BTree<T>& b)
{
    b.Output(out);
    return out;
}
#include\"iostream.h\"
template<class T> class BTree;
template<class T>
class BTNode
{    
public:
    BTNode(){lchild=rchild=0;}
    BTNode(const T& e)
    {
        element=e;
        lchild=rchild=0;
    }
    BTNode(const T& e,BTNode<T>* l,BTNode<T>* r)
    {
        element=e;
        lchild=l;
        rchild=r;
    }
private:
    T element;
    BTNode<T> *lchild,*rchild;
    friend class BTree<T>;
    friend ostream& operator<<(ostream& out,BTNode<T>& a);
};

template<class T>
ostream& operator<<(ostream& out,BTNode<T>& a)
{
    out<<a.element<<\"  \";
    return out;
}
#include\"BTNode.h\"
template<class T>
class BTree
{
public:
    BTree(){root=NULL;}//创建一颗空树
    BTree(T c){flag=c;root=NULL;}//指定输入结束标志
    ~BTree(){DestroyBTree(root);}//释放一棵树
    void SetFlag();//设定输入结束标志
    bool IsEmpty()const;//判空
    bool Root(T& x)const;//返会根节点
    int Height(){return Height(root);}//计算树的高度
    int LeafNum(){return LeafNum(root);}//计算树中叶子个数
    BTree<T> operator=(BTree<T> &bt)//复制一棵树
    {
        flag=bt.flag;
        Copy(root,bt.root);
        return *this;
    }
    void PermuteLR(){PermuteLR(root);}//置换左右子树
protected:
    T flag;//输入结束标志
    BTNode<T>* root;
private:
    //void MakeTree(const T& e,BTree<T>&left,BTree<T>&right);
    void InputPerfTr(istream& in);
    void InputAnyTr(istream& in);
    void Output(ostream& out);
    //void BreakTree(T& e,BTree<T>&left,BTree<T>&right);
    int Height(BTNode<T>* t);
    int LeafNum(BTNode<T>* t);
    void Copy(BTNode<T>* r,BTNode<T>* t);
    void PermuteLR(BTNode<T>* t);
    void PreOrder(BTNode<T>* t);//前序遍历
    void InOrder(BTNode<T>* t);//中序遍历
    void PostOrder(BTNode<T>* t);//后序遍历
    void LayerOrdor(BTNode<T>* t);//按层次遍历
    void DestroyBTree(BTNode<T>* t);
    friend istream& operator>>(istream& in,BTree<T>&);
    friend ostream& operator<<(ostream& out,BTree<T>&);
};
#include\"BTree.cpp\"
void main()
{
    BTree<char> a,b;
    char ch;

    cout<<\"Input the Tree Of A:\"<<endl;
    cin>>a;
    cout<<\"The Tree Of A Is:\"<<endl<<a;
    a.Root(ch);
    cout<<\"  Root:\"<<ch<<endl;
    cout<<\"Leaves:\"<<a.LeafNum()<<endl;
    cout<<\"Height:\"<<a.Height()<<endl;
    cout<<endl;

    cout<<\"Input the Tree Of B:\"<<endl;
    cin>>b;
    cout<<\"The Tree Of B Is:\"<<endl<<b;
    b.Root(ch);
    cout<<\"  Root:\"<<ch<<endl;
    cout<<\"Leaves:\"<<b.LeafNum()<<endl;
    cout<<\"Height:\"<<b.Height()<<endl;
    cout<<endl;

    a=b;
    cout<<\"The Tree Of A After \\"A=B\\" Is:\"<<endl;
    cout<<a;
    cout<<\"Leaves:\"<<a.LeafNum()<<endl;
    cout<<\"Height:\"<<a.Height()<<endl;
    cout<<endl;

    a.PermuteLR();
    cout<<\"The Tree Of A After Permuted Is:\"<<endl;
    cout<<a;
    cout<<endl;
}

[此贴子已经被作者于2006-7-6 18:52:38编辑过]