Question

Binary Tree

“二元树”是计算机科学最重要的概念，甚至可以说：二元树开创了计算机科学。

像是资料结构 Binary Search Tree 与 Heap，交换式排序演算法的 Decision Tree、资料压缩的 Huffman Tree、3D 绘图的 BSP Tree、编译器的 Parse Tree……，这一大堆稀奇古怪的术语，通通都是二元树。总之，二元树的应用相当广泛，是资工系学生必学的基础概念。

“二元树”与“树”，儘管名称相近，但是概念不相近，至于用途更是天差地远，两者可以分别独立学习。二元树：资料结构课程的二元搜寻树章节，会顺便引出二元树的概念；树：演算法课程的图论章节，一开始就会介绍树的定义。

言归正传。“二元树”就是分两岔的树，每个节点可以有左小孩和右小孩，每个节点可以有零个、一个、两个小孩。

顺便介绍几个特殊的二元树：

full binary tree：除了树叶以外，每个节点都有两个小孩。

complete binary tree：各层节点全满，除了最后一层，最后一层节点全部靠左。

perfect binary tree：各层节点全满。同时也是 full binary tree 和 complete binary tree。

Binary Tree 资料结构

第一种方法，是建立节点，运用指标串接各个节点。

第二种方法，是让二进位数字一一对应到二元树的节点。

建立一个阵列，运用阵列索引值就能得到各个节点：树根的索引值固定是一，索引值乘上两倍就得到左小孩，索引值乘上两倍再加一就得到右小孩，索引值除以二就得到父亲。

优点是程式码简洁，效率高。

缺点是浪费记忆体空间。如果不是 complete binary tree，那麽阵列就有很多閒置空格。

另一个缺点是树的高度受限制。1024 = 2^10 格的阵列，树的高度只有 10，不能更高了。

UVa 112 122

Binary Tree Traversal

二元树的遍历顺序，理论上总共四种──但是事实上还是只有 DFS 与 BFS 两种，只不过更动了节点的输出顺序。

注意树根的位置，就能轻鬆解读这四种序。

Preorder Traversal 前序遍历
理论上的遍历顺序是：根、左子树、右子树。根排在前面。
即是 Depth-first Search。

Inorder Traversal 中序遍历
理论上的遍历顺序是：左子树、根、右子树。根排在中间。
实际上是採用 Depth-first Search，只不过更动了节点的输出顺序。

Postorder Traversal 后序遍历
理论上的遍历顺序是：左子树、右子树、根。根排在后面。
实际上是採用 Depth-first Search，只不过更动了节点的输出顺序。

Level-order Traversal 层序遍历
即是 Breath-first Search。

UVa 112 699

Binary Tree Reconstruction

以一棵二元树能得到前序、中序、后序、层序，那麽以前序、中序、后序、层序能得到一棵二元树吗？

只有一种序，是无法还原出一棵二元树的，有很多可能性。

有两种序，就有机会还原出唯一一棵二元树。比方说，只知道 preorder 和 inorder，求出原本的二元树。

运用 Divide and Conquer 可以巧妙解决。在 preorder 之中，最左边的元素就是 root；在 inorder 之中，root 的两边分别为左子树和右子树──利用 root 便可区分左子树和右子树。子树也是树，可以用相同手法继续分割，最后便可求出整棵树的架构。

但是只有 preorder 和 postorder 的话，是做不出答案的。因为无法确定树根的位置。

那麽 level-order 呢？大家就自己想想吧。

UVa 10701 536 548 10410 12347

Polish Notation / Reverse Polish Notation

凡是谈到二元树的前序、中序、后序，总是顺便谈到四则运算的前序、中序、后序表示法。

我们可以将一道四则运算式子，换成二元树。

然后列出此二元树的前序、中序、后序。其中前序就是波兰表示法，又称作 prefix；中序就是原来的四则运算式子、需要括号，又称作 infix；后序就是逆波兰表示法，又称作 postfix。

然而，建立二元树是很麻烦的。能不能略过二元树，直接把四则运算式子换成波兰表示法（逆波兰表示法）呢？当然能！只要运用 stack，就可以做到这件事情。

一道四则运算式子，改成波兰表示法（逆波兰表示法）之后，计算过程变成由左往右计算，不必顾虑先乘除后加减、不必顾虑括号，只需要一个额外的 stack 作为辅助。

程式语言的四则运算式子，事实上都会被编译器转换成波兰表示法（逆波兰表示法），以利电脑计算。

UVa 372 727 11234 172 10700 10847

N-ary Tree

N-ary Tree（k-way Tree）

“多元树”就是分 N 岔的树，每个节点可以有零个、一个、两个、……、N 个小孩。

注意到：多元树，节点只有一个小孩时，没有左小孩、右小孩的差别；二元树，节点只有一个小孩时，有左小孩、右小孩的差别。

Left Child/Right Sibling Representation

一棵多元树，可以改用二元树表示：多元树的左小孩，是二元树的左小孩；多元树的其馀小孩（左小孩的兄弟），是二元树的右小孩、右右小孩、……。

芸芸多元树，皆得简化成二元树；区区二元树，便可描述出多元树。万流归宗、一以贯之。

有兴趣的读者，可以观察多元树与转化过的二元树的前序、中序、后序、层序。也可以计算一下多元树的节点数目、树叶数目、高度。