C++数据结构学习:二叉树(1)[组图]

　　这些天参与了CSDN论坛的讨论，改变了我以前的一些看法。回头看我以前的东西，我虽对这本书很不满，但我还是按照它的安排在一点点的写；这样就导致了，我过多的在意书中的偏漏，我写的更多是说“这本书怎样”，而偏离了我写这些的初衷――给正在学习数据结构的人一些帮助。 <!-- frame contents --> <!-- /frame contents --> 正像我在前面所说的，虽然现有的教科书都不是很合理，但假如仅仅是抱怨这点，那无异于泼妇骂街。虽然本人的水平连初级都够不上，但至少先从我做一点尝试，以后这门课的教授方法必将一点点趋于合理。
　　
　　 　　因此，后面不在按照书上的次序，将本着“实际应用（算法）决定数据结构”的思想来讲解，常见教科书上有的，基本不再重点叙述（除了重点，例如AVL树的平衡旋转），――因此，在看本文的同时，一定要有一本教科书。这只是一个尝试，希望大家多提宝贵意见。
　　
　　 　　树
　　 　　因为现实世界中存在这“树”这种结构――族谱、等级制度、目录分类等等，而为了研究这类问题，必须能够将树储存，而如何储存将取决于所需要的操作。这里有个问题，是否答应存在空树。有些书认为树都是非空的，因为树表示的是一种现实结构，而0不是自然数；我用过的教科书都是说可以有空树，当然是为了和二叉树统一。这个没有什么原则上的差别，反正就是一种习惯。
　　
　　 　　二叉树
　　 　　二叉树可以说是人们假想的一个模型，因此，答应有空的二叉树是无争议的。二叉树是有序的，左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定，是因为人们赋予了左孩子和右孩子不同的意义，在二叉树的各种应用中，你将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书，你会发现一个有趣的现象：在二叉树这里，基本操作有计算树高、各种遍历，就是没有插入、删除――那树是怎么建立起来的？其实这很好理解，对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应用中，才会有插入删除操作。
　　 更多内容请看C/C++技术专题  数据结构  数据结构教程专题，或 　　节点结构
　　 　　数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲，或者是资源紧张，建议附加一个双亲指针，这将会给很多算法带来方便，尤其是在这个“空间换时间”的时代。
　　
　　 　　template
　　
　　 　　strUCtBTNode
　　
　　 　　{
　　
　　 <!-- frame contents --> <!-- /frame contents --> 　　BTNode(Tdata=T(),BTNode*left=NULL,BTNode*right=NULL,BTNode*parent=NULL)
　　 　　
　　 　　:data(data),left(left),right(right),parent(parent){}
　　 　　
　　 　　BTNode*left,*right,*parent;
　　 　　
　　 　　Tdata;
　　 　　
　　 　　};
　　
　　 　　基本的二叉树类
　　 　　template
　　 　　
　　 　　classBTree
　　 　　
　　 　　{
　　
　　 　　public:
　　 　　
　　 　　BTree(BTNode*root=NULL):root(root){}
　　 　　
　　 　　~BTree(){MakeEmpty();}
　　 　　
　　 　　voidMakeEmpty(){destroy(root);root=NULL;}
　　
　　 　　protected:
　　 　　
　　 　　BTNode*root；
　　 　　
　　 　　private:
　　 　　
　　 　　voiddestroy(BTNode*p)
　　 　　
　　 　　{
　　 　　
　　 　　if(p)
　　 　　
　　 　　{
　　 　　
　　 　　destroy(p->left);
　　 　　
　　 　　destroy(p->right);
　　 　　
　　 　　deletep;
　　 　　
　　 　　}
　　 　　
　　 　　}
　　 　　
　　 　　}
　　
　　 　　二叉树的遍历
　　 　　基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？到了后面才明白，这是不同的应用需要的。例如，判定两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。
　　
　　 　　
　　 　　实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性，这些遍历方法能很清楚的表达。
　　 更多内容请看C/C++技术专题  数据结构  数据结构教程专题，或 　　1.前序遍历
　　
　　 　　public:
　　 　　
　　 　　voidPreOrder(void(*visit)(T&data)=print){PreOrder(root,visit);}
　　 　　
　　 　　private:
　　 　　
　　 　　voidPreOrder(BTNode*p,void(*visit)(T&data))
　　 　　
　　 　　{
　　 　　
　　 <!-- frame contents --> <!-- /frame contents --> 　　if(p){visit(p->data);PreOrder(p->left,visit);PreOrder(p->right,visit);}
　　 　　
　　 　　}
　　 　　
　　 　　2.中序遍历
　　 　　
　　 　　public:
　　 　　
　　 　　voidInOrder(void(*visit)(T&data)=print){InOrder(root,visit);}
　　 　　
　　 　　private:
　　
　　 　　voidInOrder(BTNode*p,void(*visit)(T&data))
　　
　　 　　{
　　
　　 　　if(p){InOrder(p->left,visit);visit(p->data);InOrder(p->right,visit);}
　　
　　 　　}
　　
　　 　　3.后序遍历
　　
　　 　　public:
　　
　　 　　voidPostOrder(void(*visit)(T&data)=print){PostOrder(root,visit);}
　　
　　 　　private:
　　
　　 　　voidPostOrder(BTNode*p,void(*visit)(T&data))
　　
　　 　　{
　　
　　 　　if(p){PostOrder(p->left,visit);PostOrder(p->right,visit);visit(p->data);}
　　
　　 　　}
　　
　　 　　4.层次遍历
　　 　　
　　 　　voidLevelOrder(void(*visit)(T&data)=print)
　　
　　 　　{
　　 　　
　　 　　queue*>a;BTNode*p=root;//记得#include
　　 　　
　　 　　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:
　　 　　
　　 　　staticvoidprint(T&data){cout<　　
　　 　　5.不用栈的非递归中序遍历
　　 更多内容请看C/C++技术专题  数据结构  数据结构教程专题，或 　　
　　 　　当有parent指针时，可以不用栈实现非递归的中序遍历，书上提到了有这种方法，但没给出例程。
　　 　　
　　 　　public:
　　 　　
　　 　　BTNode*next()
　　 　　
　　 　　{
　　 　　
　　 　　if(!current)returnNULL;
　　 　　
　　 <!-- frame contents --> <!-- /frame contents --> 　　if(current->right){current=current->right;while(current->left)current=current->left;}
　　 　　
　　 　　else
　　 　　
　　 　　{
　　 　　
　　 　　BTNode*y=current->parent;
　　 　　
　　 　　while(y&¤t==y->right){current=y;y=y->parent;}
　　 　　
　　 　　current=y;
　　 　　
　　 　　}
　　 　　
　　 　　returncurrent;
　　
　　 　　
　　 　　}
　　 　　
　　 　　private:
　　 　　
　　 　　BTNode*current;
　　 　　
　　 　　上面的函数能使current指针向前移动一个位置，假如要遍历整棵二叉树，需要使current指向中序序列的第一个节点，例如下面的成员函数：
　　 　　
　　 　　public:
　　 　　
　　 　　voidfirst(){current=root;while(current->left)current=current->left;}
　　 更多内容请看C/C++技术专题  数据结构  数据结构教程专题，或