树（C语言）

一、定义

有且只有1个称为根的节点；
有若干个互不相交的子树，这些子树本身也是一棵树。

树由节点和边（指针域）组成。
每个节点只有一个父节点，但可以有多个子节点；
但有一个节点例外，该节点没有父节点，此节点称为根节点。

二、专业术语

1、节点
2、父节点
3、子节点
4、子孙
5、堂兄弟
6、深度：从根节点到最底层节点的层数。
根节点是第1层。
7、叶子节点：没有子节点的节点。
8、非终端节点/非叶子节点：有子节点的节点。
根节点既可以是叶子节点，也可以是非叶子节点。
9、节点的度：子节点的个数。
树的度：节点的度中最大的度称为树的度。

三、树的分类

一般树：任意一个节点的子节点的个数都不受限制。

二叉树：任意一个节点的子节点的个数最多2个，且子节点的位置不可更改。

二叉树的分类：

一般二叉树
满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树是满二叉树。
完全二叉树：如果只是删除了满二叉树最底层、最右边的连续若干个节点，这样形成的二叉树就是完全二叉树。

完全二叉树的优点：
查找某个节点的父节点和子节点（也包括判断有没有子节点）的速度很快；

满二叉树是完全二叉树的一个特例；完全二叉树包含满二叉树。

森林：n个互不相交的树的集合。

四、树的存储

1、二叉树的存储：

连续存储[完全二叉树]：

要以数组方式来存，必须先转化成完全二叉树才能存储。因为，只保存有效的点，而不转化的话，是无法知道以前的树是怎么构造出来的。

这样存储，耗用内存空间过大。

链式存储：相对比较简单，耗用内存空间也比较小。

2、一般树的存储

（1）双亲表示法：求父节点方便。

（2）孩子表示法：求子节点方便。

（3）双亲孩子表示法：求父节点和子节点都方便。

（4）二叉树表示法（孩子兄弟链表表示法）：一般树转化成二叉树来存储。

具体转换方法：设法保证任意一个节点的左指针域指向它的第一个孩子，右指针域指向它的下一个兄弟。
只要能满足此条件，就可以把一个普通树转化为二叉树。

一般树转化为二叉树

一般树转化成的二叉树，一定没有右子树。

3、森林的存储

森林转化成二叉树来存储。

森林转化成二叉树

五、二叉树的遍历

已知二叉树，求其先序、中序、后序序列

1、先序遍历

先访问根节点，再先序遍历左子树，再先序遍历右子树。

ABDCEFG

2、中序遍历

中序遍历左子树，再访问根节点，再中序遍历右子树。

DBAECGF

3、后序遍历

中序遍历左子树，再中序遍历右子树，再访问根节点。

DBEGFCA

4、已知两种遍历序列求原始二叉树

通过先序和中序，或者中序和后序，我们可以还原出原始的二叉树。但是，通过先序和后序是无法还原出原始的二叉树的。

只有通过先序和中序，或者中序和后序，才可以唯一地确定一个二叉树。

5、已知先序和中序，求后序

先序：ABCDEFGH
中序：BDCEAFHG
求后序？

后序序列为：DECBHGFA

6、已知中序和后序，求先序

中序：BDCEAFHG
后序：DECBHGFA
求先序？

先序：ABCDEFGH

7、链式二叉树遍历-程序

#include <stdio.h>
#include <malloc.h>

struct BTNode
{
    char data;
    struct BTNode * pLchild;
    struct BTNode * pRchild;
};

struct BTNode * CreateBTree(void);
void PreTraverseBTree(struct BTNode * pT);
void InTraverseBTree(struct BTNode * pT);
void PostTraverseBTree(struct BTNode * pT);

int main(void)
{
    struct BTNode * pT = CreateBTree(); // pT保存根节点的地址 

    printf("先序：\n");
    PreTraverseBTree(pT); // 先序遍历 
    printf("中序：\n");
    InTraverseBTree(pT); // 中序遍历
    printf("后序：\n");
    PostTraverseBTree(pT); // 后序遍历 

    return 0;
}

void PreTraverseBTree(struct BTNode * pT)
{
    if(NULL != pT)
    {
        printf("%c\n", pT->data); // 先访问根节点
        if(NULL != pT->pLchild)
        {
            PreTraverseBTree(pT->pLchild); // 先序遍历左子树。pT->pLchild 代表整个左子树 
        }
        if(NULL != pT->pRchild)
        {
            PreTraverseBTree(pT->pRchild); // 先序遍历右子树。pT->pRchild 代表整个右子树
        } 
    }
}

void InTraverseBTree(struct BTNode *pT)
{
    if(NULL != pT)
    {
        if(NULL != pT->pLchild)
        {
            InTraverseBTree(pT->pLchild); // 中序遍历左子树。pT->pLchild 代表整个左子树 
        }
    
        printf("%c\n", pT->data); // 访问根节点
    
        if(NULL != pT->pRchild)
        {
            InTraverseBTree(pT->pRchild); // 中序遍历右子树。pT->pRchild 代表整个右子树
        } 
    }
}

void PostTraverseBTree(struct BTNode *pT)
{
    if(NULL != pT)
    {
        if(NULL != pT->pLchild)
        {
            PostTraverseBTree(pT->pLchild); // 后序遍历左子树。pT->pLchild 代表整个左子树 
        }
    
        if(NULL != pT->pRchild)
        {
            PostTraverseBTree(pT->pRchild); // 后序遍历右子树。pT->pRchild 代表整个右子树
        } 
    
        printf("%c\n", pT->data); // 访问根节点
    }
}

// 静态创建一个链式二叉树 
// 返回根节点的地址 
struct BTNode * CreateBTree(void)
{
    struct BTNode * pA = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pB = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pC = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pD = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode * pE = (struct BTNode *)malloc(sizeof(struct BTNode));

    pA->data = 'A';
    pB->data = 'B';
    pC->data = 'C';
    pD->data = 'D';
    pE->data = 'E';

    pA->pLchild = pB;
    pA->pRchild = pC;
    pB->pLchild = pB->pRchild = NULL;
    pC->pLchild = pD;
    pC->pRchild = NULL;
    pD->pLchild = NULL;
    pD->pRchild = pE;
    pE->pLchild = pE->pRchild = NULL;

    return pA;
};

六、树的应用

树是数据库中数据组织的一种重要形式。
操作系统父子进程的关系本身就是一棵树。
面向对象语言中类的继承关系本身就是一棵树。
赫夫曼树。