数据结构与算法-树

#include <iostream>
#define nullptr NULL
using namespace std;

typedef struct BiNode{
    char data;
    struct BiNode *lchild,*rchild;
}*BiTree;

void CreateBiTree(BiTree &T){
    char ch;
    cin>>ch;

    if (ch=='#')
        T=NULL;
    else{
        T = new BiNode;
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

int Depth(BiTree T){
    int m,n;
    if(T==NULL)
        return 0;
    else{
        m =Depth(T->lchild);
        n =Depth(T->rchild);
        if(m>n)
            return m+1;
        else
            return n+1;
    }
}

void InOderTraverse(BiTree T){
    if(T){
        InOderTraverse(T->lchild);
        cout<<T->data;
        InOderTraverse(T->rchild);
    }
}

int NodeCount(BiTree T){
    if(T==NULL)
        return 0;
    else
        return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

int main(){
    BiTree tree = nullptr;
    int choose = -1;
    cout<<"1.建立二叉树"<<endl;
    cout<<"2.计算二叉树的深度"<<endl;
    cout<<"3.中序遍历二叉树"<<endl;
    cout<<"4.计算二叉树节点个数"<<endl;
    cout<<"5.退出程序"<<endl;
    while (choose){
        cout<<"请选择功能:";
        cin>>choose;
        switch (choose){
            case 1: //建立二叉树
                cout<<"输入二叉树的序列:";
                CreateBiTree(tree);
                break;
            case 2:  //计算二叉树深度
                if(tree==nullptr)
                    cout<<"请先建立二叉树"<<endl;
                else
                    cout<<"树的深度为:"<<Depth(tree)<<endl;
                break;
            case 3:
                if(tree==nullptr)
                    cout<<"请先建立二叉树"<<endl;
                else{
                    cout<<"二叉树的序列为(中序):";
                    InOderTraverse(tree);
                    cout<<endl;
                }
                break;
            case 4: //统计节点个数
                if(tree==nullptr)
                    cout<<"请先建立二叉树"<<endl;
                else{
                    cout<<"二叉树的节点:"<<NodeCount(tree)<<endl;
                }
                break;
            default:
                break;
        }
    }
    
    return 0;
}
#include <iostream>
#define nullptr NULL
using namespace std;
//树的类型定义
typedef struct BiNode{
    char data;//包含一个字符型的数据成员data
    struct BiNode *lchild,*rchild;//指向二叉树节点结构体的成员,分别是lchild,rchild
}*BiTree;//结构体二叉树节点别名,表示指向struct BiNode的结构指针,可用于声明二叉树的根节点或其他节点
//先序遍历创建二叉树
void CreateBiTree(BiTree &T){
    char ch;   //用于存储用户输入的字符
    cin>>ch;

    if (ch=='#')
        T=NULL; //检查读取字符是否为空#,如果是表示当前节点为空
    else{
        T = new BiNode;//使用new动态分配一个二叉树节点结构体内存,并将其地址赋值给T
        T->data=ch;  //将读取到的字符复制给新节点data
        CreateBiTree(T->lchild);//递归调用创建二叉树的函数,创建当前节点的左子树,这里的T->lchild表示当前节点的左孩子是指向二叉树节点结构体的指针
        CreateBiTree(T->rchild);
    }
}
//计算二叉树的深度
int Depth(BiTree T){
    int m,n;//声明两个整数变量m,n用于存储左子树和右子树
    if(T==NULL)
        return 0;
    else{   //如果当前节点不为空,进入else分支
        m =Depth(T->lchild); //调用depth函数计算左子树的深度,并将结果赋值给m
        n =Depth(T->rchild);//调用depth函数计算右子树的深度,并将结果赋值给n
        if(m>n)
            return m+1;
        else
            return n+1;
    }
}
//中序遍历二叉树
void InOderTraverse(BiTree T){
    if(T){
        InOderTraverse(T->lchild);
        cout<<T->data;
        InOderTraverse(T->rchild);
    }
}
//统计二叉树节点个数
int NodeCount(BiTree T){
    if(T==NULL)
        return 0;
    else
        return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

int main(){
    BiTree tree = nullptr;
    int choose = -1;
    cout<<"1.建立二叉树"<<endl;
    cout<<"2.计算二叉树的深度"<<endl;
    cout<<"3.中序遍历二叉树"<<endl;
    cout<<"4.计算二叉树节点个数"<<endl;
    cout<<"5.退出程序"<<endl;
    while (choose){
        cout<<"请选择功能:";
        cin>>choose;
        switch (choose){
            case 1: //建立二叉树
                cout<<"输入二叉树的序列:";
                CreateBiTree(tree);
                break;
            case 2:  //计算二叉树深度
                if(tree==nullptr)
                    cout<<"请先建立二叉树"<<endl;
                else
                    cout<<"树的深度为:"<<Depth(tree)<<endl;
                break;
            case 3:
                if(tree==nullptr)
                    cout<<"请先建立二叉树"<<endl;
                else{
                    cout<<"二叉树的序列为(中序):";
                    InOderTraverse(tree);
                    cout<<endl;
                }
                break;
            case 4: //统计节点个数
                if(tree==nullptr)
                    cout<<"请先建立二叉树"<<endl;
                else{
                    cout<<"二叉树的节点:"<<NodeCount(tree)<<endl;
                }
                break;
            default:
                break;
        }
    }
    
    return 0;
}

评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注