【二叉树的先序创建、先序中序后序递归遍历、结点个数、叶子节点个数】实验报告+完整代码

题目: 二叉树的创建与遍历

一、实验目的和要求

（1）熟悉C++的上机环境，进一步掌握C++的结构特点；
（2）掌握二叉树的创建与遍历。

二、实验环境

Windows10, CodeBlocks.

三、实验内容及实施

【实验内容】
实验5： 二叉树的创建与遍历
编写一个程序，实现二叉树的各种运算，并在此基础上设计一个程序完成如下功能：
（1）创建一棵二叉树（用键盘按照先序遍历序列输入一个字符串生成二叉树）；
（2）输出前序、中序、后序遍历的遍历序列；
（3）统计并输出二叉树的的结点个数；
（4）输出二叉树的叶子结点的个数；(选做)
【程序流程】

#include<bits/stdc++.h>
using namespace std;
typedef int Status;
typedef char TElemType;
#define OVERFLOW -1
#define ERROR 0
#define OK 1
int cnt = 0;

//-----二叉树的二叉链式存储表示-----
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

BiTree T;

//3、先序遍历的顺序建立二叉链表 
void CreateBiTree(BiTree &T)
{//按先序次序输入二叉树中结点的值，创建二叉链表表示的二叉树T
    TElemType ch;
    cin>>ch;
    if(ch == '#')                   //递归结束，建空树
        T = NULL;
    else                            //递归创建二叉树
    {
        T = new BiTNode;            //生成根结点
        T->data = ch;               //根结点数据域置为 ch
        CreateBiTree(T->lchild);    //递归创建左子树
        CreateBiTree(T->rchild);    //递归创建右子树
    }
}

//17、先序遍历二叉树
void PreOrderTraverse(BiTree T)
{//先序遍历二叉树T的递归算法
    if(T)                               //若二叉树非空 
    {
        cout<<T->data;                  //访问根结点 
        PreOrderTraverse(T->lchild);     //中序遍历左子树 
        PreOrderTraverse(T->rchild);     //中序遍历右子树
    }
}

//18、中序遍历二叉树
void InOrderTraverse(BiTree T)
{//中序遍历二叉树T的递归算法
    if(T)                               //若二叉树非空 
    {
        InOrderTraverse(T->lchild);     //中序遍历左子树 
        cout<<T->data;                  //访问根结点 
        InOrderTraverse(T->rchild);     //中序遍历右子树
    }
}

//19、后序遍历二叉树
void PostOrderTraverse(BiTree T)
{//后序遍历二叉树T的递归算法
    if(T)                               //若二叉树非空 
    {
        PostOrderTraverse(T->lchild);   //中序遍历左子树 
        PostOrderTraverse(T->rchild);   //中序遍历右子树
        cout<<T->data;                  //访问根结点 
    }
}

//23、二叉树结点个数
int NodeCount(BiTree T)
{//统计二叉树T中的结点个数
    if(T == NULL)
        return 0;
    else
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

//24、二叉树叶子结点个数
void LeavesCount(BiTree T)
{
    if(T)
    {
        if(!T->lchild && !T->rchild)
            cnt++;
        LeavesCount (T->lchild);
        LeavesCount (T->rchild);
    }
}

int main()
{
    cout << "--------------- 菜单 --------------" << '\n';
    cout << " 操作0：退出程序" << '\n';
    cout << " 操作1：先序输入创建二叉树" << '\n';
    cout << " 操作2：输出先序遍历序列" << '\n';
    cout << " 操作3：输出中序遍历序列" << '\n';
    cout << " 操作4：输出后序遍历序列" <<'\n';
    cout << " 操作5：输出二叉树的结点个数" << '\n';
    cout << " 操作6：输出二叉树叶子结点的个数"<< '\n';
    cout << "-----------------------------------" << '\n';
    int n, flag = 1;;
    while(flag)
    {
        cout << '\n' << "您想进行的操作的序号是：";
        cin >> n;
        switch(n)
        {
            case 0:
            {
                flag = 0;
                cout << "感谢使用本程序，祝您生活愉快！" << '\n';
                break;
            }
            case 1:
            {
                cout << "请按先序输入创建二叉树（空树输入#）：";
                CreateBiTree(T);
                cout << "二叉树创建完毕！" << '\n';
                break;
            }
            case 2:
            {
                cout << "按先序遍历输出二叉树：";
                PreOrderTraverse(T);
                cout << '\n';
                break;
            }
            case 3:
            {
                cout << "按中序遍历输出二叉树：";
                InOrderTraverse(T);
                cout << '\n';
                break;
            }
            case 4:
            {
                cout << "按后序遍历输出二叉树：";
                PostOrderTraverse(T);
                cout << '\n';
                break;
            }
            case 5:
            {
                cout << "二叉树的结点个数是：" ;
                cout << NodeCount(T) << '\n';
                break;
            }
            case 6:
            {
                cnt = 0;
                cout << "二叉树叶子结点的个数是：";
                LeavesCount(T);
                cout << cnt <<'\n';
                break;
            }
        }
    }
    return 0;
}

四、实验结果

五、实验讨论

（1）熟悉了C++的上机环境，进一步掌握C++的结构特点；
（2）掌握了二叉树的创建与遍历。