ChinaITLab.com 
2003-10-16 
|
这些天参与了CSDN论坛的讨论，改变了我以前的一些看法。回头看我以前的东西，我虽对这本书很不满，但我还是按照它的安排在一点点的写；这样就导致了，我过多的在意书中的偏漏，我写的更多是说“这本书怎样”，而偏离了我写这些的初衷——给正在学习数据结构的人一些帮助。正像我在前面所说的，虽然现有的教科书都不是很合理，但如果仅仅是抱怨这点，那无异于泼妇骂街。虽然本人的水平连初级都够不上，但至少先从我做一点尝试，以后这门课的教授方法必将一点点趋于合理。 因此，后面不在按照书上的次序，将本着“实际应用（算法）决定数据结构”的思想来讲解，常见教科书上有的，基本不再重点叙述（除了重点，例如AVL树的平衡旋转），——因此，在看本文的同时，一定要有一本教科书。这只是一个尝试，希望大家多提宝贵意见。 树 因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等，而为了研究这类问题，必须能够将树储存，而如何储存将取决于所需要的操作。这里有个问题，是否允许存在空树。有些书认为树都是非空的，因为树表示的是一种现实结构，而0不是自然数；我用过的教科书都是说可以有空树，当然是为了和二叉树统一。这个没有什么原则上的差别，反正就是一种习惯。 二叉树 二叉树可以说是人们假想的一个模型，因此，允许有空的二叉树是无争议的。二叉树是有序的，左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定，是因为人们赋予了左孩子和右孩子不同的意义，在二叉树的各种应用中，你将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书，你会发现一个有趣的现象：在二叉树这里，基本操作有计算树高、各种遍历，就是没有插入、删除——那树是怎么建立起来的？其实这很好理解，对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应用中，才会有插入删除操作。 节点结构 数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲，或者是资源紧张，建议附加一个双亲指针，这将会给很多算法带来方便，尤其是在这个“空间换时间”的时代。 template struct BTNode { BTNode(T data = T(), BTNode : data(data), left(left), right(right), parent(parent) {} BTNode T data; }; 基本的二叉树类 template class BTree { public: BTree(BTNode ~BTree() { MakeEmpty(); } void MakeEmpty() { destroy(root); root = NULL; } protected: BTNode private: void destroy(BTNode { if (p) { destroy(p->left); destroy(p->right); delete p; } } } 二叉树的遍历 基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？到了后面才明白，这是不同的应用需要的。例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。 实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性，这些遍历方法能很清晰的表达。 1. 前序遍历 public: void PreOrder(void (*visit)(T &data) = print) { PreOrder(root, visit); } private: void PreOrder(BTNode { if (p){ visit(p->data); PreOrder(p->left, visit); PreOrder(p->right, visit); } } 2. 中序遍历 public: void InOrder(void (*visit)(T &data) = print) { InOrder(root, visit); } private: void InOrder(BTNode { if (p){ InOrder(p->left, visit); visit(p->data); InOrder(p->right, visit); } } 3. 后序遍历 public: void PostOrder(void (*visit)(T &data) = print) { PostOrder(root, visit); } private: void PostOrder(BTNode { if (p){ PostOrder(p->left, visit); PostOrder(p->right, visit); visit(p->data); } } 4. 层次遍历 void LevelOrder(void (*visit)(T &data) = print) { queue< BTNode while (p) { visit(p->data); if (p->left) a.push(p->left); if (p->right) a.push(p->right); if (a.empty()) break; p = a.front(); a.pop(); } } 附注：缺省的visit函数print如下 private: static void print(T &data) { cout << data << ' '; } 5. 不用栈的非递归中序遍历 当有parent指针时，可以不用栈实现非递归的中序遍历，书上提到了有这种方法，但没给出例程。 public: BTNode { if(!current) return NULL; if (current->right) { current = current->right; while (current->left) current = current->left; } else { BTNode while (y && current == y->right) {current = y; y = y->parent; } current = y; } return current; } private: BTNode 上面的函数能使current指针向前移动一个位置，如果要遍历整棵二叉树，需要使current指向中序序列的第一个节点，例如下面的成员函数： public: void first() { current = root; while (current->left) current = current->left; } 【2】 线索化二叉树 这是数据结构课程里第一个碰到的难点，不知道你是不是这样看，反正我当初是费了不少脑细胞——当然，恼人的矩阵压缩和相关的加法乘法运算不在考虑之列。我费了不少脑细胞是因为思考：他们干什么呢？很欣喜的看到在这本黄皮书上，这章被打了*号，虽然我不确定作者是不是跟我一个想法——线索化二叉树在现在的PC上是毫无用处的！——不知我做了这个结论是不是会被人骂死，^_^。 为了证明这个结论，我们来看看线索化二叉树提出的缘由：第一，我们想用比较少的时间，寻找二叉树某一个遍历线性序列的前驱或者后继。当然，这样的操作很频繁的时候，做这方面的改善才是有意义的。第二，二叉树的叶子节点还有两个指针域没有用，可以节省内存。说真的，提出线索化二叉树这样的构思真的很精巧，完全做到了“废物利用”——这个人真应该投身环保事业。但在计算机这个死板的东西身上，人们的精巧构思往往都是不能实现的——为了速度，计算机的各个部件都是整齐划一的，而构思的精巧往往都是建立在组成的复杂上的。 我们来看看线索化二叉树究竟能不能达到上面的两个目标。 求遍历后的线性序列的前驱和后继。前序线索化能依次找到后继，但是前驱需要求双亲；中序线索化前驱和后继都不需要求双亲，但是都不很直接；后序线索化能依次找到前驱，但是后继需要求双亲。可以看出，线索化成中序是最佳的选择，基本上算是达到了要求。 节省内存。添加了两个标志位，问题是这两个位怎么储存？即使是在支持位存储的CPU上，也是不能拿位存储器来存的，第一是因为结构体成员的地址是在一起的，第二是位存储器的数目是有限的。因此，最少需要1个字节来储存这两个标志位。而为了速度和移植，一般来说，内存是要对齐的，实际上根本就没节省内存！然而，当这个空间用来储存双亲指针时，带来的方便绝对不是线索化所能比拟的，前面已经给出了无栈的非递归遍历。并且，在线索化二叉树上插入删除操作附加的代价太大。 综上，线
| |
 相关文章 |
热门文章 |
|
| 系统分析师论文"论建立企业INTRANET的策略" 计算机软件水平考试：《数据结构》是核心 系统分析员考试备考要略 系统分析员备考之经济管理篇（二） 系统分析员备考之经济管理篇(一) 软件设计师复习－－检错码ＣＲＣ 关于高程下午试题的一些预测与解题方法 程序高手必读：写好C程序的10条秘籍 1990-2000年事务处理流程图和数据流图试题分… 数据结构学习（C++）——树（总结） |
| 文章评论 | |||