Question

数据结构与算法分析 —— C 语言描述：二叉树

Answer 1

二叉树（binary tree）是一棵树，其中每个节点的儿子都不能多于两个。

二叉树的一个性质是平均二叉树的深度要比 N 小的多，这个性质有时很重要。分析表明，这个平均深度为 ，而对于特殊类型的二叉树，即二叉查找树(binary search tree)。其深度的平均值是 。不幸的是，在最坏情况下，这个深度可以大到 N-1 的。

因为一棵二叉树最多有两个儿子，所以我们可以用指针直接指向它们。树节点的声明在结构上类似于双链表的声明，在声明中，一个节点就是由 key（关键字）信息加上两个指向其他节点的指针（Left 和 Right）组成的结构。

应用于链表上的许多法则也可以应用到树上。特别地，当进行一次插入时，必须调用 malloc 创建一个节点。节点可以在调用 free 删除后释放。

我们可以用在画链表时常用的矩形框画出二叉树，但是，树一般画成圆圈并用一些直线连接起来，因为二叉树实际上就是图（graph）。当涉及树时，我们也不显示地画出 NULL 指针，因为具有 N 个节点的每一棵二叉树都将需要 N+1 个 NULL 指针。

二叉树有许多与搜索无关的重要应用。二叉树的主要用处之一是在编译器的设计领域。

上图就是一个表达式树（expression tree）。表达式树的树叶是操作树（operand），比如常数或者变量，而其他的节点为操作符（operator）。由于这里所有的操作都是二元的，因此这棵特定的树正好是二叉树，虽然这是最简单的情况，但是节点含有的儿子还是有可能多于两个的。一个节点也有可能只有一个儿子，如果有一目减算符（unary minus operator）的情形。可以将通过递归计算左子树和右子树所得到的值应用在根处的算符操作中而算出表达式树 T 的值。上面里的例子中，左子树的值是“((3+1) 3)/((9-5)+2)”，右子树的值是“(3 (7-4)+6)”，因此整棵树的表达式就是图上的结果。

我们可以通过递归产生一个带括号的左表达式，然后打印出在根处的运算符，最后再递归地产生一个带括号的右表达式而得到一个（对两个括号整体进行计算的）中缀表达式（infix expression）。这种一般的方法（左，节点，右）称为中序遍历（inorder traversal）；由于其产生的表达式类型，这种遍历很容易记忆。

另一个遍历策略是递归打印出左子树、右子树，然后打印运算符。如果我们应用这种策略于上面的树，则输出将是“31+3 95-2+/743- 6+-”。这种遍历策略一般称为后序遍历（postorder traversal）。

第三种遍历策略是先打印出运算法，然后递归地打印出右子树和左子树。同样的，应用这种策略于上面的树，则输出将是“-/ ++313-952+ 3-746”，这是一种不太常用前缀（prefix）记法，这种遍历策略为先序遍历（preorder traversal）。

这里我们只给出一种算法，来把后缀表达式转变成表达式树。这里的要点是，一次一个符号地读入表达式。如果符号是操作符，那么我们就建立一个单节点树并将一个指向它的指针推入栈中。如果符号是操作符，那么我们就从栈中弹出指向两棵树 和 的那两个指针( 的先弹出)并形成一棵新的树，该树的根就是操作符，它的左、右儿子分别指向 和 。然后将这棵新树的指针压入栈中。