1.树的基本概念

1. 根节点：有且仅有一个
2. 分支节点：有后继的节点
3. 叶子节点：没有后继的节点
4. 除根节点外，所有节点有且仅有一个前驱（与图相对）
5. 子树：除根节点外，可以分为m个互不相交的集合（例：BEFKL、CG、DHIJM）
6. 祖先节点：根A到结点K的从上往下的唯一路径上的任意结点，例：B是K的祖先结点
7. 子孙结点：根A到结点K的从上往下的唯一路径上的任意结点，例：K是B的子孙结点
8. 双亲结点（父结点）：某结点的前驱。例：E是K的双亲结点，B是F的双亲结点
9. 孩子结点：某结点的后继。例：K是E的孩子结点，F是B的孩子结点
10. 兄弟结点：同一层上的结点。例如：E是F的兄弟结点，K是L的兄弟结点
11. 路径：两个结点之间所经过的结点序列（单向，且由上往下，B到L有路径，而B到D没路径）
12. 路径长度：路径上所经过的边的个数
13. 结点的层次：由上往下，A是1层，B是2层，E是3层，K是4层
14. 结点的高度：由下往上，K是1层，E是2层，B是3层，A是4层。特别地，F也是2层
15. 树的高度：根节点的高度，即总共多少层
16. 结点的度：有几个孩子结点。E的度为2，K的度为0，A的度为3。特别地，度为0时，结点为叶子结点；度＞0时，结点为分支结点
17. 树的度：各个结点中度数最大的值
18. 森林：n棵互不相交的树的集合，森林和树可以相互转换（添加根节点）

2.树的性质

1. 结点数 = 总度数 + 1（除根节点外，每个结点都有一条边指向其前驱）
2. 度为m的树和m叉树

1. 相同点：允许结点的度 ≤ m

         b.不同点：m叉树的结点度数可以都＜m，但是度为m的树至少有一个节点的度 = m；m叉树可以为空树，度为m的树至少有m + 1个结点（根节点 + m个叶子节点）

3.度为m的树第 i 层至多有 个结点（最多情况下：第一层为根节点，结点数1，即 ；第二层为m个结点，即 ，第二层为 以此类推）

4.高度为h的m叉树至多又 个结点（等比数列求和）

5.高度为h的m叉树最少有h个结点；高度为h的度为m的树最少有 h + m - 1 个结点（设最后一个结点为 m，高度为 h，m + h - 1，- 1 为减去最后一个结点的高度）

3.二叉树

3.1.二叉树

3.1.1.二叉树的基本概念

1. 二叉树由根节点和左右子树构成
2. 每个结点至多有两个子树（注意区别度为2的树）
3. 有序树（左右子树不能颠倒）
4. 可以是个空树

3.1.2.二叉树的性质

设二叉树中度为0、度为1、度为2的结点个数分别为a、b、c，则a = c + 1

1. 设 n 为结点总个数
2. n = 0 * a + 1 * b + 2 * c + 1（结点个数 = 总度数 + 1）
3. n = a + b + c（结点个数相加得到总个数）
4. b + 2c + 1 = a + b + c → a = c + 1

3.2.满二叉树

1. 除了叶结点外，所有结点都有左右子树

2.设高度为 h，共  个结点

3.按层序编号，根节点为1，则结点 i 的左孩子为2i，右孩子为2i + 1，父结点为⌊ i / 2⌋

3.3.完全二叉树

3.3.1.完全二叉树的概念

1. 当且仅当其每个结点都与高度为 h 的二叉树中编号为1 - n 的节点一一对应
2. 只有可能有一个度为1的叶子结点（在倒数第二层）
3. 叶子结点出现在最后两层
4. 按层序编号，根节点为1，则结点 i 的左孩子为2i，右孩子为2i + 1，父结点为⌊ i / 2⌋
5. i ≤ ⌊ n / 2⌋为分支节点 i > ⌊ n / 2 ⌋为叶子结点

3.3.2.完全二叉树的性质

1. 具有 n 个结点的完全二叉树的高度 h 为⌈ ⌉ 或 ⌊ ⌋ + 1

    1. 第 h - 1 层的完全二叉树的结点个数为

   2. 第 h 层的完全二叉树的结点个数为

   3.

    4.

