第七章二叉树

满二叉树：所有度为0的节点位于同一层，其他所有节点的度都为2

完全二叉树：最后一层的节点均靠左，除去最后一层为满二叉树

性质1：

一棵非空二叉树的第i层上最多有$2^{i-1}$个节点

性质2：

深度为h的二叉树最多有$2^h-1$个节点

性质3：

对于任何一棵二叉树T，如果度为0的节点数为n0，度为2的节点数为n2，那么

$$ n0=n2+1 $$

假设一颗二叉树的总的节点个数为n，度为1的节点个数为n1，

可知

$$ n=n0+n1+n2 $$

又可知节点的度代表了这个节点下面有几个节点，那么所有节点的度加起来，就是除了根节点之外所有节点的个数了，用这个来表示总的节点个数为：

$$ n = 0n0+1n1+2n2+1=n1+2n2+1 $$

可知 $$ n = n0+n1+n2=n1+2*n2+1 $$

所以 $$ n0 = n2+1 $$

性质4

对于具有n个节点的完全二叉树，如果按照从上到下，从左至右的方法对所有节点从1开始顺序编号，对于序号为i的节点有：

如果i>1，那么其父节点为i/2

如果其左孩子存在，那么序号为2i，如果其右孩子存在则序号为2*i+1

7.6 穿线二叉树

对于一个具有n个节点的二叉树，可知一共会存2*n个指针，但是，只用了其中的n-1个，剩下的n+1个指针都是空指针。

在实际应用中我们可以根据需要利用这些空指针做一个穿线二叉树，即线索二叉树

做法为将原来空的左孩子指针指向父节点，将原来空的右孩子指针指向先序遍历（中序，后序）下的后继节点。

产生的穿线二叉树分别叫做前序穿线二叉树中序穿线二叉树后序穿线二叉树

为了区分指针指向的是左右孩子，还是父节点和后继节点，需要额外在每个节点增加两个标记位，分别标记。

省不了内存，但是可以允许你从某一个节点往前找，或往后找。但感觉也没有太大优势。

树转二叉树

1 在所有兄弟节点之间添加一条线

2 对于每个节点，保留第一个孩子的连线，删除其他孩子的连线

二叉树到树

将一个节点的左孩子的右孩子，及其右孩子的右孩子，等等全部连接到该节点，去除之前的连接