【数据结构】第5章树和二叉树实验6：中序线索二叉树的创建与遍历

超、凢脫俗 2022-11-29 03:07 76阅读 0赞

【线索二叉树的中序创建、先序中序后序遍历】实验报告+完整代码

--------------------

题目: 中序线索二叉树的创建与遍历

## 一、实验目的和要求 ##

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

## 二、实验环境 ##

Windows10, CodeBlocks.

## 三、实验内容及实施 ##

【实验内容】  
在实验5： 二叉树的创建与遍历的基础上完成如下功能：  
（1）中序线索化二叉树；  
（2）中序遍历线索二叉树并输出的遍历序列；  
【程序流程】

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef char TElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    char ch;
    int cnt;
    
    //-----线索二叉树的存储表示-----
    typedef struct BiThrNode
    {
        
        TElemType data;
        struct BiThrNode *lchild, *rchild;
        int LTag, RTag;
    }BiThrNode, *BiThrTree;
    
    BiThrTree T, Thrt, p, pre;
    
    //0、先序输入创建二叉树
    void CreateBiTree(BiThrTree &T)
    {
        
        cin>>ch;
        if(ch == '#')
            T = NULL;
        else
        {
        
            T = new BiThrNode;
            T->data = ch;
            T->LTag = 0;
            T->RTag = 0;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }
    }
    
    //1、输出先序遍历序列
    void PreOrderTraverse(BiThrTree T)
    {
        
        if(T)
        {
        
            cout<<T->data;
            PreOrderTraverse(T->lchild);
            PreOrderTraverse(T->rchild);
        }
    }
    
    //2、输出中序遍历序列
    void InOrderTraverse(BiThrTree T)
    {
        
        if(T)
        {
        
            InOrderTraverse(T->lchild);
            cout<<T->data;
            InOrderTraverse(T->rchild);
        }
    }
    
    //3、输出后序遍历序列
    void PostOrderTraverse(BiThrTree T)
    {
        
        if(T)
        {
        
            PostOrderTraverse(T->lchild);
            PostOrderTraverse(T->rchild);
            cout<<T->data;
        }
    }
    
    //4、输出二叉树的结点个数
    int NodeCount(BiThrTree T)
    {
        
        if(T == NULL)
            return 0;
        else
            return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
    }
    
    //5、输出二叉树叶子结点的个数
    void LeavesCount(BiThrTree T)
    {
        
        if(T)
        {
        
            if(!T->lchild && !T->rchild)
                cnt++;
            LeavesCount (T->lchild);
            LeavesCount (T->rchild);
        }
    }
    
    // 中序遍历进行二叉树线索化
    void InThreading(BiThrTree p,BiThrTree &pre)
    {
        
        if (p)
        {
        
            InThreading(p->lchild,pre);//左子树线索化
            if (!p->lchild)
            {
        
                p->LTag = 1;
                p->lchild = pre;//前驱线索
            }
            if ((!pre->rchild)&&pre->rchild==NULL)
            {
        
                pre->RTag = 1;
                pre->rchild = p;//后继线索
            }
            pre = p;
            InThreading(p->rchild, pre);//右子树线索化
        }
    }
    
    //中序遍历并线索化二叉树T，Thrt指向头结点
    int InOrderThreading(BiThrTree &Thrt, BiThrTree T)
    {
        
        Thrt = new BiThrNode;
        Thrt->LTag = 0;
        Thrt->RTag = 1;
        Thrt->rchild = Thrt;//右指针回指
        BiThrTree pre;
        if (!T)
            Thrt->lchild = Thrt;//若二叉树为空，则左指针回指
        else
        {
        
            Thrt->lchild = T;
            pre = Thrt;
            InThreading(T,pre);//中序遍历进行中序线索化
            pre->rchild = Thrt;//最后一个结点线索化
            pre->RTag = 1;
            Thrt->rchild = pre;
        }
        return 1;
    }
    
    
    // T指向头结点，头结点的lchild指向根节点，中序遍历线索二叉树
    int InOrderTraverse_Thr(BiThrTree T)
    {
        
        BiThrTree p = T->lchild;
        while (p&&(p != T))
        {
        
            while (p->LTag == 0)
            {
        
                p = p->lchild;
            }
            cout<<p->data;
            while (p->RTag == 1 && p->rchild != T)
            {
        
                p = p->rchild;
                cout<<p->data;
            }
            p = p->rchild;
        }
        return 1;
    }
    
    
    
    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 << " 操作7：中序线索化二叉树" << '\n';
        cout << " 操作8：中序遍历线索二叉树并输出的遍历序列；" << '\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;
                }
                case 7:
                {
        
                    InOrderThreading(Thrt, T);
                    cout << "二叉树线索化完毕！" <<'\n';
                    break;
                }
                case 8:
                {
        
                    cout << "按中序遍历输出线索二叉树：";
                    InOrderTraverse_Thr(Thrt);
                    cout << '\n';
                    break;
                }
            }
        }
        return 0;
    }

## 四、实验结果 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center] ##

## 五、实验讨论 ##

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/6d0f9517fddf4f9c82fde6d530c69ef6.png