数据结构 第8节 树

一、树定义

---

1. 专业定义
  1. 有且只有一个称谓根的节点
  2. 有若干个互不想交的子树，这些子树本身也是一棵树

2. 通俗定义
  1. 树是由节点和边（指针域）组成。
  2. 每个节点只有一个父节点，但可以有多个子节点
  3. 但有一个节点例外，没有父节点，该节点是根节点

3. 专业术语

1. 节点
2. 父节点
3. 子节点
4. 祖先节点
5. 子孙
6. 堂兄弟
7. 深度：树中节点的最大层次。从根节点到最底层节点的层数称之为深度。根节点是第一层。
8. 叶子节点：没有子节点的节点
9. 非终端节点：非叶子节点
10. 度：子节点的个数。含有最大子节点个数的度数即整棵树的度数。

二、树的分类

---

1. 一般树

任意一个节点的子节点的个数都不受限制

2. 二叉树
   任意一个节点的子节点个数最多都是2个，且子节点的位置不可变更。左子树和右子树顺序不可互换，说明二叉树是有序树。（一般树无所谓，可以变也可以不变）

• 二叉树的分类
  • 一般二叉树
  • 满二叉树：
    在每一层节点数都是最大的。
    在不增加树的层数的前提下无法再多添加一个节点的二叉树
    满二叉树是一般不太用，学它是为了引申出完全二叉树
  • 完全二叉树
    如果只是删除了满二叉树最底层最右边连续若干个节点，这样形成的二叉树就是完全二叉树，满二叉树是完全二叉树的一个特例，就是一个叶子节点都不删。
    用数组存储的二叉树必须是完全二叉树

3. 深林
   n个不相交的树的集合。

4. B+树

5. 红黑树

三、树的存储

---

1. 树存储的由来思考

  线性结构的存储顺序是确定的，树的结构并非线性结构，存储顺序不是确定的。那么你以什么方式（顺序）存储就需要有规则，才好在读取时按原来存储的顺序规则解读出来。

eg：

1. 先存根节点 & 叶子节点？
2. 先存左子节点 & 右子节点？
3. 从下往上存 & 从上往下存？

根据以上疑问，人类创造出了如下三个规则：

1. 先序遍历
2. 中序遍历
3. 后续遍历

利用这三个规则，都可以将非线性结构的树转化为线性结构。

 无论以这三种哪种方式转化成的线性结构，在数组方式存储下（连续存储），如果只存储，你都无法反推其原始树，无法还原。所以不能只存储器有效节点，还要存储补全的无效节点。

有效节点是红色节点，蓝色节点都是补全成完全二叉树而添加的无效数据节点，只起占位作用，存储时也需要存储起来，否则无法反推还原。垃圾节点也需要存。

2. 完全二叉树的优缺点

缺点：

以完全二叉树存储，保存了大量垃圾节点，耗费内存

优点：

1. 知道总节点个数，能立马推断出其层级数
2. 已知任意一个节点（编号），可以立马知道其父节点、子节点、有没有子节点
3. ：以数组的方式存储。
   其它方式存储的都不能（立马）找到其父子节点
   （得需要遍历寻找才能找到，耗时）

3. 二叉树的存储

 如果一般的二叉树要想以的形式存储的话，必须先转化为完全二叉树。
 数组是线性结构，二叉树是非线性结构，如果想用线性结构存储非线性结构的数据，你得告诉我个规则，要不然我咋知道先存哪个后存哪个！（先序、后序、中序）

存储简单，不浪费内存，指针域执行子节点、父节点

4. 一般树的存储

双亲表示法
孩子表示法
双亲孩子表示法

双亲表示法，求父节点方便，求子节点不方便 孩子表示法 双亲孩子表示法

双亲孩子表示法的总结

  数据以C结构体或Java类的形式存储在数组里，父节点域中存储的是父节点在数组中的下标，子节点不能像父节点那样用下标存储，因为子节点可能有一个、多个或没有，用数组的话只能保存一个，搞不定。所以只能用链表，一个一个往后列（HashMap 的影子）

5. 二叉树表示法

双亲孩子表示法虽然好，但是操作不方便，一般还是用二叉树表示法。

如何把一个普通树转化为二叉树❓

