数据结构学习（C++）之二叉树

《数据结构学习（C++）之二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构学习（C++）之二叉树树　　因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等，而为了研究这类问题，必须能够将树储存，而如何储存将取决于所需要的操作。这里有个问题，是否允许存在空树。有些书认为树都是非空的，因为树表示的是一种现实结构，而0不是自然数；我用过的教科书都是说可以有空树，当然是为了和二叉树统一。这个没有什么原则上的差别，反正就是一种习惯。　　二叉树　　二叉树可以说是人们假想的一个模型，因此，允许有空的二叉树是无争议的。二叉树是有序的，左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定，是因为人们赋予了左孩

2、子和右孩子不同的意义，在二叉树的各种应用中，你将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书，你会发现一个有趣的现象：在二叉树这里，基本操作有计算树高、各种遍历，就是没有插入、删除——那树是怎么建立起来的？其实这很好理解，对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应用中，才会有插入删除操作。　　节点结构　　数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲，或者是资源紧张，建议附加一个双亲指针，这将会给很多算法带来方便，尤其是在这个“空间换时间”的时代。templates

3、tructBTNode{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;};　　基本的二叉树类templateclassBTree{public:BTree(BTNode*root=NULL):root(root){}~BTree(){Make

4、Empty();}voidMakeEmpty(){destroy(root);root=NULL;}protected:BTNode*root；private:voiddestroy(BTNode*p){if(p){destroy(p->left);destroy(p->right);deletep;}}}　　二叉树的遍历　　基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？到了后面才明白，这是不同的应用需要的。例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；而删除二叉树，

5、必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。　　实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性，这些遍历方法能很清晰的表达。　　1.前序遍历public:voidPreOrder(void(*visit)(T&data)=print){PreOrder(root,visit);}private:voidPreOrder(BTNode*p,void(*visit)(T&data)){if(p){visit(p->data);P

6、reOrder(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:voidPostOrde

7、r(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;//记得#in

8、cludewhile(p){visit(p->data);if(p->left)a.push(p->left