1、二叉树上的操作

均是C++实现先根序创建二叉树及其其它方法

我认为在二叉树的创建方法和遍历以外，以下方法值得我们关注：

public:intsize()const;//求结点个数intheight()const;//求树的高度BinTreeNode<Type>*root_1()const;//求根节点BinTreeNode<Type>*leftChild(BinTreeNode<Type>*cur)const;//求当前结点的左孩子BinTreeNode<Type>*rightChild(BinTreeNode<Type>*cur)const;//求当前结点的右孩子BinTreeNode<Type>*find(constType&key)const;//查找当前结点BinTreeNode<Type>*parent(BinTreeNode<Type>*cur)const;//查找当前结点的父结点voidmakeEmpty();//将二叉树置空boolequal(constBinTree<Type>&t)const;//两个二叉树是否相同的比较BinTreeNode<Type>*copy(BinTreeNode<Type>*t)const;//拷贝构造函数的方法，复制一个二叉树

2、方法一一实现：

(1)、求结点个数

template<typenameType>intBinTree<Type>::size(BinTreeNode<Type>*t)const{if(t==NULL){return0;}returnsize(t->leftChild)+size(t->rightChild)+1;}

(2)、求树的高度

template<typenameType>intBinTree<Type>::height(BinTreeNode<Type>*t)const{if(t==NULL){return0;}intleftHeight=height(t->leftChild);intrightHeight=height(t->rightChild);return(leftHeight>rightHeight?leftHeight:rightHeight)+1;}

(3)、查找当前结点

template<typenameType>BinTreeNode<Type>*BinTree<Type>::find(constType&key,BinTreeNode<Type>*t)const{if(t==NULL){returnNULL;}if(t->data==key){returnt;}BinTreeNode<Type>*p=find(key,t->leftChild);if(p!=NULL){returnp;}returnfind(key,t->rightChild);}

(4)、查找当前结点的父结点

