1、数据结构二叉树（c+）【摘要】现实社会中的树书籍的目录、任务大纲、家族族谱之类等等。人们要研究就必须能过将树正确的储存，如何存储又关系到实际的操作。树是否为空，在本学期学习的数据结构的教材中允许树为空 【1】 。因为树表现形式的是一种现实的结构，而 0 不是自然数。从直观上看树是分支关系定义的层次结构，其中树和二叉树是最常见的 【1】 。【关键词】 数据结构；树；二叉树；遍历；探讨空间；1、二叉树1.1 二叉树 T 是有限的结点的集合（允许为空） ，或者由一个根结点 u 以及分别称为左子树和右子树的两棵互不相交的二叉树 u(1)和 u(2)组成。若用 n,n1 和 n2 分别表示T，u(1)和
2、 u(2)的结点数，则有 n=1+n1+n2 。u(1)和 u(2)有时分别称为 T 的第一和第二子树。在二叉树中，每个结点至多有两个孩子，并且有左、右之分。因此任一结点的孩子不外4 种情况：没有孩子；只有一个左孩子；只有一个右孩子；有一个左孩子并且有一个右孩子。 （如图 1.1）图 1.1 五种基本形态 （其中 表示空）1.2 二叉树与度数不超过 2 的树不同，与度数不超过 2 的有序树也不同。在有序树中，虽然一个结点的孩子之间是有左右次序的，但若该结点只有一个孩子时，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。图 1.2a （不同的两颗二叉树） 图 1.2b（普通的一棵
3、树）由图可见：(a)和(b) 是两棵不同的二叉树。虽然它们与普通的一棵树(作为无序树或有序树)很相似，但它们却不能等同于这棵普通的树。若将这 3 棵树均看作是有序树，则它们就是相同的了。所以二叉树和树尽管有很多相似 ，但是二叉树不是树的特殊情形。所以，二叉树是一种人们假设的一种现象，所以允许为空是无争议的。二叉树是一种有序的树，左边是孩子、右边是兄弟。其实可以看作不同的两棵树。做这个规定，正式因为人们要赋予给孩子兄弟不同的意义。通过这学期的学习发现了一个现象，就是树并没有插入删除操作。对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应用中，才会有插入删除操
4、作。2、特殊形态的二叉树2.1 满二叉树 【1 】 ：一棵高度为 h0 且有 2h+1-1 个结点的二叉树称为满二叉树。 （如图3.1） 图 3.1 （满二叉树）2.2 完全二叉树 【1 】 ：若一棵二叉树至多只有最下面的两层结点的度数小于 2，并且最下面一层结点都集中在该层的最左边，则称这种二叉树为完全二叉树。 （如图 3.2）图 3.2 （完全二叉树）3、二叉树的遍历以及实现（c+ ）3.1 二叉树基本上有先序遍历、中序遍历、后序遍历，最开始并不明白为什么有这么多，到了后面才明白，这是不同的应用需要的。例如，删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历，而判断两个
5、二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；3.1.1 前序遍历public:void PreOrder(void (*visit)(T private:void PreOrder(BTNode* p, void (*visit)(T PreOrder(p-left, visit); PreOrder(p-right, visit); 3.1.2 中序遍历 public:void InOrder(void (*visit)(T private:void InOrder(BTNode* p, void (*visit)(T visit(p-data); InOrder(
6、p-right, visit); 3.1.3 后序遍历public:void PostOrder(void (*visit)(T private:void PostOrder(BTNode* p, void (*visit)(T PostOrder(p-right, visit); visit(p-data); 4、二叉树的顺序存储结构4.1 在一棵具有 n 个结点的近似满二叉树中，我们从树根起，自上到下，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列。所以，顺序存储结构是二叉树的一种特点，按照一定的顺序存储在特定的连续单元中。 （如图4.1）图 4.1 （完全二叉树
7、的结点编号）我们将数组下标作为结点编号，就可将二叉树中所有结点的标号存储在一维数组中。（如图 4.2）图 4.2可以看到二叉树的这种表示方式下，各结点之间的逻辑关系是隐含表示的。完全二叉树中，除最下面一层外，各层都充满了结点。除最底层外，每一层的结点个数恰好是上一层结点个数的 2 倍。因此，从一个结点的编号就可推知其父亲，左孩子、右兄弟，等各结点的编号。假设对结点为 i 的二叉树有如下定义：1. 仅当 i=1 时，结点 i 为根结点；2. 当 i1 时，结点 i 的父结点为i/2；3. 结点 i 的左孩子结点为 2i；4. 结点 i 的右孩子结点为 2i+1；5. 当 i 为奇数且不为 1 时
8、，结点 i 的左兄弟结点为 i-1；6. 当 i 为偶数时，结点 i 的右兄弟结点为 i+1。4.2 但对于一般的二叉树，采用顺序存储时，为了能用结点在数组中的位置来表示结点之间的逻辑关系，也必须按近似满二叉树的形式来存储树中的结点。一个只有 k 个结点的右单枝树却需要 2k-1 个结点的存储空间。假设结点为 3 的右单二叉树，添上虚结点后，成为一棵近似满二叉树。 （如图 4.2）图 4.3 可知这样造成的存储空间的浪费5、索化二叉树5.1 当 用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右孩子结点的指针，所以从任一结点出发只能直接找到该结点的左、右孩子。在一般情况下靠它无法
9、直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。例：一棵中序线索二叉树如（图 5.1）：图 5.1图 5.2 （线索链表）由图 5.2 可知：在二叉树的线索链表上增加了一个头结点，其 LeftChild 指针指向二叉树的根结点，其 RightChild 指针指向中序遍历时的最后一个结点。另外，二叉树中依中序列表的第一个结点的 LeftChild 指针，和最后一个结点的 RightChild 指针都指向头结点。这就像为二叉树建立了一个双向线索链表，既可从第一个结点起，顺着后继进行遍历，也可从最后一个结点起顺着前驱进行遍历。6、探
10、讨线索化二叉树是否降低空间效率7.1 线索化二叉树提出的缘由：第一，二叉树的叶子节点还有两个指针域没有用，可以节省内存。第二，我们想用比较少的时间，寻找二叉树某一个遍历线性序列的前驱或者后继。当然，这样的操作很频繁的时候，做这方面的改善才是有意义的。7.2 证明：求遍历后的线性序列的前驱和后继。7.2.1 先序线索化能依次找到后继，但是前驱需要求双亲；中序线索化前驱和后继都不需要求双亲，但是都不很直接；后序线索化能依次找到前驱，但是后继需要求双亲。可以看出，线索化成中序是最佳的选择，基本上算是达到了要求。7.2.2 节省内存：线索化增加了两个标志位，但是这两个位怎么储存？即使是在支持位存储的
11、CPU 上，也不能拿位存储器来存的，第一是因为结构体成员变量的内存地址是在连续的一起的，第二是位存储器的存储数目是有限的。目前的计算机最少需要 1 个字节来储存这两个标志位。而为了传输速度和内存移植，大部分的内存是要对齐的，这就导致在内存中使用线索化二叉树根本就没节省内存。假设把个内存空间用来储存双亲指针时，带来的方便绝对不是线索化所能比拟的，前面已经给出了无栈的非递归遍历。并且，在线索化二叉树上插入删除操作附加的代价太大。结论：线索化线索化二叉树在现在的计算机上是毫无用处的。参考文献： 1. 数据结构理论与实践 杨永斌 杨友斌编著 天津：天津科技技术出版社2. 数据结构题集 （c 语言版） 严蔚敏等 编著 北京：清华大学出版社3. 数据结构-二叉树的运用 百度.百度文库
