这些天参与了CSDN论坛的讨论，改变了我以前的一些看法。回头看我以前的东西，我虽对这本书很不满，但我还是按照它的安排在一点点的写；这样就导致了，我过多的在意书中的偏漏，我写的更多是说“这本书怎样”，而偏离了我写这些的初衷——给正在学习数据结构的人一些帮助。正像我在前面所说的，虽然现有的教科书都不是很合理，但如果仅仅是抱怨这点，那无异于泼妇骂街。虽然本人的水平连初级都够不上，但至少先从我做一点尝试，以后这门课的教授方法必将一点点趋于合理。 因此，后面不在按照书上的次序，将本着“实际应用（算法）决定数据结构”的思想来讲解，常见教科书上有的，基本不再重点叙述（除了重点，例如AVL树的平衡旋转），——因此，在看本文的同时，一定要有一本教科书。这只是一个尝试，希望大家多提宝贵意见。 树 因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等，而为了研究这类问题，必须能够将树储存，而如何储存将取决于所需要的操作。这里有个问题，是否允许存在空树。有些书认为树都是非空的，因为树表示的是一种现实结构，而0不是自然数；我用过的教科书都是说可以有空树，当然是为了和二叉树统一。这个没有什么原则上的差别，反正就是一种习惯。 二叉树 二叉树可以凳侨嗣羌傧氲囊桓瞿Ｐ停虼耍市碛锌盏亩媸魇俏拚榈摹６媸魇怯行虻模蟊哂幸桓龊⒆雍陀冶哂幸桓龅亩媸魇遣煌牧娇檬鳌Ｗ稣飧龉娑ǎ且蛭嗣歉秤枇俗蠛⒆雍陀液⒆硬煌囊庖澹诙媸鞯母髦钟τ弥校憬崆宄目吹健Ｏ旅嬷唤步饬词浇峁埂？锤髦纸彩萁峁沟氖椋慊岱⑾忠桓鲇腥さ南窒螅涸诙媸髡饫铮静僮饔屑扑闶鞲摺⒏髦直槔褪敲挥胁迦搿⑸境鞘魇窃趺唇⑵鹄吹模科涫嫡夂芎美斫猓杂诜窍咝缘氖鹘峁梗迦肷境僮鞑辉谝欢ǖ姆ㄔ蚬娑ㄏ拢呛廖抟庖宓摹Ｒ虼耍挥性诰咛宓挠τ弥校呕嵊胁迦肷境僮鳌?SPAN lang=EN-US> 节点结构 数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲，或者是资源紧张，建议附加一个双亲指针，这将会给很多算法带来方便，尤其是在这个“空间换时间”的时代。 template <class T> struct BTNode {     BTNode(T data = T(), BTNode<T>* left = NULL, BTNode<T>* right = NULL, BTNode<T>* parent = NULL)         : data(data), left(left), right(right), parent(parent) {}     BTNode<T> *left, *right, *parent;     T data; }; 基本的二叉树类 template <class T> class BTree { public:     BTree(BTNode<T> *root = NULL) : root(root) {}     ~BTree() { MakeEmpty(); }     void MakeEmpty() { destroy(root); root = NULL; } protected:     BTNode<T> *root； private:     void destroy(BTNode<T>* p)     {         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<T>* p, void (*visit)(T &data)) { 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<T>* p, void (*visit)(T &data)) {        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<T>* p, void (*visit)(T &data)) {        if (p){ PostOrder(p->left, visit); PostOrder(p->right, visit); visit(p->data); }        } 4.         层次遍历 void LevelOrder(void (*visit)(T &data) = print) {        queue< BTNode<T>* > a; BTNode<T>* p = root;//记得#include<queue>        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<T>* next() {        if(!current) return NULL;        if (current->right) { current = current->right; while (current->left) current = current->left; }        else        {               BTNode<T>* y = current->parent;               while (y && current == y->right) {current = y; y = y->parent; }               current = y;        }        return current; } private: BTNode<T>* current; 上面的函数能使current指针向前移动一个位置，如果要遍历整棵二叉树，需要使current指向中序序列的第一个节点，例如下面的成员函数： public: void first() { current = root; while (current->left) current = current->left; }

评论