2022-05-05树和二叉树

//算法5.3 先序遍历的的顺序建立二叉链表
#include<iostream>
using namespace std;

//二叉树的二叉链表存储表示
typedef struct BiNode
{               
    char data;                      //结点数据域
    struct BiNode *lchild,*rchild;  //左右孩子指针
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)
{   
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
    char ch;
    cin >> ch;
    if(ch=='#')  T=NULL;            //递归结束，建空树
    else{                           
        T=new BiTNode;
        T->data=ch;                 //生成根结点
        CreateBiTree(T->lchild);    //递归创建左子树
        CreateBiTree(T->rchild);    //递归创建右子树
    }                               //else
}                                   //CreateBiTree
//先序遍历的递归算法                         
void InOrderTraverse1(BiTree T)
{  
    if(T){
        cout << T->data;
        InOrderTraverse1(T->lchild);
        InOrderTraverse1(T->rchild);
    }
}
//用算法5.1 中序遍历的递归算法                          
void InOrderTraverse2(BiTree T)
{  
    //中序遍历二叉树T的递归算法
    if(T){
        InOrderTraverse2(T->lchild);
        cout << T->data;
        InOrderTraverse2(T->rchild);
    }
}
//后序遍历的递归算法                         
void InOrderTraverse3(BiTree T)
{  
    if(T){
        InOrderTraverse3(T->lchild);
        InOrderTraverse3(T->rchild);
        cout << T->data;
    }
}

int Depth(BiTree T)
{ 
    int m,n;
    if(T == NULL ) return 0;        //如果是空树，深度为0，递归结束
    else 
    {                           
        m=Depth(T->lchild);         //递归计算左子树的深度记为m
        n=Depth(T->rchild);         //递归计算右子树的深度记为n
        if(m>n) return(m+1);        //二叉树的深度为m 与n的较大者加1
        else return (n+1);
    }
}
int NodeCount(BiTree T)
{
     if(T==NULL) return 0;              // 空树，则结点个数为0，递归结束
     else return NodeCount(T->lchild)+ NodeCount(T->rchild) +1;
     //否则结点个数为左子树的结点个数+右子树的结点个数+1
} 
int LeafCount(BiTree T)
{
     if(T) return 0+(LeafCount(T->lchild)&&LeafCount(T->rchild));// 空树，则结点数为0，递归结束
     else return 1;
     
} 

void menu()       //显示菜单 
{
    cout<<"----------------------\n";     
    cout<<"1.按先序、中序和后序遍历二叉树，输出所有的结点（递归算法）\n";     
    cout<<"2.求二叉树的结点个数\n";     
    cout<<"3.输出二叉树的叶子结点\n";     
    cout<<"4.求二叉树的高度\n";         
    cout<<"0.退出\n";      //以上为功能介绍     
    cout<<"----------------------\n";     
    fflush(stdin); 
         
} 
int main()
{
    int a;
    BiTree tree;
    cout<<"请输入建立二叉链表的序列：\n";
    CreateBiTree(tree);
    menu();
    while(1)
    {
        cout<<"\n请输入功能选项：";  
        cin>>a;
        //判断功能是否存在，不存在就重新输入 
        while(a<0&&a>4)
        {
             cout<<"暂时没有此功能，请重新输入：";
             fflush(stdin);             
             cin>>a; 
        }  
        switch(a)
        {
            case 1:
                cout<<"按先序、中序和后序遍历二叉树，输出所有的结点（递归算法）\n";
                cout<<"先序遍历的结果为：";
                InOrderTraverse1(tree);cout<<endl;
                cout<<"中序遍历的结果为：";
                InOrderTraverse2(tree);cout<<endl;
                cout<<"后序遍历的结果为：";
                InOrderTraverse3(tree);cout<<endl;
                break;
            case 2:
                cout<<"结点个数为："<<NodeCount(tree)<<endl;
                break;
            case 3:
                cout<<"叶子结点个数为："<<LeafCount(tree)<<endl;
                break;
            case 4:
                cout<<"数的深度为："<<Depth(tree)<<endl;
                break;

            default:
                return 0;
            
            
        }
    }   
    return 0;
}