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

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

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

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

-即使树中某个节点中只有一个子树的花，也要区分它是左子树还是右子树
二叉树一般有五种形态
1.空二叉树
2.只有一个根节点
3.根结点只有左子树
4.根节点只有右子树

二叉树的性质
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;

1
2
3
4
5
6
7

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);
      }
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

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

如图为扩展二叉树：（前序遍历为：ABDG##H###CE#I##F##）