二叉树及其上基本操作

《二叉树及其上基本操作》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include#defineN10;templatestructBinTreeNode{//二叉树结点类定义Tdata;BinTreeNode*left,*right;BinTreeNode():leftChild(NULL),rightChild(NULL){}BinTreeNode(T&x,BinTreeNode*l=NULL,BinTreeNode*r=NULL):data(x),left(l),right(r){}};templateclassBinTree{public

2、:BinTree():root(NULL){}BinTree(Tvalue=0):RefValue(value),root(NULL){}BinTree(BinTree&s);~BinTree(){Destroy(root);}BinTreeNodeGetroot()const{returnroot;}//取根boolIsempty(){return(root==NULL)?true:false;}BinTreeNode*Parent(BinTreeNode*current);//寻找父结点BinTreeNode*LeftChild(BinTreeNode

3、*current)//寻找左右子结点{return(current!=NULL)?current->left:NULL;}BinTreeNode*RightChild(BinTreeNode*current){return(current!=NULL)?current->right:NULL;}BinTreeNode*Setleft(BinTreeNode*current){left=current;}//设置左右子结点BinTreeNode*Setright(BinTreeNode*current){right=current;}BinTre

4、eNode*Create();//创建树voidPreorder(BinTreeNode*t);//先根遍历voidInorder(BinTreeNode*t);//中根遍历voidPostorder(BinTreeNode*t);//后根遍历boolFind(T&x);//查找符合数据域条件的结点voidDestroy(BinTreeNode&subtree);//删除子树voidDel(BinTreeNode*p);voidout(BinTreeNode*t);//以表格形式输出二叉树private:BinTreeNode*root;

5、TRefValue;};templateBinTreeNode*BinTree::Parent(BinTreeNode*current)//父结点{if(current==NULL

6、

7、Isempty())returnNULL;if(root->left==current

8、

9、root->right==current)returnroot;BinTreeNode*q;q=Parent(root->left);if(q!=NULL)returnq;returnq=Parent(root->right);}templateboolBinT

10、ree::Find(BinTreeNode*t,T&x)//符合数据域条件的结点{if(Isempty())returnfalse;if(t->data==x)returntrue;BinTreeNode*q;q=Find(t->left,x);if(q!=NULL)returnq;returnq=Find(t->right,x);}templatevoidBinTree::Destroy(BinTreeNode&subtree)//删除节点及子树{if(subtree==NULL)exit(1);if(subtree==root){Del

11、(root);root=NULL;exit(1);}BinTreeNode*p==subtree;BinTreeNode*q;q=Parent(p);if(q->left==p)q->left=NULL;if(q->right==p)q->right=NULL;Del(p);}templatevoidBinTree::Del(BinTreeNode*p){if(p==NULL)exit(0);Del(p->le