数据结构——实验三二叉树的遍历

ゝ一世哀愁。 2023-06-18 10:53 47阅读 0赞

**一、【实验目的】**

1、 了解二叉树的前序、中序、后序和层次序列排列；

2、 将C语言同二叉树的数据结构联系起来；

3、 掌握生成的二叉树的链表结构；

4、 掌握如何按层次输出二叉树的所有结点；

5、 掌握如何将动态二叉树转换为静态二叉链表。

**二、【实验内容】**

创建一个二叉树，对这棵动态二叉树进行分析，将其用静态二叉链表表示。二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。lchild和rdhild分别用于存储左右孩子的下标。

**三、【实验步骤与要求】**

1、实验前的准备

（1）了解二叉树的基本概念；

（2）了解二叉树的基本结构。

2、上机操作

（1）了解二叉树的前序、中序、后序和层次排列；

（2）将C语言同二叉树的数据结构联系起来；

（3）掌握生成的二叉树的链表结构；

（4）掌握如何按层次输出二叉树的所有结点；

（5）掌握如何将动态二叉树转换为静态二叉链表。

**实验要求：**

复习课本6.3节（p128~p135）和p32静态链表示例；

建树和遍历得采用前序、中序、后序和层次遍历中的2种；

转换成静态二叉链表时的输出格式为：data下标、data、左孩子下标、右孩子下标；

实验报告上需画出实验所用的二叉树以及各节点下标。

**四、实验代码**

///创建一个二叉树，对这棵动态二叉树进行分析，将其用静态二叉链表表示。
    ///二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。
    ///静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，
    ///也有三个字段：data，lchild，rchild。lchild和rdhild分别用于存储左右孩子的下标。
    ///建树和遍历得采用前序、中序、后序和层次遍历中的2种
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX 9
    using namespace std;
    typedef struct node///结点结构
    {
        char data;///数据域
        struct node *lchild;///左孩子指针
        struct node *rchild;///右孩子指针
    }BiTNode,*BiTree;///树中结点类型
    typedef struct BiTNode_s///树结构
    {
        char data;
        int lchild;///左孩子下标
        int rchild;///右孩子下标
    }BiTNode_s,*BiTree_s;
    int i=1;
    
    ///前序法构建二叉树
    void PreCreatBiTree(BiTree&T)
    {
        ///按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
        char ch;///结点的值
        if((ch=getchar())=='*')///用*表示空
            T=NULL;///递归结束，建空树
        else
        {
            T=(BiTNode *)malloc(sizeof(BiTNode));///开辟新的空间
            T->data=ch;///生成根结点赋值
            PreCreatBiTree(T->lchild);///递归创建左子树
            PreCreatBiTree(T->rchild);///递归创建右子树
        }
    }
    
    
    ///前序遍历，中左右
    void PreTravel(BiTree &T)
    {
        if(T)
        {
            printf("%c ",T->data);///中
            PreTravel(T->lchild);///先左子树
            PreTravel(T->rchild);///后右子树
        }
    }
    ///中序遍历，左中右
    void MidTravel(BiTree&T)
    {
        if(T)
        {
            MidTravel(T->lchild);
            printf("%c ",T->data);
            MidTravel(T->rchild);
        }
    }
    ///后序遍历，左右中
    void AftTravel(BiTree &T)
    {
        if(T)
        {
            AftTravel(T->lchild);
            AftTravel(T->rchild);
            printf("%c ",T->data);
        }
    }
    
    ///将动态二叉树转化为用静态二叉链表
    void TreeToArray(BiTree &T,BiTNode_s a[])
    {
        int k;
        a[i].data=T->data;
        k=i;///k用于记录递归调用的每一层此结点对应的数组下标,i在外面就被初始化为1
        if(T->lchild)
        {
            i++;
            a[k].lchild=i;///将左孩子结点对应的下标赋给双亲结点
            TreeToArray(T->lchild,a);///递归调用Tree_to_Array函数
        }
        else
            a[k].lchild=0;///没有左孩子结点
        if(T->rchild)
        {
            i++;
            a[k].rchild=i;///将右孩子结点对应的下标赋给双亲结点的rcjild
            TreeToArray(T->rchild,a);///递归调用Tree_to_Array函数
        }
        else
            a[k].rchild=0;///没有右孩子结点
    }
    
    int main()
    {
        int j;
        BiTree T;
        BiTNode_s a[MAX];
        printf("请按先序遍历顺序输入二叉树的各节点，没有的用符号*代替：\n");
        PreCreatBiTree(T);
        printf("前序遍历结果：\n");
        PreTravel(T);
        printf("\n");
        printf("中序遍历结果：\n");
        MidTravel(T);
        printf("\n");
        printf("后序遍历结果：\n");
        AftTravel(T);
        printf("\n");
        TreeToArray(T,a);
        printf("转化成静态二叉链表为：\n");
        for(j=1;j<MAX;j++)
            printf("%d %c %d %d\n",j,a[j].data,a[j].lchild,a[j].rchild);
    
        return 0;
    }
    
    ///ABCD***E**FG*H***

六、实验结果截图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2NTU5Nw_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2NTU5Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019120123120815.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2NTU5Nw==,size_16,color_FFFFFF,t_70