二叉树的具体代码实现

树的基本常考的操作都包含！！

#include<iostream>
#include<algorithm>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
#define OVERFLOW 0
using namespace std;

typedef char TElemType;
typedef struct BiTNode              //结点结构 
{
    TElemType data;                 //结点数据 
    struct BiTNode *lchild,*rchild; //左右孩子指针 
}BT;

/*
    按前序输入二叉树中结点的值(一个字符)
    #表示空树,构造二叉树表表示二叉树T. 
*/
BT* CreateTree()            //测试:AB#D##C## 
{
    BT* t;
    TElemType e;
    cin>>e;
    if(e == '0')
        t = NULL;
    else
    {
        t = new BT;
        t->data = e;
        cout<<"请输入"<<e<<"的左子结点:"<<endl;
        t->lchild = CreateTree();
        cout<<"请输入"<<e<<"的右子结点:"<<endl;
        t->rchild = CreateTree(); 
    }
    return t;
}


/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BT* T)
{
    if(T == NULL)
        return;
    cout<<T->data<<endl;//显示结点数据,可以更改为其他对结点操作
    PreOrderTraverse(T->lchild);//再先序遍历左子树
    PreOrderTraverse(T->rchild);//最后先序遍历右子树
}

/*中序遍历*/
void InOrderTraverse(BT* T)
{
    if(T == NULL)
        return;
    InOrderTraverse(T->lchild);//中序遍历左子树 
    cout<<T->data<<endl;//显示结点数据,可以更改为其他对结点操作 
    InOrderTraverse(T->rchild);//最后中序遍历右子树 
}

/*后序遍历*/
void PostOrderTraverse(BT* T)
{
    if(T == NULL)
        return;
    PostOrderTraverse(T->lchild);//先后序遍历左子树 
    PostOrderTraverse(T->rchild);//再后序遍历右子树 
    cout<<T->data<<endl;//显示结点数据,可以更改为其他队节点操作 
}


/*求叶子数(前序遍历求法)*/
int BiLeafTree(BT* T)
{
    if(T != NULL)
    {
        if(T->lchild == NULL && T->rchild == NULL)
            return 1;
        return 1 + BiLeafTree(T->lchild) + BiLeafTree(T->rchild);
    }
}

/*求结点数*/
int BiLength(BT* T)
{
    if(T)
        return 1 + BiLength(T->lchild) + BiLength(T->rchild);   
}

/*求树深度*/
int Depth(BT* T)
{
    if(T == NULL)
        return 0;
    return 1 + max(Depth(T->lchild),Depth(T->rchild));
}

/*菜单*/
void menu()
{
    BT* T;
    while(1)
    {
        cout<<"\t**********树子系统*************"<<endl;
        cout<<"\t   1----------建二叉树"<<endl;
        cout<<"\t   2----------先序遍历"<<endl;
        cout<<"\t   3----------中序遍历"<<endl;
        cout<<"\t   4----------后序遍历"<<endl;
        cout<<"\t   5----------求叶子数"<<endl;
        cout<<"\t   6----------求结点数"<<endl;
        cout<<"\t   7----------求树深度"<<endl;
        cout<<"\t   0----------退    出"<<endl;
        cout<<"\t********************************"<<endl;
        cout<<"请输入菜单号<0~6> : ";
        int choice;
        cin>>choice;
        switch(choice)
        {
            case 1:cout<<"根据创建要求逐个输入:(若子树为NULL,则只需输入0即可)"<<endl<<"请输入根结点:"<<endl;
                    T = CreateTree();
                break;
            case 2:
                    PreOrderTraverse(T);
                break;
            case 3:
                    InOrderTraverse(T);
                break;
            case 4:
                    PostOrderTraverse(T);
                break;
            case 5:
                    cout<<"叶子结点数:"<<BiLeafTree(T)<<endl; 
                break;
            case 6:
                    cout<<"结点数:"<<BiLength(T)<<endl; 
                break;
            case 7:
                    cout<<"二叉树的深度:"<<Depth(T)<<endl;
                break;
            case 0:
                    exit(OVERFLOW);
            default:
                cout<<"无效指令!"<<endl<<"重新输入!"<<endl;
                break;
        }
    }
}

int main()
{
    menu();
    return 0;
}

考研数据结构目录:

https://www.acwing.com/file_system/file/content/whole/index/content/5394132/