@[toc]

1.树

树的基本概念

结点的度：指该结点的分支个数，如结点A的度为2
树的度：指树中最大的结点度数，如该树的度为3
祖先和子孙：对于某结点来说，从根到该结点所经的所有结点称为该结点的祖先。反之，以某结点为根的所有子树上的结点称为该结点的子孙。如路径ABEH，ABE是H的祖先，BEH是A的子孙。

2.二叉树

2.1 二叉树的基本概念

复习概念：m叉树 度≤m的树
等比数列求和公式：S~n~=a~1~(1-q^n^)/(1-q)
树节点的度数即为该节点孩子的个数。

二叉树是度小于等于2的有序树。(左右子树顺序不能颠倒）

性质:

• 对任意一棵二叉树，如果用n~0~表示叶子结点的数量，用n~2~表示度为2的结点的数量，则有n~0~=n~2~+1
• 非空二叉树第k层最多有2^k-1^个结点
• 深度为h的二叉树最多有2^h^-1个结点

推导
假设树中结点总数为n，则
n=n~0~+n~1~+n~2~ (二叉树结点总数=度为0的结点数+度为1的结点数+度为2的结点数）
n=n~1~+2n~2~+1(树的结点总数=总度数+1）总度数=n*度为n结点数之和（二叉树是0-2）
上面两个方程作差即得到n~0~=n~2~+1

二叉树的五种状态:

2.2 满二叉树

顾名思义：每一个非叶子结点的结点的度都是2
一棵高度为h，且含有2^h^-1个结点的树

推导：2^0^+2^1^+.....2^n^=1(1-2^n^)(1-2)=2^n^-1

特点：
:one:只有最后一层有叶子结点
:two:不存在度为1度结点
:three:按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1，结点i的父结点为⌊i/2⌋

2.3 完全二叉树

完全二叉树是指从左到右从上到下依次补满全部结点的树，停止于任意位置，序号一一对应。
结论：满二叉树是一种特殊的完全二叉树

特点：

• 若完全二叉树的深度为h，则它的前h-1层全是满的
• 只有最后两层可能有叶子结点，且最底层的叶子结点依次排列在最左边。
• 最多只有一个度为1的点
• 有n个结点的完全二叉树的深度⌊ log~2~n⌋+1⌈ log~2~n+1⌉

  推导&解释
  使用这两个公式都可以通过结点数计算出完全二叉树的高度
  推导过程：⌈log~2~(n+1)⌉
  上取整通过≤最大值证明出
  结点n最大为2^h^-1，必然也肯定大于下一高度的最大值2^h-1^-1
  2^h-1^-1<n≤2^h^-1
  中间值+1后，取log2，并且上取整，满足该条件
  ⌈log~2~(n+1)⌉

推导过程:⌊log~2~n⌋+1
上取整通过≥最小值证明出
结点n最少的可能就是上一层满了，下一层一个，即2^h-1^-1+1=2^h-1^,肯定小于结点最大值+1
2^h-1^≤n<2^h^
取log2，下取整，再+1，即证毕，⌊log~2~n⌋+1

• 对于完全二叉树，由结点数就可以推出各个度的结点数的个数。（n~0~,n~1~,n~2~）

  推导：记忆是困难的，通过推导辅助记忆
  (1) 完全二叉树最多只有一个度为1度结点（完全二叉树的性质）推出 完全二叉树度为1度结点要么是0，要么是1.
  (2)n~0~=n~2~+1推出n~0~+n~2~=n~2~+1+n~2~=2n~2~+1推出一定是奇数
  最终推，若完全二叉树有2k个结点（偶数）个结点，即n~0~+n~1~+n~2~=偶数，n~0~+n~2~=奇数，所以n~1~=1,n~0~=k,n~2~=k-1.若是奇数个结点（2k-1）个结点，n~1~=0,n~0~和n~2~同偶数，写法是不变的

2.4 二叉排序树

左子树结点值<根节点值<右子树结点值

2.5 平衡二叉树

平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1

3.二叉树的存储结构

3.1 二叉树的顺序存储

用一组连续存储单元自上而下，自左到右存储树上的结点元素。比较适合完全二叉树和满二叉树。对于一般的二叉树，需添加一些不存在的空结点。

#define MaxSize 100
struct TreeNode{
   
   
ElemType value； //结点中的数据元素
bool isempty；   //结点是否为空，当所存储的二叉树不是完全二叉树的时候使用这个。
}
TreeNode t[MaxSize];

如果是非完全二叉树，那么为了找到他的左孩子，右孩子，父结点，我们仍要按照完全二叉树的存储结构让序号对应起来，唯一不同的点是，我们无法根据序号，判定是否存在左孩子还是右孩子了，所以我们使用bool类型isempty，来实现判断

3.2 二叉树的链式存储

typedef struct BiTNode{
   
   
    ElemType data;
    struct BiTNode *lchild,*rchild; //左孩子指针,右孩子指针
}BiTNode,*BiTree;

在二叉链表中，链表的头指针T指向根节点。T->data表示根结点的值

n个结点的二叉链表共有n+1个空链域

每个结点都有2个指针(链域),一共有2n个链域,但是使用的链域是结点数-1,即n-1,所以2n-n+1=n+1,有n+1个空链域,这些空链域用来构造线索二叉树

但是如果想找到指定结点的父节点,只能从根开始遍历寻找,
改进方法是加上一个父节点指针,struct BiTNode *parent; 父节点指针,改进之后的链表就是三叉链表