二叉树知识
1.二叉树性质
1.1 在二叉树的第 \(i\) 层上最多有 \(2^i-1\) 个节点
1.2 深度为 \(k\) 的二叉树上最多有 \(2^{k-1}-1\) 个节点
1.3 一棵深度为 \(k\) 且有 \(2^{k-1}-1\) 个节点的二叉树称为满二叉树
如下图。
1.4 深度为 \(k\) 且有 \(n\) 个节点的二叉树，且每一个节点的编号都与满二叉树一一对应的二叉树，称为完全二叉树
如图 B，是一棵完全二叉树，而图 C 和图 D 不是完全二叉树，因为它们没有完全符合满二叉树编号。注意是一一对应，因此图 D 的三号节点不符合编号。
1.5 对任何一棵二叉树，如果其叶节点数为 \(m\)，度为 2 的节点数为 \(b\)，则一定满足 \(b=m+1\)。
因为二叉树中所有节点的度数均不大于 2，因此节点总数 \(tot=a+b+c\)，其中 \(a\) 为 0 度节点数，\(b\) 为 1 度节点数，\(c\) 为 2 度节点数。
并且，1 度节点数有一个孩子，2 度节点数有两个孩子，因此孩子总数为 \(b+2c\)。
树中只有根节点不是任何
1.6 具有 n 个节点的完全二叉树的深度为 \(log 2^n\) 向下取整
1.7 对于一棵 \(n\) 个节点的树，对任何一个节点，有（1）若 \(i=1\)，则节点为根；（2）若 \(i>1\)，其父节点为 \(i/2\)；（3）如果 \(2*i>n\)，则节点 \(i\) 没有左右孩子，否则左孩子编号为 \(i/2\)；如果 \(2*i+1>n\)，则节点 \(i\) 无右孩子，否则右孩子节点编号为 \(2*i+1\)
2.树的遍历
对于上图的二叉树，有以下几种遍历方式。
2.1 中序遍历
按照“左右根”的顺序遍历，即递归地寻找左子树，进行中序访问，然后是根，最后寻找右子树，进行中序访问，直到找到叶节点。这种遍历方法只适用于二叉树。
2.2 先（前）序遍历
按照“根左右”的顺序遍历，具体方法同上。
2.3 后序遍历
按照“左右根”的顺序遍历。