1. 左指针域指向它的第一个孩子
2. 右指针域指向下一个兄弟节点
3. 只要能满足此条件，就可以把一个普通树转化为二叉树。

普通树转化为二叉树

普通树转化成的二叉树一定没有右子树。
当你看到一个二叉树的时候，它可能并不是二叉树，有可能就是一个普通树转化的结果。

6. 森林的存储

不直接存储森林，先转化为二叉树，再存储二叉树。
将各个树之间当做兄弟，然后转化步骤参考普通树转化二叉树

森林转化二叉树

四、二叉树的操作

---

1. 先序遍历（先访问根节点【以及中间的父节点】）

先访问根节点
再先序访问左子树
再先序访问右子树

先序遍历demo_01 先序遍历demo_02 先序遍历demo_03

2. 中序遍历（根节点【以及中间的父节点】放中间访问）

（1）中序遍历左子树
（2）访问根节点
（3）再中序遍历右子树

中序遍历_demo01 中序遍历_demo02

3. 后序遍历

后序遍历左子树，
后序遍历右子树
最后访问根节点

后序遍历_demo01 后序遍历_demo02

4. 已知2种遍历序列推算出原始二叉树

（1）根据先序序列的第一个节点确定根节点
（2）在中序序列中，根节点左侧的是其做子树的所有节点，根节点右侧的是其右子树的所有节点
（3）中序序列中的 根节点左边的节点为根节点的左子树的所有节点，左子树所有节点在先序序列中第一个出现的节点，即：根节点左子树的根节点，左子树的子树依此类推。
（4）中序序列中的 根节点右边的节点为根节点的右子树的所有节点，右子树所有节点在先序序列中第一个出现的节点，右子树的子树依此类推。

已知先序和中序求后序实例_demo01 已知先序和中序求后序实例_demo02

（1）先根据后序得知最后一个节点是根节点
（2）再在中序序列中，根节点左边的节点 是其左子树，根节点右侧的是其右子树
（3）中序序列的根节点的左子树中的所有节点，在后序序列中排在最后的节点，即：左子树的根节点，左子树的子树依此类推。
（4）中序序列的根节点的右子树中的所有节点，在后序序列中排在最后的节点，即：右子树的根节点，右子树的子树依此类推。

已知中序和后序,求先序demo

：已知先序和后序无法推算出原始二叉树

五、应用

---

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

六、程序：静态创建二叉树、二叉树遍历

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

typedef struct BTreeNode {
    char data;                       //数据域
    struct BTreeNode * pLChild;  //左侧子节点指针
    struct BTreeNode * pRChild; //右侧子节点指针
} BTREE_NODE, * PBTREE_NODE;

/** 静态创建二叉树 */
struct BTreeNode * createBTree(){
    //创建根节点
    struct BTreeNode * pA = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
    struct BTreeNode * pB = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
    struct BTreeNode * pC = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
    struct BTreeNode * pD = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
    struct BTreeNode * pE = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));

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

/** 先序遍历 */
void preOrderShow(struct BTreeNode * pT) {
    if(NULL != pT) {
        printf("%c ", pT->data);
        if(NULL != pT->pLChild)
            preOrderShow(pT->pLChild);
        if(NULL != pT->pRChild)
            preOrderShow(pT->pRChild);
    }
}

/** 中序遍历 */
void middleOrderShow(struct BTreeNode * pT) {
    if(NULL != pT) {
        if(NULL != pT->pLChild)
            middleOrderShow(pT->pLChild);
        printf("%c ", pT->data);
        if(NULL != pT->pRChild)
            middleOrderShow(pT->pRChild);
    }
}


/** 后序遍历 */
void postOrderShow(struct BTreeNode * pT) {
    if(NULL != pT) {
        if(NULL != pT->pLChild)
            postOrderShow(pT->pLChild);
        if(NULL != pT->pRChild)
            postOrderShow(pT->pRChild);
        printf("%c ", pT->data);
    }
}

int main(void) 
{
    struct BTreeNode * pT = createBTree();
    preOrderShow(pT);
    printf("\n");
    middleOrderShow(pT);
    printf("\n");
    postOrderShow(pT);
    printf("\n");
    return 0;
}