二叉树

一 树形结构：

数据结构分为线性结构和树形结构，如下图：

• 线性结构：

• 树形结构：

• 生活中的树形结构

  

二 树(Tree)的基本概念

• 节点，父节点，子节点，跟节点，兄弟节点

• 一棵树可以没有任何节点，成为空树

• 一棵树可以只有一个节点，也就是跟节点

• 子树，左子树，右子树

• 节点的度：子树的个数

• 树的度：所有接点度中的最大值

• 叶子节点leaf：度为0的节点

• 非叶子节点： 度不为0的节点

• 层数：根节点在第一层，根节点的字节点在第二层，以此类推

• 节点的深度：从根节点到当前节点的节点总数

• 节点的高度：从当前节点到最远叶子节点的路径上的节点总数

• 树的深度：所有节点深度中的最大值

• 树的高度：所有节点高度中的最大值

• 树的深度等于树的高度

有序树，无序树，森林

• 有序树：树中任意节点的字节点有顺序关系
• 无序树：树中任意节点的字节点没有顺序关系，也成为自由树
• 森林：由m(m >= 0) 棵互不相交的树组成的集合

二叉树（Binary Tree）

二叉树的特点：

• 每个节点的度最大为2（最多拥有两棵子树）
• 左子树和右子树是有顺序的
• 即使某一节点只有一棵树，也要区分左右子树
• 有序树

二叉树的性质：

• 非空二叉树，第i层最多有 (2 ^ （i-1）)个节点

• 在高度为h的二叉树上，最多有 2 ^ h - 1 个节点

  • 在任意一棵非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则n0 = n2 + 1；

  • 加入度为1的节点总数为n1，则节点总数n = n0 + n1 + n2；

  • 二叉树的边数 T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1;

  • 因此 n0 = n2 + 1；

真二叉树(Proper Binary Tree)：

度要么为0，要么为2的二叉树。 如图：

下图不是真二叉树，因13， 15节点度为1.

满二叉树(Full Binary Tree)：

• 最后一层节点的度为0， 其他节点的度都为2
• 在同样高度的二叉树中，满二叉树的叶子节点最多，总节点数量最多
• 满二叉树一定是真二叉树，真二叉树不一定是满二叉树

满二叉树性质

假设满二叉树的高度为h(h >= 1),

• 那么第i层的节点数量为： 2 ^ (i - 1)
• 叶子节点数量 ：2 ^ (h - 1)
• 总节点数量： n = 2 ^ h - 1

假设满二叉树的节点总数为n，则

• h = log2(n + 1)

完全二叉树

对节点从上到下从左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应。

特点

• 叶子节点只能出现在最后两层，最后一层的叶子节点都靠左对齐
• 完全二叉树丛根节点到倒数第二层是一棵满二叉树
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

性质

• 度为1的节点只有左子树

• 度为1的节点要么是1个，要么是0个

• 同样节点数量的二叉树，完全二叉树的高度最小

• 假设完全二叉树的高度为h(h >= 1),那么

  • 至少有 2 ^ (h - 1) 个节点（最后一层只有一个节点）
  • 最多有 2 ^ h - 1 个节点（满二叉树）
  • 总节点数为n
    • 2 ^ (h - 1) <= n < 2 ^ h
    • h - 1 <= log2N < h
    • h = floor(log2N) + 1 (floor是向下取整)

• 一棵完全二叉树有n个节点，从上到下，从左到右从1开始编号，对任意第i个节点

  • 如果i = 1，它是根节点
  • 如果i > 1, 它的父节点的编号为floor(i / 2)
  • 如果 2i <= n, 它的左节点编号为2i
  • 如果 2i > n, 它没有左子节点
  • 如果 2i + 1 <= n , 它的右子节点编号为 2i + 1
  • 如果 2i + 1 > n, 它没有右子节点

• 一棵右n个节点的完全二叉树(n > 0)，从上到下，从左到右从0开始编号，对任意第i个节点

  • 如果i = 0， 它是根节点
  • 如果i > 0, 它的父节点编号为 floor (i - 1) / 2)
  • 如果2i + 1 <= n - 1, 它的左子节点为 2i + 1
  • 如果2i + 1 > n - 1, 它没有左子节点
  • 如果2i + 2 <= n - 1, 它的右子节点为 2 i + 1
  • 如果2i + 2 > n - 1, 它没有右子节点

