数据结构中树的复习与总结

树是整个《数据结构》的重点章节，而其中的二叉树又是本章的重点内容。本章在试题中所占分数达到20%左右，如加上其他章节与二叉树有关的二叉排序树等内容，则占有四分之一以上的分值，可见树是十分重要的内容，务必仔细掌握各个知识点。在这一章里要了解树的定义熟悉二叉树的定义、性质、存储结构、遍历、线索化和树的存储结构、遍历以及树、森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。算法的重点是二叉树的遍历及其有关应用。这也是本章的难点。

树与二叉树

树的逻辑结构特征是：树中任一结点都可以有零个或多个直接后继(孩子)结点，但至多只能有一个直接前趋(双亲)结点。树形结构是非线性结构。二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0),或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

二叉树不是树的特殊情形，似乎不容易理解。问题就在于二叉树是无论结点是否只有一个孩子，它都要确定是左孩子或右孩子，而度数为二的有序树虽然很象二叉树，但是当结点只有一个孩子时，就无须区分它是左还是右的次序。(也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了)，因此二者是不同的。二叉树的画法是一定要会。

二叉树的顺序存储结构就是把二叉树的所有结点按照一定次序(从根结点起，从上层到下层，从左往右编号就得到了存放的次序)存储到一片连续的存储单元中 。对于顺序存储方式的二叉树，可以根据结点的编号可以直接得出结点之间的逻辑关系，这里应该会计算应用，比如知道一个结点的序号为3，要我们计算其双亲的序号，兄弟、孩子等序号。只要对完全二叉树的形态了如指掌，这样的计算也是易如反掌的。

用顺序存储方式对于完全二叉树而言其结构简单又节省空间，但是对于一般二叉树并不合适。因此树的存储结构更多的是用链式存储。结点的结构为两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据。把所有二叉树的结点，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root唯一确定的。

二叉树的遍历