數(shù)據(jù)結(jié)構(gòu)-二叉樹基本操作源代碼

數(shù)據(jù)結(jié)構(gòu)二叉樹基本操作(1).//

對二叉樹的基本操作的類模板封裝//------------------------------------------------------------------------------------------------------------------------#include<iostream>usingnamespacestd;//------------------------------------------------------------------------------------------------------------------------//定義二叉樹的結(jié)點(diǎn)類型

BTNode,

其中包含數(shù)據(jù)域、左孩子，右孩子結(jié)點(diǎn)。template<classT>structBTNode{Tdata;BTNode*lchild;BTNode*rchild;

//數(shù)據(jù)域//指向左子樹的指針//指向右子樹的指針};//------------------------------------------------------------------------------------------------------------------------//CBinary的類模板template<classT>classBinaryTree{BTNode<T>*BT;public:BinaryTree(){BT=NULL;}

//構(gòu)造函數(shù)

,將根結(jié)點(diǎn)置空~BinaryTree(){clear(BT);}

//調(diào)用

Clear()函數(shù)將二叉樹銷毀voidClearBiTree(){clear(BT);BT=NULL;};

//銷毀一棵二叉樹voidCreateBiTree(Tend);

//創(chuàng)建一棵二叉樹，

end

為空指針域標(biāo)志boolIsEmpty();intBiTreeDepth();boolRootValue(T&e);

//判斷二叉樹是否為空//計(jì)算二叉樹的深度//若二叉樹不為空用

e返回根結(jié)點(diǎn)的值，函數(shù)返回

true，否則函數(shù)返回

falseBTNode<T>*GetRoot(); //二叉樹不為空獲取根結(jié)點(diǎn)指針，否則返回 NULLboolAssign(Te,Tvalue); //找到二叉樹中值為 e的結(jié)點(diǎn)，并將其值修改為 value。TGetParent(Te);//若二叉樹不空且e是二叉樹中的一個(gè)結(jié)點(diǎn)那么返回其雙親結(jié)點(diǎn)值TGetLeftChild(Te);//獲取左孩子結(jié)點(diǎn)值TGetRightChild(Te);//獲取右孩子結(jié)點(diǎn)值TGetLeftSibling(Te);//獲取左兄弟的結(jié)點(diǎn)值Trightsibling(BTNode<T>*p,Te);TGetRightSibling(Te);//獲取右孩子的結(jié)點(diǎn)值boolInsertChild(BTNode<T>*p,BTNode<T>*c,intRL);//插入操作boolDeleteChild(BTNode<T>*p,intRL);//刪除操作voidPreTraBiTree();//遞歸算法：先序遍歷二叉樹voidInTraBiTree();//遞歸算法：中序遍歷二叉樹voidPostTraBiTree();//遞歸算法：后序遍歷二叉樹voidPreTraBiTree_N();//非遞歸算法：先序遍歷二叉樹voidInTraBiTree_N();//非遞歸算法：中序遍歷二叉樹voidLevelTraBiTree();//利用隊(duì)列層次遍歷二叉樹intLeafCount();//計(jì)算葉子結(jié)點(diǎn)的個(gè)數(shù)BTNode<T>*SearchNode(Te);//尋找到結(jié)點(diǎn)值為e的結(jié)點(diǎn)，返回指向結(jié)點(diǎn)的指針voidDisplayBTreeShape(BTNode<T>*bt,intlevel=1);};//二叉樹的樹形顯示算法template<classT>voidBinaryTree<T>::DisplayBTreeShape(BTNode<T>*bt,intlevel){if(bt)//空二叉樹不顯示{DisplayBTreeShape(bt->rchild,level+1);// 顯示右子樹cout<<endl;//顯示新行for(inti=0;i<level-1;i++)cout<<" ";//確保在第 level列顯示節(jié)點(diǎn)cout<<bt->data;//顯示節(jié)點(diǎn)DisplayBTreeShape(bt->lchild,level+1);// 顯示左子樹}//if}//DisplayBTreetemplate<classT>staticintclear(BTNode<T>*bt){

//銷毀一棵二叉樹if(bt)//根結(jié)點(diǎn)不空{(diào)clear(bt->lchild);clear(bt->rchild);

//遞歸調(diào)用//遞歸調(diào)用

Clear()Clear()

函數(shù)銷毀左子樹函數(shù)銷毀右子樹cout<<"釋放了指針 "<<bt<<"所指向的空間。 "<<endl;delete bt; //釋放當(dāng)前訪問的根結(jié)點(diǎn)}return0;}template<classT>voidBinaryTree<T>::CreateBiTree(Tend){ //創(chuàng)建一棵二叉樹：先序序列的順序輸入數(shù)據(jù)，cout<<"請按先序序列的順序輸入二叉樹 ,-1BTNode<T>*p;

end為結(jié)束的標(biāo)志為空指針域標(biāo)志： "<<endl;Tx;cin>>x; //輸入根結(jié)點(diǎn)的數(shù)據(jù)if(x==end)return; //end表示指針為空，說明樹為空p=newBTNode<T>;// 申請內(nèi)存if(!p){cout<<"申請內(nèi)存失?。?"<<endl;exit(-1);//申請內(nèi)存失敗退出}p->data=x;p->lchild=NULL;p->rchild=NULL;BT=p;//根結(jié)點(diǎn)create(p,1,end);//創(chuàng)建根結(jié)點(diǎn)左子樹，1為標(biāo)志，表示左子樹create(p,2,end);//創(chuàng)建根結(jié)點(diǎn)右子樹，2為標(biāo)志，表示右子樹}template<classT>staticintcreate(BTNode<T>*p,intk,Tend){//

靜態(tài)函數(shù)，創(chuàng)建二叉樹，

k為創(chuàng)建左子樹還是右子樹的標(biāo)志，

end

為空指針域的標(biāo)志BTNode<T>*q;Tx;cin>>x;if(x!=end){

//先序順序輸入數(shù)據(jù)q=newBTNode<T>;q->data=x;q->lchild=NULL;q->rchild=NULL;if(k==1)p->lchild=q; //q為左子樹if(k==2)p->rchild=q;//p 為右子樹create(q,1,end); //遞歸創(chuàng)建左子樹create(q,2,end); //遞歸創(chuàng)建右子樹}return0;}template<classT>boolBinaryTree<T>::IsEmpty(){//判斷二叉樹是否為空if(BT==NULL)returntrue;// 樹根結(jié)點(diǎn)為空，說明樹為空returnfalse;}template<classT>intBinaryTree<T>::BiTreeDepth(){//利用遞歸算法計(jì)算樹的深度BTNode<T>*bt=BT;// 樹根結(jié)點(diǎn)intdepth=0;//開始的時(shí)候數(shù)的深度初始化為 0if(bt)//如果樹不為空Depth(bt,1,depth);returndepth;}template<classT>staticintDepth(BTNode<T>*p,intlevel,int&depth){//這個(gè)函數(shù)由BiTreeDepth()函數(shù)調(diào)用完成樹的深度的計(jì)算//其中p是根結(jié)點(diǎn)，Level是層，depth用來返回樹的深度if(level>depth)depth=level;if(p->lchild)Depth(p->lchild,level+1,depth);// 遞歸的遍歷左子樹， 并且層數(shù)加 1if(p->rchild) Depth(p->rchild,level+1,depth);// 遞歸的遍歷右子樹，并且層數(shù)加1return0;}template<classT>boolBinaryTree<T>::RootValue(T&e){//

若二叉樹不為空用

e返回根結(jié)點(diǎn)的值，函數(shù)返回

true，否則函數(shù)返回

falseif(BT!=NULL){

//判斷二叉樹是否為空e=BT->data;//若不空，則將根結(jié)點(diǎn)的數(shù)據(jù)賦值給 ereturntrue;//操作成功，返回

true}returnfalse;//

二叉樹為空，返回

false}template<classT>BTNode<T>*BinaryTree<T>::GetRoot(){//獲取根信息returnBT;//返回根結(jié)點(diǎn)的指針，若二叉樹為空那么返回 NULL}template<classT>boolBinaryTree<T>::Assign(Te,Tvalue){//結(jié)點(diǎn)賦值if(SearchNode(e)!=NULL){(SearchNode(e))->data=value;returntrue;}returnfalse;}template<classT>TBinaryTree<T>::GetParent(Te){//獲取雙親信息BTNode<T>*Queue[200],*p;intrear,front;rear=front=0;if(BT){Queue[rear++]=BT;while(rear!=front){p=Queue[front++];if(p->lchild&&p->lchild->data==e||p->rchild&&p->rchild->data==e)returnp->data;else{if(p->lchild)Queue[rear++]=p->lchild;if(p->rchild)Queue[rear++]=p->rchild;}}}returnNULL;}template<classT>TBinaryTree<T>::GetRightChild(Te){//如果二叉樹存在， e是二叉樹中的一個(gè)結(jié)點(diǎn)，右子樹存在那么返回右子樹的結(jié)點(diǎn)值，否則返回 0并提示右子樹為空BTNode<T>*p=SearchNode(e);if(p->rchild)returnp->rchild->data;// 右子樹不空，返回右子樹根結(jié)點(diǎn)的值cout<<"結(jié)點(diǎn)"<<e<<"的右子樹為空 "<<endl;return0;}template<classT>TBinaryTree<T>::GetLeftChild(Te){//如果二叉樹存在， e是二叉樹中的一個(gè)結(jié)點(diǎn)，左子樹存在那么返回左子樹的結(jié)點(diǎn)值，否則返回 0并提示左子樹為空BTNode<T>*p=SearchNode(e);if(p->lchild)returnp->lchild->data;cout<<"結(jié)點(diǎn)"<<e<<"的左子樹為空 "<<endl;return0;}template<classT>TBinaryTree<T>::GetLeftSibling(Te){//獲取左兄弟信息if(BT!=NULL){returnleftsibling(BT,e);}else{//二叉樹為空cout<<"二叉樹為空！ "<<endl;return0;}}template<classT>Tleftsibling(BTNode<T>*p,Te){Tq=0;if(p==NULL)return0;else{if(p->rchild){if(p->rchild->data==e){if(p->lchild)returnp->lchild->data;elsereturnNULL;}}q=leftsibling(p->lchild,e);if(q)returnq;q=leftsibling(p->rchild,e);if(q)returnq;}return0;}//------------------------------------------------------------------------------------------------------------------------template<classT>TBinaryTree<T>::GetRightSibling(Te){//獲取右兄弟信息if(BT!=NULL){returnrightsibling(BT,e);}else{//二叉樹為空cout<<"二叉樹為空！ "<<endl;return0;}}template<classT>TBinaryTree<T>::rightsibling(BTNode<T>*p,Te){BTNode<T>*q=SearchNode(e);BTNode<T>*pp;if(q){pp=SearchNode(GetParent(e));if(pp){if(pp->rchild)returnpp->rchild->data;elsereturn0;}elsereturn0;}return0;}template<classT>boolBinaryTree<T>::InsertChild(BTNode<T>*p,BTNode<T>*c,intLR){//插入孩子if(p){if(LR==0){c->rchild=p->lchild;p->lchild=c;}else{c->rchild=p->rchild;p->rchild=c;}returntrue;}returnfalse;//p為空}//------------------------------------------------------------------------------------------------------------------------template<classT>boolBinaryTree<T>::DeleteChild(BTNode<T>*p,intRL){//刪除結(jié)點(diǎn)if(p){if(RL==0){clear(p->lchild);// 釋放p右子樹的所有結(jié)點(diǎn)空間p->lchild=NULL;}else{clear(p->rchild);p->rchild=NULL;}returntrue;//刪除成功}returnfalse;//p為空}//------------------------------------------------------------------------------------------------------------------------template<classT>voidBinaryTree<T>::PreTraBiTree(){//先序遍歷二叉樹cout<<"----------------------------------------------"<<endl;cout<<"先序遍歷二叉樹 :";BTNode<T>*p;p=BT; //根結(jié)點(diǎn)PreTraverse(p);//從根結(jié)點(diǎn)開始先序遍歷二叉樹cout<<endl;cout<<"----------------------------------------------"<<endl;}template<classT>staticintPreTraverse(BTNode<T>*p){if(p!=NULL){cout<<p->data<<''; //輸出結(jié)點(diǎn)上的數(shù)據(jù)PreTraverse(p->lchild); //遞歸的調(diào)用前序遍歷左子樹PreTraverse(p->rchild); //遞歸的調(diào)用前序遍歷右子樹}return0;}//------------------------------------------------------------------------------------------------------------------------template<classT>voidBinaryTree<T>::InTraBiTree(){//中序遍歷二叉樹cout<<"----------------------------------------------"<<endl;cout<<"中序遍歷二叉樹 :";BTNode<T>*p;p=BT;//根結(jié)點(diǎn)InTraverse(p);//從根結(jié)點(diǎn)開始中序遍歷二叉樹cout<<endl;cout<<"----------------------------------------------"<<endl;}template<classT>staticintInTraverse(BTNode<T>*p){if(p!=NULL){InTraverse(p->lchild);cout<<p->data<<'';InTraverse(p->rchild);

//遞歸的調(diào)用中序遍歷左子樹//輸出結(jié)點(diǎn)上的數(shù)據(jù)//遞歸的調(diào)用中序遍歷右子樹}return0;}//------------------------------------------------------------------------------------------------------------------------template<classT>voidBinaryTree<T>::PostTraBiTree(){//后序遍歷二叉樹cout<<"----------------------------------------------"<<endl;cout<<"后序遍歷二叉樹 :";BTNode<T>*p;p=BT;//根結(jié)點(diǎn)PostTraverse(p);//從根結(jié)點(diǎn)開始遍歷二叉樹cout<<endl;cout<<"----------------------------------------------"<<endl;}template<classT>staticintPostTraverse(BTNode<T>*p){if(p!=NULL){PostTraverse(p->lchild);//PostTraverse(p->rchild);//cout<<p->data<<'';

遞歸調(diào)用后序遍歷左子樹遞歸調(diào)用后序遍歷右子樹//輸出結(jié)點(diǎn)上的數(shù)據(jù)}return0;}//------------------------------------------------------------------------------------------------------------------------template<classT>voidBinaryTree<T>::PreTraBiTree_N(){//cout<<"----------------------------------------------"<<endl;cout<<"先序(非遞歸)遍歷二叉樹得： ";BTNode<T>*Stack[200];// 利用指針數(shù)組作為棧inttop=0;BTNode<T>*p=BT;// 將根結(jié)點(diǎn)的指針賦值給 pwhile(p!=NULL||top!=0){while(p!=NULL){cout<<p->data<<"";Stack[top++]=p->rchild;p=p->lchild;}if(top!=0){p=Stack[--top];}}cout<<"\n----------------------------------------------"<<endl;}//------------------------------------------------------------------------------------------------------------------------template<classT>voidBinaryTree<T>::InTraBiTree_N(){//非遞歸中序遍歷二叉樹cout<<"----------------------------------------------"<<endl;cout<<"中序(非遞歸)遍歷二叉樹得： ";inttop=0;BTNode<T>*Stack[200];BTNode<T>*p=BT;while(p||top){while(p){Stack[top++]=p;p=p->lchild;}if(top){p=Stack[--top];cout<<p->data<<'';p=p->rchild;}}cout<<"\n----------------------------------------------"<<endl;}//------------------------------------------------------------------------------------------------------------------------template<classT>voidBinaryTree<T>::LevelTraBiTree(){//利用隊(duì)列 Queue層次遍歷二叉樹BTNode<T>*Queue[100];

//利用一維數(shù)組作為隊(duì)列，存放結(jié)點(diǎn)的指針BTNode<T>*b;intfront,rear;front=rear=0;

//指向隊(duì)列的頭和尾下標(biāo)//隊(duì)列初始為空cout<<"----------------------------------------------"<<endl;if(BT)

//若二叉樹不為空。{Queue[rear++]=BT;

//二叉樹的根結(jié)點(diǎn)指針進(jìn)隊(duì)列。while(front!=rear) //隊(duì)列不為空。{b=Queue[front++]; //隊(duì)首的元素出隊(duì)列if(b)cout<<b->data<<''; //輸出結(jié)點(diǎn)的值if(b->lchild)Queue[rear++]=b->lchild;// 如果左子樹不空，進(jìn)隊(duì)。if(b->rchild)Queue[rear++]=b->rchild;// 如果右子樹不空，進(jìn)隊(duì)。}}cout<<"\n----------------------------------------------"<<endl;}template<classT>intBinaryTree<T>::LeafCount(){//計(jì)算葉子的個(gè)數(shù)intcount=0;returnLeaf(BT,count);}template<classT>staticintLeaf(BTNode<T>*p,int&count){//staticintcount=0;//靜態(tài)變量，存放葉子結(jié)點(diǎn)的個(gè)數(shù)if(p){if(p->lchild==NULL&&p->rchild==NULL) count++;//判斷是否為葉子結(jié)點(diǎn)Leaf(p->lchild,count);// 遞歸遍歷左子樹Leaf(p->rchild,count);// 遞歸遍歷右子樹}returncount;}template<classT>BTNode<T>*BinaryTree<T>::SearchNode(Te){//結(jié)點(diǎn)查詢BTNode<T>*t;if(BT){if(BT->data==e) returnBT;t=search(BT->lchild,e);// 在左子樹中查找if(t)returnt;t=search(BT->rchild,e);//在右子樹查找if(t)returnt;}returnNULL;}template<classT>staticBTNode<T>*search(BTNode<T>*bn,Te){BTNode<T>*t;if(bn){if(bn->data==e) {returnbn;}t=search(bn->lchild,e);//遞歸查找左子樹if(t)returnt;t=search(bn->rchild,e);//遞歸查找右子樹if(t)returnt;}returnNULL;}//------------------------------------------------------------------------------------------------------------------------(2).#include"BinaryTree.cpp"#include"windows.h"intmain(){intMainMenu=-1;BinaryTree<int>T;BinaryTree<int>t;while(MainMenu!=6){system("cls");cout<<"--------------主菜單--------------"<<endl;cout<<"1--創(chuàng)建二叉樹(元素類型為整數(shù))"<<endl;cout<<"2--樹形顯示二叉樹"<<endl;cout<<"3--獲取二叉樹信息>>【進(jìn)入子菜單】"<<endl;cout<<"4--對二叉樹操作>>【進(jìn)入子菜單】"<<endl;cout<<"5--遍歷二叉樹>>【進(jìn)入子菜單】"<<endl;cout<<"6--退出"<<endl;cout<<"----------------------------------"<<endl;cout<<"請選擇操作：[]";cout<<"\b\b";cin>>MainMenu;switch(MainMenu){case1:T.CreateBiTree(-1);break;case2:cout<<"下面顯示的是一棵左轉(zhuǎn)了 90度的樹!"<<endl;T.DisplayBTreeShape(T.GetRoot());// 第一個(gè)參數(shù)是根結(jié)點(diǎn)指針，第二個(gè)參數(shù)為默認(rèn)的 1cout<<endl;system("pause");break;case3:intop;//cin>>op;do{//system("cls");cout<<"---3-獲取二叉樹信息---------"<<endl;cout<<"0.返回主菜單"<<endl;cout<<"1.獲取樹根結(jié)點(diǎn)值"<<endl;cout<<"2.判斷樹是否為空"<<endl;cout<<"3.求樹的深度"<<endl;cout<<"4.雙親結(jié)點(diǎn)值"<<endl;cout<<"5.左孩子值"<<endl;cout<<"6.右孩子值"<<endl;cout<<"7.左兄弟值"<<endl;cout<<"8.右兄弟值"<<endl;cout<<"9.葉子結(jié)點(diǎn)的個(gè)數(shù)"<<endl;cout<<"10.樹形顯示二叉樹"<<endl;cout<<"------------------------------"<<endl;cout<<"請選擇操作： [ ]";cout<<"\b\b\b";cin>>op;switch(op){case1:introot;if(T.RootValue(root)==true)cout<<"樹根結(jié)點(diǎn)的值為： "<<root<<endl;elsecout<<"二叉樹為空 "<<endl;system("pause");break;case2:if(T.IsEmpty()==true)cout<<"二叉樹為空！ "<<endl;elsecout<<"二叉樹不空！ "<<endl;system("pause");break;case3:cout<<"二叉樹的深度為： "<<T.BiTreeDepth()<<endl;system("pause");break;case4:cout<<"請輸入結(jié)點(diǎn)值： ";intnode1;cin>>node1;cout<<"該結(jié)點(diǎn)的雙親結(jié)點(diǎn)為： "<<T.GetParent(node1)<<endl;system("pause");break;case5:cout<<"請輸入結(jié)點(diǎn)值： ";intnode2;cin>>node2;cout<<" 該 結(jié) 點(diǎn) 的 左 孩 子 結(jié) 點(diǎn) 值 為 ："<<T.GetLeftChild(node2)<<endl;system("pause");break;case6:cout<<"請輸入結(jié)點(diǎn)值： ";intnode3;cin>>node3;cout<<" 該 結(jié) 點(diǎn) 的 右 孩 子 結(jié) 點(diǎn) 值 為 ："<<T.GetRightChild(node3)<<endl;system("pause");break;case7:cout<<"請輸入結(jié)點(diǎn)值： ";intnode4;cin>>node4;cout<<" 該 結(jié) 點(diǎn) 的 左 兄 弟 結(jié) 點(diǎn) 值 為 ："<<T.GetLeftSibling(node4)<<endl;system("pause");break;case8:cout<<"請輸入結(jié)點(diǎn)值： ";intnode5;cin>>node5;cout<<" 該 結(jié) 點(diǎn) 的 右 兄 弟 結(jié) 點(diǎn) 值 為 ："<<T.GetRightSibling(node5)<<endl;system("pause");break;case9:cout<<"二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)為："<<T.LeafCount()<<endl;system("pause");break;case10:cout<<"下面顯示的是一棵左轉(zhuǎn)了90度的二叉樹!"<<endl;T.DisplayBTreeShape(T.GetRoot());//第一個(gè)參數(shù)是根結(jié)點(diǎn)指針，第二個(gè)參數(shù)為默認(rèn)的 1cout<<endl;system("pause");break;default:break;}}while(op!=0);break;case4:intop2;do{cout<<"---------4 對二叉樹進(jìn)行操作cout<<"0. 返回主菜單"<<endl;cout<<"1. 銷毀二叉樹"<<endl;cout<<"2. 給指定結(jié)點(diǎn)賦值 "<<endl;cout<<"3. 插入"<<endl;cout<<"4. 刪除"<<endl;cout<<"5. 顯示二叉樹"<<endl;

----------"<<endl;cout<<"------------------------------------"<<endl;cout<<"請選擇操作： []";cout<<"\b\b";cin>>op2;switch(op2){case0:break;case1:T.ClearBiTree();cout<<"已經(jīng)將二叉樹銷毀！ "<<endl;system("pause");break;case2:intChangeValue;//

要改變的結(jié)點(diǎn)值intNewValue;//

修改之后的結(jié)點(diǎn)值cout<<"

請輸入要修改的結(jié)點(diǎn)值：

";cin>>ChangeValue;cout<<"請輸入修改之后的結(jié)點(diǎn)值：cin>>NewValue;if(T.SearchNode(ChangeValue)){

"<<endl;(T.SearchNode(ChangeValue))->data=NewValue;cout<<"修改成功！ "<<endl;}else{cout<<"修改失??！ "<<endl;}system("pause");break;case3:cout<<"請創(chuàng)建一棵沒有右子樹的二叉樹： "<<endl;t.CreateBiTree(-1);cout<<"請輸入要插入的二叉樹的結(jié)點(diǎn)值 "<<endl;in