二叉树的建立及其递归遍历（C语言实现)

红太狼 2022-05-22 11:20 162阅读 0赞

##### 最近在学习数据结构中树的概念，迟迟不得入门，应该是自己的懒惰和没有勤加练习导致的，以后应该多加练习 #####

以下是我对二叉树的一些总结内容  
二叉树的特点有：

*  每一个节点最多有两棵子树，所以二叉树中不存在度大于2的节点，注意，是最多有两棵，没有也是可以的  
    左子树和右子树是有顺序的，次序不能颠倒，这点可以在哈夫曼编码中体现， 顺序不同编码方式不同

\-即使树中某个节点中只有一个子树的花，也要区分它是左子树还是右子树  
二叉树一般有五种形态  
1.空二叉树  
2.只有一个根节点  
3.根结点只有左子树  
4.根节点只有右子树  
![这里写图片描述][70]![这里写图片描述][70 1]

二叉树的性质  
1：在二叉树的第i层上最多有2^(i-1)个节点  
2：深度为K的二叉树之多有2^(k-1)个节点

#### 注：这里的深度K意思就是有K层的二叉树 ####

3：对于任何一棵二叉树T，如果其终端节点有No个，度为2的节点数有N2，则No=N2+1  
4: 具有n个节点的完全二叉树的深度为\[log2n\]+1(\[x\]表示不大于x的最大整数）

#### 1，二叉树的存储结构（二叉链表） ####

//二叉树的存储结构，一个数据域，2个指针域
     typedef struct BiTNode
    {
         char data;
         struct BiTNode *lchild,*rchild;
      }BiTNode,*BiTree;

####  2，首先要建立一个二叉树，建立二叉树必须要了解二叉树的遍历方法。，我在这里展示的是二叉树的递归建立方式 ####

//我在这里实现的是，二叉树的前序遍历方式创建，如果要使用中序或者后序的方式建立二叉树，只需将生成结点和构造左右子树的顺序改变即可
     void CreateBiTree(BiTree *T)
      {
        
          char ch;
          scanf("%c",&ch);
          if(ch=='#')
              *T=NULL;
          else
         {
        
             *T=(BiTree  )malloc(sizeof(BiTNode));
             if(!*T)
                 exit(-1);
              (*T)->data=ch;
              CreateBiTree(&(*T)->lchild);
             CreateBiTree(&(*T)->rchild);
          }
     }

![这里写图片描述][70 2]  
3。二叉树的遍历方式（递归建立）

void PreOrderTraverse(BiTree T)//二叉树的先序遍历
    {
        
        if(T==NULL)
            return ;
        printf("%c ",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    void InOrderTraverse(BiTree T)//二叉树的中序遍历
    {
        
       if(T==NULL)
           return ;
       InOrderTraverse(T->lchild);
        printf("%c ",T->data);
       InOrderTraverse(T->rchild);
    }
    void PostOrderTraverse(BiTree T)//后序遍历
    {
        
        if(T==NULL)
            return;
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c ",T->data);
    }

4.完整代码

#include<stdio.h>
    #include<stdlib.h>
    typedef struct BiTNode
    {
        
        char data;
        struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    void PreOrderTraverse(BiTree T)//二叉树的先序遍历
    {
        
        if(T==NULL)
            return ;
        printf("%c ",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    void InOrderTraverse(BiTree T)//二叉树的中序遍历
    {
        
       if(T==NULL)
           return ;
       InOrderTraverse(T->lchild);
        printf("%c ",T->data);
       InOrderTraverse(T->rchild);
    }
    void PostOrderTraverse(BiTree T)//后序遍历
    {
        
        if(T==NULL)
            return;
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c ",T->data);
    }
    void CreateBiTree(BiTree *T)
    {
        
        char ch;
        scanf("%c",&ch);
        if(ch=='#')
            *T=NULL;
        else
        {
        
            *T=(BiTree  )malloc(sizeof(BiTNode));
            if(!*T)
                exit(-1);
            (*T)->data=ch;
            CreateBiTree(&(*T)->lchild);
            CreateBiTree(&(*T)->rchild);
        }
    }
    int main()
    {
        
        BiTree T;
        CreateBiTree(&T);
        PreOrderTraverse (T);
        InOrderTraverse(T);
        PostOrderTraverse(T);
        return 0;
    }

对知识点的补充：  
（1）建立二叉树时，这里是以前序遍历的方式，输入的是扩展二叉树，也就是要告诉计算机什么是叶结点，否则将一直递归，当输入“\#”时，指针指向NULL，说明是叶结点。

如图为扩展二叉树：（前序遍历为：ABDG\#\#H\#\#\#CE\#I\#\#F\#\#）  
![这里写图片描述][70 3]

[70]: https://img-blog.csdn.net/20180622224218896?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: /images/20220522/6863fccbb89240a0850ddd0b16a312d9.png
[70 2]: /images/20220522/efd6fc465f7f436299e190adc58b8f14.png
[70 3]: /images/20220522/2d8aa2cbf0db48dc81c897ca28a4a56f.png