2.设度为0的结点个数为a，度为1的结点个数为b，度为2的结点个数为c，完全二叉树可以推出a、b和c的值

   1. 在二叉树中，a = c + 1（二叉树的性质），因此，a + c必为奇数

    2.完全二叉树中度为1的结点个数最大为1（即b = 1 或 0）

    3.设总结点个数为2k（偶数）：a + c为奇数→b = 1→a = k、c = k - 1

    4.设总结点个数为2k - 1（奇数）：a + c为奇数→b=0→a = k，c = k - 1

3.5.二叉排序树

1. 左子树的所有结点的关键字都小于根节点
2. 右子树的所有结点的关键字都大于根节点
3. 左右子树依然是二叉排序树

3.6.平衡二叉树

1. 树上任意一个结点的左右子树的深度差不超过1
2. 平衡二叉树具有更高的搜索效率

4.二叉树的存储结构

4.1.二叉树的顺序存储

#define MAXSIZE 100
typedef struct treeNode{
    elemType value;    //结点中元素的值
    bool isEmpty;    //结点是否为空
}treeNode;
//申明一个长度为MAXSIZE的结构体数组
//由上至下、从左至右的方式存放完全二叉树的各个结点数据
treeNode T[MAXSIZE];
//初始化时，把结点置空
for(int i = 0; i < MAXSIZE; i++) T[i].isEmpty = true;

1. 为了方便存储，从数组下标1开始存储数据。
2. 树的顺序存储通常只用于存储完全二叉树（普通二叉树采用顺序存储的方式跟完全二叉树一样，但是采用这种方式的代价是浪费大量存储空间）

4.2.二叉树的链式存储

typedef struct BiTNode{
    elemtype value;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//定义一个空树
BiTree root = NULL;
//插入根结点
root = (BiTNode*)malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;
//插入新结点
BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
p->data = {2}
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;    //作为根结点的左孩子

1. n个节点的二叉链表共有n + 1个空指针域

1. 总共n个节点，除了头结点，每个节点都被一个指针指着
2. 2n个指针就有n-1个指针不是空指针
3. 2n-（n-1）= n + 1

2. 普通二叉树的链式存储中，找其双亲结点只能通过从根节点重新遍历树寻找，如果经常需要找到某个结点的父亲节点，可以增加一个指针指向双亲结点（三叉链表）

typedef struct BiTNode{
    struct BiTNode *parent, *lchild, *rchild;
    elemType value;
}BiTNode, *BiTree;

5.王道课后题

1. 设度为0的结点个数为a，度为1的结点个数为b，度为c的结点个数为c
2. 当b = 1时：

      1.a = c + 1，总结点个数为 0 * a + 1 * b + 2 * c + 1 = 2a

      2.高度为 向上取整

3.当b = 0时：

1. a = c + 1，总结点个数为 0 * a + 1 * b + 2 * c + 1 = 2a - 1
2. 高度为 向上取整

1. 设度为0的结点个数为a，度为1的结点个数为b，度为c的结点个数为c，总结点个数为n
2. 度为0的结点，即叶子结点
3. 度为2的结点，即分支节点
4. a = c + 1 → c = a - 1
5. 满二叉树 → b = 0
6. n = a + b + c → n = 2a - 1 → a = (n + 1) / 2 即 叶子结点 = (n + 1) / 2
7. n = a + b + c → n = 2c + 1 → c = (n - 1) / 2 即 分支节点 = (n - 1) / 2
8. 高度 向上取整

1. 整个完全二叉树295个结点

1. 前八层的总数为255
2. 第九层的结点个数240

2. 叶子结点的个数为248个

1. 第九层为完全二叉树的最后一层，其结点都为叶子结点，即240个
2. 第八层的结点共128个，其分支节点的个数为第九层的一半，即120个，剩下的都是叶子结点，即8个

#define MAXSIZE 100
typedef struct treeNode{
    elemType value;
    bool isEmpty;
}treeNode;
treeNode T[MAXSIZE];
elemType commonParent(treeNode T, int p, int q){
    //寻找公共结点
    while (p != q){
        //谁大谁找双亲结点
        if (p > q) p /= 2;
        else q /= 2;
    }
    return T[p].value;
}