以下内容来源：zzu信息工程学院数据结构课件
本文主要梳理二叉树的一些概念
1 二叉树的定义和术语
2 二叉树的性质
- 性质1：在二叉树的第
i层上至多有 2i-1 个结点(i≥1) - 性质2：深度为
k的二叉树至多有 2k－1 个结点(k≥1)
- 性质3：对任何一棵二叉树，如果其终端结点（度为0的结点）数为n0，度为2的结点数为n2，则n0＝n2＋1。
- 性质4：具有
n个结点的完全二叉树的深度为└log2n┘+ 1（log2n向下取整再+1）
- 性质5：如果对一颗有
n个结点的完全二叉树（其深度为└log2n┘+1）的结点按层序编号，对于任意结点i有：
①如果i = 1，则结点 i 是二叉树的根结点，无双亲；如果i > 1，则其双亲结点是└i/2┘
②如果2i > n，则节点 i 无左孩子；否则其左孩子就是 2i
③如果2i + 1 > n，则节点i无右孩子；否则其右孩子就是2i + 1
简要概括就是：一个结点编号为i，它的左孩子（若存在）编号一定是2i，它的右孩子（若存在）编号一定是2i + 1
3 二叉树的存储结构
二叉树的存储结构包括顺序存储结构和链式存储结构，先看顺序存储结构。（这个结构在算法题中使用较多）
注意在顺序存储结构存储时，0号单元空闲，1号单元存储根结点。
因为如果根节点是0号单元，那么2 × 0 = 0，就会使后面的子树都存在0号单元中。
然后是链式存储结构：
关于右下方的，可以套用已有的一个性质：n0 = n2 + 1
我们如果把所有的空链域都填上了一个叶子结点，那么原先的n个结点就都成了度为2的结点。由于叶子结点的个数 = 度为2的结点个数 + 1，所以空链域的个数就是n + 1。
链式存储结构还包括三叉链表，但也仅做了解。毕竟链式存储在算法题中本来就不怎么用到。
4 二叉树的遍历
4.1 二叉树遍历的定义和应用场合
4.2 二叉树遍历方法
根据遍历的顺序，我们有先序、中序、后序三种遍历方法。
三种遍历方法这么叫是有原因的，在课件中已经提出：
- 先序：先根序（DLR）
- 中序：中根序（LDR）
- 后序：后根序（LRD）
举个例子：
结果如下： - 先序：ABDEFHGC
- 中序：DBFHEGAC
- 后序：DHFGEBCA
算法实现也很简单，就是写一个递归，以先序为例：
4.3 二叉树遍历的应用
如何写二叉树应用问题的递归形式的遍历算法？
- 确定使用何种顺序的遍历
- 写出解决问题的递归描述，确定访问当前结点时要做什么操作
- 确定递归的出口条件
应用1 建立其二叉链表存储结构
应用2 利用遍历判断两棵二叉树是否相等
应用3 求二叉树中位于先序序列第k个结点的值
每遍历一次k - 1，k为0时返回这个结点，不为0时递归遍历左右子树，即count_k()。
得到返回的结点data值，即为Loc_k()。
这个算法当时我想了好久，印象尤深……现在看来不过如此，一扫而过。
呵，不过是递归的小把戏罢了
应用4 利用遍历求二叉树的深度
递归左右子树，返回深度最大值，结果+1即可。
应用5 删除二叉树中所有以值为x的结点为根的子树并释放相应空间
当前树的data == x，则删除该树的所有子树delsubtree()（无条件删除）。
否则再判断左右子树DelTree()。
应用6 用二叉树表示表达式
用中缀表达式计算时会出现优先级的错误，需要加括号，而用前、后缀表达式不加括号就可以避免优先级问题。所以说，在计算机内，使用前、后缀表达式可以直接进行求值运算。
比如，后缀表达式的处理方法——利用栈来模拟计算：
遇到操作数直接压栈，碰到操作符直接取栈顶的2个操作数进行计算（注意第一次取出来的是右操作数），然后再把计算结果压栈，如此循环下去。最后栈中剩下的唯一一个元素便是整个表达式的值。
应用7 用某两种序构造二叉树
已知某二叉树先序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 怎样构造二叉树？
这种东西就是靠观察：
先序第一个是A，那么树的结构肯定是A做为根结点。
根据中序可知，A的左子树包含结点HBDF，右子树包含结点EKCG
在HBDF中，由先序BHFD可知，B为左子树的根结点，同理，E为右子树的根结点。
由中序HBDF可知，B左子树包含结点H，右子树包含结点DF。
由中序EKCG可知，E左子树没有结点，右子树包含结点KCG。
其余分析同理，分析过程和结果如下：
当然，并不是任意给两种二叉树的遍历序列，都可以唯一确定一棵二叉树，因为先或后序的作用是确定根节点，中序的作用是确定根节点的左右子树包含哪些结点，这样一层一层递归地确定。如果只告诉先序 + 后序，确定的结果自然是不唯一的。即：
- 先序遍历 + 中序遍历
- 后序遍历 + 中序遍历
- 先序遍历 + 后续遍历（不可行）