template<typenameType>BinTreeNode<Type>*BinTree<Type>::parent(BinTreeNode<Type>*cur,BinTreeNode<Type>*t)const{if(t==NULL||cur==NULL||cur==t){returnNULL;}if(t->leftChild==cur||t->rightChild==cur){returnt;}//思路：利用父的孩子节点和当前节点比较BinTreeNode<Type>*p=parent(cur,t->leftChild);if(p!=NULL){returnp;}returnparent(cur,t->rightChild);}

(5)、将二叉树置空

template<typenameType>voidBinTree<Type>::makeEmpty(BinTreeNode<Type>*t){if(t!=NULL){makeEmpty(t->leftChild);makeEmpty(t->rightChild);deletet;}}

(6)、两个二叉树是否相同的比较

template<typenameType>boolBinTree<Type>::equal(BinTreeNode<Type>*t,BinTreeNode<Type>*t1)const{if(t==NULL&&t1==NULL){//取反判断与这个是一个道理returntrue;}if(t!=NULL&&t1!=NULL&&t->data==t1->data&&equal(t->leftChild,t1->leftChild)&&equal(t->rightChild,t1->rightChild)){returntrue;}else{returnfalse;}}

(7)、拷贝一个二叉树

template<typenameType>BinTreeNode<Type>*BinTree<Type>::copy(BinTreeNode<Type>*t)const{BinTreeNode<Type>*tmp;if(t==NULL){returnNULL;}else{tmp=newBinTreeNode<Type>(t->data);tmp->leftChild=copy(t->leftChild);tmp->rightChild=copy(t->rightChild);}returntmp;}

以上的这些方法都是利用二叉树的性质递归实现，比较好想清楚，就不做解释了，实在有问题，画画图就会好很多。

3、二叉树的所有方法，测试，及测试结果如下：

(1)、所有关于二叉树的代码：

#ifndef_BIN_TREE_H_#define_BIN_TREE_H_#include<iostream>#include<stack>//非递归遍历引入栈#include<queue>//层次遍历引入队列usingnamespacestd;template<typenameType>//为的是声明友元类，调用BinTreeNode<Type>的私有数据classBinTree;template<typenameType>//BinTreeNode类classBinTreeNode{friendclassBinTree<Type>;public:BinTreeNode():data(Type()),leftChild(NULL),rightChild(NULL){}BinTreeNode(Typevalue,BinTreeNode<Type>*left=NULL,BinTreeNode<Type>*right=NULL):data(value),leftChild(left),rightChild(right){}~BinTreeNode(){}private:Typedata;BinTreeNode*leftChild;BinTreeNode*rightChild;};///////////////////////////////////////////////////////////////////////////////template<typenameType>//BinTree类classBinTree{public:BinTree():root(NULL){}BinTree(Typeref):root(NULL),refval(ref){}BinTree(constBinTree&t){root=copy(t.root);//调用拷贝方法}~BinTree(){makeEmpty();//析构函数这里将二叉树置空root=NULL;}public://创建二叉树voidcreateBinTree();voidcreateBinTree(constchar*str);voidcreateBinTree(constchar*VLR,constchar*LVR,intn);voidcreateBinTree_1(constchar*LVR,constchar*LRV,intn);public://递归遍历voidprevOrder()const;voidinOrder()const;voidendOrder()const;public://各种方法的声明intsize()const;intheight()const;BinTreeNode<Type>*root_1()const;//以下的三个方法比较简单，就不在进行调用保护方法了；BinTreeNode<Type>*leftChild(BinTreeNode<Type>*cur)const;BinTreeNode<Type>*rightChild(BinTreeNode<Type>*cur)const;BinTreeNode<Type>*find(constType&key)const;BinTreeNode<Type>*parent(BinTreeNode<Type>*cur)const;voidmakeEmpty();boolequal(constBinTree<Type>&t)const;BinTreeNode<Type>*copy(BinTreeNode<Type>*t)const;public://非递归遍历voidprevOrder_1()const;voidinOrder_1()const;voidendOrder_1()const;voidlevelOrder()const;//puublic:供外界提供的接口，////////////////////////////////////////////////////////////////////////////////protected://protected:供自己函数内部调用，写保护方法voidprevOrder_1(BinTreeNode<Type>*t)const;voidinOrder_1(BinTreeNode<Type>*t)const;voidendOrder_1(BinTreeNode<Type>*t)const;voidlevelOrder(BinTreeNode<Type>*t)const;protected:intsize(BinTreeNode<Type>*t)const;intheight(BinTreeNode<Type>*t)const;BinTreeNode<Type>*find(constType&key,BinTreeNode<Type>*t)const;BinTreeNode<Type>*parent(BinTreeNode<Type>*cur,BinTreeNode<Type>*t)const;voidmakeEmpty(BinTreeNode<Type>*t);boolequal(BinTreeNode<Type>*t,BinTreeNode<Type>*t1)const;protected:voidprevOrder(BinTreeNode<Type>*t)const;voidinOrder(BinTreeNode<Type>*t)const;voidendOrder(BinTreeNode<Type>*t)const;protected:voidcreateBinTree(BinTreeNode<Type>*&t);BinTreeNode<Type>*createBinTree_1();voidcreateBinTree(constchar*&str,BinTreeNode<Type>*&t);BinTreeNode<Type>*createBinTree_1(constchar*&str);voidcreateBinTree(BinTreeNode<Type>*&t,constchar*VLR,constchar*LVR,intn);voidcreateBinTree_1(BinTreeNode<Type>*&t,constchar*LVR,constchar*LRV,intn);//以上都只是在类内声明；private:BinTreeNode<Type>*root;Typerefval;//'#'};///////////////////////////////////////////////////////////////////////////////template<typenameType>//类外实现公有方法的调用voidBinTree<Type>::createBinTree(){//创建二叉树//createBinTree(root);root=createBinTree_1();}template<typenameType>voidBinTree<Type>::prevOrder()const{//先序递归遍历cout<<"先根序如下:"<<endl;prevOrder(root);}template<typenameType>voidBinTree<Type>::inOrder()const{//中序递归遍历cout<<"中根序如下:"<<endl;inOrder(root);}template<typenameType>voidBinTree<Type>::endOrder()const{//后序递归遍历cout<<"后根序如下:"<<endl;endOrder(root);}template<typenameType>voidBinTree<Type>::createBinTree(constchar*str){//创建二叉树//createBinTree(str,root);root=createBinTree_1(str);}template<typenameType>intBinTree<Type>::size()const{//求结点个数returnsize(root);}template<typenameType>intBinTree<Type>::height()const{//求树的高度returnheight(root);}template<typenameType>BinTreeNode<Type>*BinTree<Type>::root_1()const{//求根节点returnroot;}template<typenameType>BinTreeNode<Type>*BinTree<Type>::leftChild(BinTreeNode<Type>*cur)const{//求当前结点的左孩子returncur->leftChild;}template<typenameType>BinTreeNode<Type>*BinTree<Type>::rightChild(BinTreeNode<Type>*cur)const{//求当前结点的右孩子returncur->rightChild;}template<typenameType>BinTreeNode<Type>*BinTree<Type>::find(constType&key)const{//查找当前结点returnfind(key,root);}template<typenameType>BinTreeNode<Type>*BinTree<Type>::parent(BinTreeNode<Type>*cur)const{//查找当前结点的父结点returnparent(cur,root);}template<typenameType>voidBinTree<Type>::makeEmpty(){//将二叉树置空makeEmpty(root);}template<typenameType>boolBinTree<Type>::equal(constBinTree<Type>&t)const{//两个二叉树是否相同的比较returnequal(t.root,root);}template<typenameType>voidBinTree<Type>::prevOrder_1()const{//非递归先序prevOrder_1(root);}template<typenameType>voidBinTree<Type>::inOrder_1()const{//非递归中序inOrder_1(root);}template<typenameType>voidBinTree<Type>::endOrder_1()const{//非递归后序endOrder(root);}template<typenameType>voidBinTree<Type>::levelOrder()const{//层次遍历levelOrder(root);}template<typenameType>voidBinTree<Type>::createBinTree(constchar*VLR,constchar*LVR,intn){//创建二叉树createBinTree(root,VLR,LVR,n);}template<typenameType>voidBinTree<Type>::createBinTree_1(constchar*LVR,constchar*LRV,intn){//创建二叉树createBinTree_1(root,LVR,LRV,n);}//////////////////////////////////////////////////////////////////////////////////////////template<typenameType>//以下的都是写保护的方法，供自己使用voidBinTree<Type>::createBinTree_1(BinTreeNode<Type>*&t,constchar*LVR,constchar*LRV,intn){//中序和后序创建二叉树if(n==0){t=NULL;return;}intk=0;while(LVR[k]!=LRV[n-1]){k++;}t=newBinTreeNode<Type>(LVR[k]);createBinTree_1(t->rightChild,LVR+k+1,LRV+k,n-k-1);createBinTree_1(t->leftChild,LVR,LRV,k);}template<typenameType>voidBinTree<Type>::createBinTree(BinTreeNode<Type>*&t,constchar*VLR,constchar*LVR,intn){//先序和中序创建二叉树if(n==0){t=NULL;return;}intk=0;while(LVR[k]!=VLR[0]){k++;}t=newBinTreeNode<Type>(LVR[k]);createBinTree(t->leftChild,VLR+1,LVR,k);createBinTree(t->rightChild,VLR+k+1,LVR+k+1,n-k-1);}template<typenameType>voidBinTree<Type>::levelOrder(BinTreeNode<Type>*t)const{//层次遍历queue<BinTreeNode<Type>*>qu;BinTreeNode<Type>*p;if(t!=NULL){qu.push(t);while(!qu.empty()){p=qu.front();qu.pop();cout<<p->data<<"";if(p->leftChild){qu.push(p->leftChild);}if(p->rightChild){qu.push(p->rightChild);}}}}typedefenum{L,R}Tag;template<typenameType>classstkNode{public:stkNode(BinTreeNode<Type>*p=NULL):ptr(p),tag(L){}public:BinTreeNode<Type>*ptr;Tagtag;//LR};template<typenameType>voidBinTree<Type>::endOrder_1(BinTreeNode<Type>*t)const{//非递归后序stkNode<Type>n;stack<stkNode<Type>>st;BinTreeNode<Type>*p=t;do{while(p!=NULL){n.ptr=p;n.tar=L;st.push(n);p=p->leftChild;}boolisRun=true;while(isRun&&!st.empty()){n=st.top();st.pop();switch(n.tag){caseL:p=n.ptr;n.tag=R;st.push(n);p=p->rightChild;isRun=false;break;caseR:cout<<n.ptr->data<<"";break;}}}while(!st.empty());//不用p1=NULL,因为当栈空时，最后一个节点刚好被访问完成。}template<typenameType>voidBinTree<Type>::inOrder_1(BinTreeNode<Type>*t)const{//非递归中序stack<BinTreeNode<Type>*>st;BinTreeNode<Type>*p=t;do{while(p!=NULL){st.push(p);p=p->leftChild;}if(!st.empty()){p=st.top();st.pop();cout<<p->data<<"";p=p->rightChild;}//中序遍历时，当root出栈时，此时占空，}while(p!=NULL||!st.empty());//为根的时候右边还要入栈。}template<typenameType>voidBinTree<Type>::prevOrder_1(BinTreeNode<Type>*t)const{//非递归先序stack<BinTreeNode<Type>*>st;BinTreeNode<Type>*tmp;if(t!=NULL){st.push(t);while(!st.empty()){tmp=st.top();st.pop();cout<<tmp->data<<"";if(tmp->rightChild){st.push(tmp->rightChild);}if(tmp->leftChild){st.push(tmp->leftChild);}}}}template<typenameType>BinTreeNode<Type>*BinTree<Type>::copy(BinTreeNode<Type>*t)const{//拷贝函数BinTreeNode<Type>*tmp;if(t==NULL){returnNULL;}else{tmp=newBinTreeNode<Type>(t->data);tmp->leftChild=copy(t->leftChild);tmp->rightChild=copy(t->rightChild);}returntmp;}template<typenameType>boolBinTree<Type>::equal(BinTreeNode<Type>*t,BinTreeNode<Type>*t1)const{//两个二叉树是否相同的比较if(t==NULL&&t1==NULL){//取反判断与这个是一个道理returntrue;}if(t!=NULL&&t1!=NULL&&t->data==t1->data&&equal(t->leftChild,t1->leftChild)&&equal(t->rightChild,t1->rightChild)){returntrue;}else{returnfalse;}}template<typenameType>voidBinTree<Type>::makeEmpty(BinTreeNode<Type>*t){//将二叉树置空if(t!=NULL){makeEmpty(t->leftChild);makeEmpty(t->rightChild);deletet;}}template<typenameType>BinTreeNode<Type>*BinTree<Type>::parent(BinTreeNode<Type>*cur,BinTreeNode<Type>*t)const{//查找当前结点的父结点if(t==NULL||cur==NULL||cur==t){returnNULL;}if(t->leftChild==cur||t->rightChild==cur){returnt;}//思路：利用父的孩子节点和当前节点比较BinTreeNode<Type>*p=parent(cur,t->leftChild);if(p!=NULL){returnp;}returnparent(cur,t->rightChild);}template<typenameType>BinTreeNode<Type>*BinTree<Type>::find(constType&key,BinTreeNode<Type>*t)const{//查找当前结点if(t==NULL){returnNULL;}if(t->data==key){returnt;}BinTreeNode<Type>*p=find(key,t->leftChild);if(p!=NULL){returnp;}returnfind(key,t->rightChild);}template<typenameType>intBinTree<Type>::height(BinTreeNode<Type>*t)const{//求树的高度if(t==NULL){return0;}intleftHeight=height(t->leftChild);intrightHeight=height(t->rightChild);return(leftHeight>rightHeight?leftHeight:rightHeight)+1;}template<typenameType>intBinTree<Type>::size(BinTreeNode<Type>*t)const{//求结点个数if(t==NULL){return0;}returnsize(t->leftChild)+size(t->rightChild)+1;}template<typenameType>BinTreeNode<Type>*BinTree<Type>::createBinTree_1(constchar*&str){//创建二叉树BinTreeNode<Type>*t;if(refval==*str){t=NULL;}else{t=newBinTreeNode<Type>(*str);t->leftChild=createBinTree_1(++str);t->rightChild=createBinTree_1(++str);}returnt;}template<typenameType>voidBinTree<Type>::createBinTree(constchar*&str,BinTreeNode<Type>*&t){//创建二叉树if(*str==refval){t=NULL;}else{t=newBinTreeNode<Type>(*str);createBinTree(++str,t->leftChild);//前加，后加不一样！！！在这里，就是传引用，保证每次字符串都是往后走的createBinTree(++str,t->rightChild);}}template<typenameType>BinTreeNode<Type>*BinTree<Type>::createBinTree_1(){//创建二叉树TypecreateData;cin>>createData;BinTreeNode<Type>*t;if(refval==createData){t=NULL;}else{t=newBinTreeNode<Type>(createData);t->leftChild=createBinTree_1();t->rightChild=createBinTree_1();}returnt;}template<typenameType>voidBinTree<Type>::endOrder(BinTreeNode<Type>*t)const{//后序递归遍历if(t==NULL){return;}else{endOrder(t->leftChild);endOrder(t->rightChild);cout<<t->data<<"";}}template<typenameType>voidBinTree<Type>::inOrder(BinTreeNode<Type>*t)const{//中序递归遍历if(t==NULL){return;}else{inOrder(t->leftChild);cout<<t->data<<"";inOrder(t->rightChild);}}template<typenameType>voidBinTree<Type>::prevOrder(BinTreeNode<Type>*t)const{//先序递归遍历if(t==NULL){return;}else{cout<<t->data<<"";prevOrder(t->leftChild);prevOrder(t->rightChild);}}//根据先根序创建二叉树template<typenameType>voidBinTree<Type>::createBinTree(BinTreeNode<Type>*&t){//创建二叉树TypecreateData;cin>>createData;if(refval==createData){t=NULL;}else{t=newBinTreeNode<Type>(createData);createBinTree(t->leftChild);createBinTree(t->rightChild);}}#endif

以上代码我采用折叠的方式进行写的。类外公有调用下面紧跟保护方法的实现；

(2)、测试代码

#include"BinTree.h"//ABC##DE##F##G#H##/*先根序如下:ABCDEFGH中根序如下:CBEDFAGH后根序如下:CEFDBHGA*/intmain(void){//char*VLR="ABCDEFGH";//char*LVR="CBEDFAGH";//char*LRV="CEFDBHGA";//BinTree<char>bt;//对象初始化不写'#'；//intn=strlen(VLR);//bt.createBinTree(VLR,LVR,n);//在这里创建二叉树不用'#'结束，因为是由先序和中序创建，不看结束标志'#';//bt.createBinTree_1(LVR,LRV,n);//bt.prevOrder();//cout<<endl;//bt.createBinTree(VLR,LRV,n);不能创建/*BinTree<char>bt('#');char*str="ABC##DE##F##G#H##";//char*str="ABC##DE###G#H##";bt.createBinTree(str);BinTree<char>bt1(bt);bt1.levelOrder();cout<<endl;*//*//st.createBinTree();BinTree<char>bt('#');BinTree<char>bt1('#');char*str="ABC##DE##F##G#H##";bt.createBinTree(str);bt1.createBinTree(str);//构建的是一颗空树,引用传递构建，原先字符串已经为空！if(bt.equal(bt1)){cout<<"相等"<<endl;}else{cout<<"不相等"<<endl;}*/BinTree<char>bt('#');char*str="ABC##DE##F##G#H##";bt.createBinTree(str);cout<<bt.size()<<endl;cout<<bt.height()<<endl;BinTreeNode<char>*p=bt.find('H');BinTreeNode<char>*t=bt.find('G');printf("%p\n",t);BinTreeNode<char>*q=bt.parent(p);printf("%p\n",q);bt.prevOrder();cout<<endl;bt.inOrder();cout<<endl;bt.endOrder();cout<<endl;return0;}

这是所有测试要用的代码，在编写时，写一个方法测试一个，将测试过的就注释起来了；

(3)、部分测试结果

至于其它的测试结果就不在给出了，有兴趣可以在测测其它的方法。