下图是不是一个完全二叉树

很明显不是， 5 / 6 节点度都是1，都有左子树，故不符合完全二叉树性质。

二叉树的遍历

遍历是数据结构的常用操作，把所有元素都访问一遍

线性数据结构的遍历比较简单， 正序遍历，倒序遍历。

根据节点访问顺序的不同，二叉树的常见遍历方式由四种：

• 前序遍历(Preorder Travesal)

• 中序遍历(Inorder Travesal)

• 倒序遍历(Postorder Travesal)

• 层序遍历(Level order Travesal)

前序遍历

访问顺序：根节点，遍历左子树，遍历右子树

打印顺序：7 4 2 1 3 6 9 8 11 10 12

递归 或者利用栈 前序遍历

中序遍历

访问顺序：中序遍历左子树，再访问根节点，中序遍历右子树

打印树序：1 2 3 4 5 7 8 9 10 11 12

递归 或者利用栈 中序遍历

后序遍历

访问顺序：先后续遍历左子树，再后序遍历右子树， 再访问根节点。

打印顺序：1 3 2 5 4 8 10 12 11 9 7

递归 或者利用栈 后序遍历

层序遍历

从上到下， 从左到右，依次访问每个节点

打印顺序：7 4 9 2 5 8 11 1 3 10 12

利用队列层序遍历元素。

四则运算

四则运算的表达式可分为三种

前缀表达式（prefix expression）,又称为波兰表达式

中缀表达式（infix epression）

后缀表达式（postfix expression）,又称为逆波兰表达式

表达式树

如果将表达式的操作数作为叶子节点， 运算符作为父节点（假设只有四则运算）

这些节点刚好组成一棵树，如表达式： A/B + C * D - E

可组成如上一棵树，

对上边的二叉树进行前序遍历，结果如下

-+/AB*CDE 刚好就是波兰表达式即前缀表达式

对上边的二叉树进行中序遍历，结果如下

A/B+C*D-E 刚好是中缀表达式

对上边的二叉树进行后续遍历，结果如下

AB/CD*+E- 刚好就是后缀表达式即逆波兰表达式

根据遍历结果，重构二叉树

以下结果可以重构出一个唯一的二叉树

前序遍历+中序遍历

后序遍历+中序遍历

前序遍历+后序遍历

如果它是一棵真二叉树，则结果是唯一的。

不然结果不唯一

练习题

题目一：

如果一棵完全二叉树节点总数是768个，求叶子节点的个数。

题解：

• 假设叶子节点总数为n0，度为1的节点为n1，度为2的节点个数为n2

• n = n0 + n1 + n2; 且 n0 = n2 + 1(由边数求得);

• n = no * 2 + n1 - 1;

• 在完全二叉树中， n1要么为0 要么为1

  • 当n1为1时，n = 2 * n0, n必然是偶数。 叶子节点个数为 n0 = n / 2. 非叶子节点个数n1 + n2 = n / 2；
  • 当n1为0时，n = 2n0 - 1, n必然是奇数。 叶子节点个数为 n0 = (n + 1) / 2. 非叶子节点个数为 (n - 1) / 2;

• 叶子节点个数 n0 = floor((n + 1) / 2) = ceiling(n / 2)

• 非叶子节点个数 n1 + n2 = floor(n / 2) = ceiling((n - 1) / 2)

• 因此叶子节点的个数为 384

---

二叉树的遍历

有两种遍历树的策略：

• 深度优先搜索(DFS)

  在这个策略中，我们采用深度作为优先级，以便从根开始一直到达某个确定的叶子，然后再返回根到达下一个分支。

  深度优先搜索，又可以根据根节点，左子节点和右子节点的相对顺序被分为 前序遍历 ，中序遍历，后序遍历。

• 宽度优先搜索(BFS)

  我们按照一层一层访问整棵树，高层次的节点将比低层次的节点先访问到。

如下图中，按照1 2 3 4 5比较不同的策略。