三 树（一）
树形结构是一种美丽的结构。
它是计算机科学中一种重要的结构，尤其是在数据结构中。我们通过下图，帮助您回忆这一切。
对于数据的组织，树形结构在一个非常特殊而重要的位置。一般来说，线性表简洁，可以组织通过线性关系或其复合所能表达的数据，而图结构，是更一般意义上的结构，可作为建模之用，且可视为所有数据结构的最一般形式，线性表和树形结构都可看作它的受限形式；但非线性的结构中，当是树形结构最为简洁，和线性表与图相比，它对于大量数据的组织，尤其是排序与检索过程中，有着不可替代的作用。
这次我们就谈谈二叉树和树。当然，只讨论若干问题哦。
1，二叉树的周游
遍历访问树结构，二叉树的周游是个典型。当然，很简单的，递归访问有前序、中序和后序三种形式，其它的形式另有层次访问（相当于宽度优先）。然记得前一段时间一个同学去华为参加面试，人家让他用c写二叉树的周游程序，他竟然没有写出。所以还得请大学生朋友注意基本功哦。
我们看个例子，如下图的二叉树：
它的递归周游结果，可如下给出：
1） 前序：A，B，D，C，E，G，F，H，I
2） 中序：B，D，A，G，E，C，H，F，I
3） 后序：D，B，G，E，H，I，F，C，A
我们不再给出算法的实现细节，您可以参阅有关书籍。可是，我们看一个有趣的问题，这三个结果，任意知道其中两种，您能推出第三种吗？实质就是，任意知道两种递归周游的结果，您可以重建二叉树吗？
我们先假设知道前序与中序的结果，即：
前序：A，B，D，C，E，G，F，H，I
=> 二叉树 ？
中序：B，D，A，G，E，C，H，F，I
记得当初见到这个题目的时候，有点懵了；然而，如果细细的分析算法特点的话，还是不难分析出的。
由前序周游算法的特点您可知道，A一定是整棵树的根，但仅看前序的结果，下面是分析不出左、右子树的分界线的。可是您再看中序的结果：
B，D，/ A，/ G，E，C，H，F，I
由中序周游算法的特点，很容易就能看出，B与D是左子树的结点，G，E，C，H，F，I等是右子树的结点。先看左子树部分，由前序的结果，如上进行判断，B是其根。对于D，但由前序的结果，您是无法判断它是B的左孩子还是右孩子的，再看中序的结果，才能知道B的左子树为空，D为其右孩子。然后照此判断A的右子树。就可以重建二叉树了。
如果写出这个算法，很显然还是可以写成递归的算法的。而且，中序周游的结果加后序周游的结果来重建二叉树的话，过程与此类似。
然而，如果只知道前序与后序的结果，这个问题就稍微复杂些了。能还是不能？如果不能，可如何进行补救？若您感兴趣不妨自己分析一下，我下次再给出答案。
二叉树的周游是最基本的算法。与它相关的算法，就有查询（以及与查询有关的插入、删除等），求树的高度，求结点数（或叶结点数、分支结点数）等。后面我提到的这些，大家不妨用高级语言写写算法的实现，看我同学的教训，基本功扎实才好。
2，建立最大堆
堆是个有意思的数据结构，从逻辑上讲，它是个完全二叉树。我们给出它的两个基本特点，记得了，理解了，对您掌握堆很有帮助。
一是，堆为顺序存储结构实现的完全二叉树；二是，此树局部有序。
特点一大家都明白，特点二却是在说，比如最大堆，它不象排序二叉树那样是完全有序的，对于每一棵子树（当然也包括树本身）的根，其值总是在左、右孩子结点中为最大的，而左、右孩子结点却不一定有序。
所以建立最大堆的算法，也相当自然。如下图：
在R左、右子树均不为空的情况下，递归如下的操作：
1） 若R>=H1,且R>=H2,则本操作已完成。
2） 否则，将R与H1、H2中较大的一个交换。
这样，您只要按一定的顺序访问堆中所需的结点进行下调调节，就可以建立最大堆。只是，对于算法的细节，您要注意到堆的第一个特点，并注意设计良好的调节顺序，由底层向顶层方向层层调节方可。如下图：
堆的用途，当然很多了，大家最容易想到的，就是堆排序。
二叉树的线索化，我们没什么可说的。Huffman树编码，则是贪心算法的典型。若对贪心策略的原理清楚的话，则此算法的基本内容就不会有什么问题了。
我们下次还继续讨论树形结构这一主题。
本文地址：http://com.8s8s.com/it/it37446.htm