二叉树的创建一数据结构一C++

#include <iostream> using namespace std; //二叉树结点
typedef struct BitNode               
{
    char ch;
    struct BitNode *lchild,*rchild;
}BitNode,*BitTree; //创建链式队列的方法
/*
typedef struct QNode
{
    BitNode *tree;
    struct QNode *next;
}QNode,*Queueptr; typedef struct
{
    Queueptr fro;
    Queueptr rear;
}LinkQueue;
*/ //按照先序创建二叉树
void CreatBitTree(BitTree &T)
{     char c;
    cin>>c;
    if(c=='#')
        T = NULL;
    else
    {
        T = new BitNode;
        T -> ch = c;
        CreatBitTree(T -> lchild);
        CreatBitTree(T -> rchild);
    }
} //将二叉树按照先序输出
void Print1(BitTree T)
{
    if(T != NULL)
    {
        cout<<T -> ch;
        Print1(T -> lchild);
        Print1(T -> rchild);
    }
} //将二叉树按照中序输出
void Print2(BitTree T)
{
    if(T != NULL)
    {
        Print2(T -> lchild);
        cout<<T -> ch;
        Print2(T -> rchild);
    }
} //将二叉树按照后序输出
void Print3(BitTree T)
{
    if(T != NULL)
    {
        Print3(T -> lchild);
        Print3(T -> rchild);
        cout<<T -> ch;
    }
} //将二叉树按照层次输出
void Print4(BitTree T)
{
    int m=10,i=0,fro=0,rear=0;
    BitTree *a = new BitTree[m];
    BitNode *t,*t1;
    a[rear] = T;
    cout<<a[rear] -> ch;
    rear = (rear+1)%(m+1);      //最大a[10]
    while(fro != rear)
    {
        t = a[fro];
        fro = (fro+1)%(m+1);      //读取一个双亲并删除
        if(t -> lchild)
        {
            t1 = t -> lchild;
            a[rear] = t1;
            rear = (rear+1)%(m+1);
            cout<<t1 -> ch;
        }
        if(t -> rchild)
        {
            t1 = t -> rchild;
            a[rear] = t1;
            rear = (rear+1)%(m+1);
            cout<<t1 -> ch;
        }
    }
} int Show(BitTree T)
{
    int n;
    cout<<"请输入遍历的顺序 1:先序遍历 2:中序遍历 3:后序遍历 4:层次遍历 5:退出程序"<<endl;
    cin>>n;
    switch(n)
    {
    case 1:
        {
            Print1(T);
            cout<<endl;
        }
        break;
    case 2:
        {
            Print2(T);
            cout<<endl;
        }
        break;
    case 3:
        {
            Print3(T);
            cout<<endl;
        }
        break;
    case 4:
        {
            Print4(T);
            cout<<endl;
        }
        break;
    case 5:
        {
            cout<<"程序退出成功"<<endl;
            return 0;
        }
        break;
    default:
        cout<<"输入有误,重新输入"<<endl;
        break;
    }
} int main()
{
    int m=1;
    cout<<"请按照先序输入:"<<endl;
    BitTree T;
    CreatBitTree(T);
    while(m!=0)
    {
      m=Show(T);
    }
    return 0;
} /*
测试用例
ABC##DE#G##F###
*/

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