数据结构—二叉树的建立与三种遍历方法

落日映苍穹つ 2022-05-16 03:29 108阅读 0赞

## 数据结构—二叉树的建立与三种遍历方法 ##

##### 在知道了树这样的数据结构之后，我们知道其实有很多种方法可以表示树的结构，比如双亲表示法，孩子表示法，兄弟表示法等等。但是对于我们平时最常用的数据结构——二叉树，我们该如何在计算机上建立其数据结构呢? #####

### 1.二叉树的建立 ###

看下面的这幅图片，我们现在要建立这样一个二叉树，我们的思路大致是这样:

![image.png][]

*  从根节点开始建立，然后先从左节点开始，把它也当成一个根节点，建立它的左右节点，以此类推，直到数据填好之后，再返回到开始时根节点的右孩子节点开始建立其孩子节点。

很明显，上述的过程需要用到**递归**操作，除此之外，我们如何判断某个节点是否有孩子节点呢?我这里规定：若输入节点内的数据为 -1 则表示该节点为空

也就是说，我们在操作时，其实是这样的

![image.png][image.png 1]

下面我们来看其实现代码

typedef struct BiTNode  //节点结构:该节点数据与指向两孩子节点的指针 
    {
        int data;
        BiTNode *lchild,*rchild;
    }*BiTree;
    
    /**
        二叉树的建立 ，输入-1即表示该节点没有数据 
    */
    BiTree CreateBiTree(BiTree T,int step)
    {
        int num;
        printf("请输入第%d层的数据:",++step);
        scanf("%d",&num); 
        if(num == -1)
        {
            T = NULL;
        }
        else
        {
            T = (BiTree)malloc(sizeof(BiTNode));
            T->data = num;
            T->lchild = CreateBiTree(T->lchild,step);   //递归对建立左孩子二叉树 
            T->rchild = CreateBiTree(T->rchild,step);   //递归对建立右孩子二叉树
        }
        return T;
    }

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

### 2.二叉树的遍历 ###

> 二叉树的遍历(Traversing binary tree)是指从根节点出发,按照某种次序依次访问二叉树中的所有节点，是的每个节点被访问一次且仅被访问一次

*  二叉树的遍历不同于线性结构,最多也就是从头至尾，循环，双向等简单的遍历方式。树的节点之间不存在唯一的先驱和后继关系，在访问一个节点后，下一个被访问的节点面临着不同的选择，选择的方式不同，遍历的次序就完全不同了。

#### 1>.前序遍历 ####

规则:若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树

*  代码:

/**
        二叉树的前序遍历 
    */ 
    void PreOrderTraverse(BiTree T)
    {
        if(T == NULL)
            return;
        printf("%d  ",T->data); //先输出，再递归遍历左右孩子 
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }

![image.png][image.png 2]

遍历结果: 6，7，9，20，19，18

#### 2>.中序遍历 ####

规则:若树为空,则空操作返回，否则从根节点开始(注意并不是先访问根节点),中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树

*  代码:

/**
        二叉树的中序遍历 
    */ 
    void InOrderTraverse(BiTree T)
    {
        if(T == NULL)
            return;
        InOrderTraverse(T->lchild);
        printf("%d  ",T->data); //先递归遍历左孩子，再输出，再递归遍历右孩子 
        InOrderTraverse(T->rchild);
    }

![image.png][image.png 3]

遍历结果: 7，9，6，19，20，18

#### 3>.后序遍历 ####

规则:若树为空，则空操作返回，否则从左到右先也贼厚街店的方式遍历左右子树，最后是访问根节点

*  代码:

/**
        二叉树的后序遍历 
    */ 
    void PostOrderTraverse(BiTree T)
    {
        if(T == NULL)
            return;
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%d  ",T->data); //先递归左右孩子，再输出 
    }

![image.png][image.png 4]

遍历结果: 9，7，19，18，20，6

其实还有一种遍历方法叫做层序遍历:即从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对节点逐个访问。像这样:

![image.png][image.png 5]

因为其实现需要借助队列的数据结构，所以我们这里先不写代码了，以后再补充。

##### 要深刻理解二叉树的前，中，后序遍历，就必须认真模拟一次次递归的过程，多去自己画一画，就能掌握了 #####

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

### 3.完整代码及运行结果验证 ###

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct BiTNode  //节点结构:该节点数据与指向两孩子节点的指针 
    {
        int data;
        BiTNode *lchild,*rchild;
    }*BiTree;
    
    /**
        二叉树的建立 ，输入-1即表示该节点没有数据 
    */
    BiTree CreateBiTree(BiTree T,int step)
    {
        int num;
        printf("请输入第%d层的数据:",++step);
        scanf("%d",&num); 
        if(num == -1)
        {
            T = NULL;
        }
        else
        {
            T = (BiTree)malloc(sizeof(BiTNode));
            T->data = num;
            T->lchild = CreateBiTree(T->lchild,step);   //递归对建立左孩子二叉树 
            T->rchild = CreateBiTree(T->rchild,step);   //递归对建立右孩子二叉树
        }
        return T;
    }
    
    /**
        二叉树的前序遍历 
    */ 
    void PreOrderTraverse(BiTree T)
    {
        if(T == NULL)
            return;
        printf("%d  ",T->data); //先输出，再递归遍历左右孩子 
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    
    /**
        二叉树的中序遍历 
    */ 
    void InOrderTraverse(BiTree T)
    {
        if(T == NULL)
            return;
        InOrderTraverse(T->lchild);
        printf("%d  ",T->data); //先递归遍历左孩子，再输出，再递归遍历右孩子 
        InOrderTraverse(T->rchild);
    }
    
    /**
        二叉树的后序遍历 
    */ 
    void PostOrderTraverse(BiTree T)
    {
        if(T == NULL)
            return;
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%d  ",T->data); //先递归左右孩子，再输出 
    }
    
    
    int main()
    {
        BiTree T;
        int step;
        T = CreateBiTree(T,0);
        printf("前序遍历:"); 
        PreOrderTraverse(T);
        printf("\n");
    
        printf("中序遍历:"); 
        InOrderTraverse(T);
        printf("\n");
    
        printf("后序遍历:"); 
        PostOrderTraverse(T);
        printf("\n");
    
        return 0;
    }

![image.png][image.png 6]

[image.png]: /images/20220516/3deb26e050c7472e88383fbb34562f2c.png
[image.png 1]: /images/20220516/84827d12bc724270b6d475c5f4667f36.png
[image.png 2]: /images/20220516/f1e55fd50aa4483a99f0ed7a21128a24.png
[image.png 3]: /images/20220516/1d6cdaee04034ef38516a07370d6cc28.png
[image.png 4]: /images/20220516/ae7de61ee0d649cab4c10009cd3e874f.png
[image.png 5]: /images/20220516/f9bc2862a9c4476db7031a3c77a53e85.png
[image.png 6]: /images/20220516/701e91436b214016afe30e0eeb64e0ee.png