前言

这次是数据结构第五次作业,操作二叉树来实现存储,使用链式存储结构实现二叉树的建立和三种遍历递归和非递归的实现。
Snipaste_2019-11-03_22-49-39.png

运行结果

QQ图片20191103224206.png
非递归输入内容:1 a 2 b 3 c 4 d 5 e 6 #
递归输入内容:ABD##E##C##
先序遍历结果为:ABDEC
中序遍历结果为:DBEAC
二叉树叶子总数为:5
二叉树度为2的结点数为:2
二叉树深度为:3
Snipaste_2019-11-03_22-45-18.png

代码

#include <iostream>
using namespace std;
#define Maxnum 20
//定义树的结点类型
typedef struct bitreenode{
    char data;
    struct bitreenode *lchild,*rchild;

}bitree,*Btree;
//递归建立二叉树
void CreateBiTree(Btree &bt){
    char ch;
    cin>>ch;
    if(ch=='#')
        bt = NULL; //创建空树
    else{
        bt = new bitreenode;
        bt->data = ch;
        CreateBiTree(bt->lchild);
        CreateBiTree(bt->rchild);
    }
}
//非递归建立二叉树
bitree *creatree(){
    int i,j;
    char ch;
    bitree *p[Maxnum]; //定义结点指针数组
    bitree *root,*s;
    cout<<"请输入编号i和节点ch,若输入编号为0或节点为'#',则终止!\n";
    cin>>i; //输入结点编号
    cin>>ch; //输入根结点
    while(i!=0&&ch!='#'){
        s = new bitree; //生成新结点
        s->data = ch;
        s->lchild = NULL;
        s->rchild = NULL;
        p[i]=s;
        if(i==1)
            root=s; //序号为1,为根结点
        else{
            j = i/2; //双亲结点的序号
            if(i%2==0) //序号为奇数,作为双亲的左孩子插入
                p[j]->lchild=s;
            else
                p[j]->rchild=s;
        }
        cout<<"\n输入i,ch:\n";
        cin>>i;
        cin>>ch; //输入二叉树结点及编号
    }
    return (root);
}
//先序遍历二叉树
void preorder(bitree *t){
    if(t==NULL)
        return;
    else{
        cout<<t->data;
        preorder(t->lchild);
        preorder(t->rchild);
    }
}
//中序遍历二叉树
void inorder(bitree *t){
    if(t==NULL)
        return;
    else{
        inorder(t->lchild);
        cout<<t->data;
        inorder(t->rchild);
    }
}
//统计子叶结点个数
int Countleaf(bitree *t){
    if(t==NULL)
        return 0;
    if(t->lchild==NULL&&t->rchild==NULL)
        return 1;
    else
        return (Countleaf(t->lchild)+Countleaf(t->rchild)+1);
}
//统计度为2的结点个数
int CountNode2(bitree *t){
    if(t==NULL)
        return 0;
    if(t->lchild!=NULL&&t->rchild!=NULL)
        return (CountNode2(t->lchild)+CountNode2(t->rchild)+1);
    else
        return (CountNode2(t->lchild)+CountNode2(t->rchild));
}
//计算二叉树的深度
int Depth(bitree *t){
    int d=0,dl,dr;
    if(t==NULL)
        return 0;
    dl=Depth(t->lchild);
    dr=Depth(t->rchild);
    d=(dl>dr?dl:dr)+1;
    return d;
}
//主程序
int main() {
    bitree *bt;
    int choice;
    while(1) {
        cout << endl << endl << endl;
        cout << "**********************\n\n";
        cout << "1.非递归建立二叉树\n";
        cout << "2.先序遍历二叉树\n";
        cout << "3.中序遍历二叉树\n";
        cout << "4.计算二叉树的叶子总数\n";
        cout << "5.计算二叉树为2的结点数\n";
        cout << "6.计算二叉树的深度\n";
        cout << "7.递归建立二叉树\n";
        cout << "0.退出\n\n";
        cout << "\n 输入你的选择:";
        cin >> choice;
        switch(choice)
        {
            case 1:bt=creatree();
            cout<<"\n非递归二叉树建立完成\n";
            break;
            case 2:cout<<"\n先序遍历结果为:";
            preorder(bt);
            break;
            case 3:cout<<"\n中序遍历结果为:";
            inorder(bt);
            break;
            case 4:cout<<"\n二叉树叶子总数为:"<<Countleaf(bt);
            break;
            case 5:cout<<"\n二叉树度为2的结点数为:"<<CountNode2(bt);
            break;
            case 6:cout<<"\n二叉树深度为:"<<Depth(bt);
            break;
            case 7:cout<<"请按照二叉树的先序序列输入结点的字符,无左右子树则以'#'代替:\n";
            CreateBiTree(bt);
            cout<<"\n递归二叉树建立完成\n";
            break;
            case 0:cout<<"\n程序结束,按任意键返回!\n";
            exit(0);
        }
    }
    return 0;
}

问题

这次计算二叉树度为2的时候,直接复制的计算子叶的方法,导致最后不是递归,结果错误。

Last modification:May 27th, 2020 at 02:07 pm
如果觉得我的文章对你有用,请随意赞赏