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

1、word數(shù)據(jù)結(jié)構(gòu)二叉樹根本操作(1)./ 對(duì)二叉樹的根本操作的類模板封裝/-#include<iostream>using namespace std;/-/定義二叉樹的結(jié)點(diǎn)類型BTNode,其中包含數(shù)據(jù)域、左孩子，右孩子結(jié)點(diǎn)。template <class T>struct BTNodeT data ;/數(shù)據(jù)域BTNode* lchild;/指向左子樹的指針BTNode* rchild;/指向右子樹的指針;/-/CBinary的類模板template <class T>class BinaryTreeBTNode<T>* BT;public:

2、BinaryTree()BT=NULL;/ 構(gòu)造函數(shù),將根結(jié)點(diǎn)置空BinaryTree()clear(BT);/ 調(diào)用Clear()函數(shù)將二叉樹銷毀void ClearBiTree()clear(BT);BT=NULL;/ 銷毀一棵二叉樹void CreateBiTree(T end);/ 創(chuàng)立一棵二叉樹，end為空指針域標(biāo)志bool IsEmpty();/ 判斷二叉樹是否為空int BiTreeDepth();/ 計(jì)算二叉樹的深度bool RootValue(T &e);/ 假設(shè)二叉樹不為空用e返回根結(jié)點(diǎn)的值，函數(shù)返回true，否那么函數(shù)返回falseBTNode<T>*

3、GetRoot();/ 二叉樹不為空獲取根結(jié)點(diǎn)指針，否那么返回NULLbool Assign(T e,T value);/ 找到二叉樹中值為e的結(jié)點(diǎn)，并將其值修改為value。T GetParent(T e);/ 假設(shè)二叉樹不空且e是二叉樹中的一個(gè)結(jié)點(diǎn)那么返回其雙親結(jié)點(diǎn)值T GetLeftChild(T e);/ 獲取左孩子結(jié)點(diǎn)值T GetRightChild(T e);/ 獲取右孩子結(jié)點(diǎn)值T GetLeftSibling(T e);/ 獲取左兄弟的結(jié)點(diǎn)值T rightsibling(BTNode<T>*p,T e);T GetRightSibling(T e);/ 獲取右孩子的結(jié)

4、點(diǎn)值bool InsertChild(BTNode<T>* p,BTNode<T>* c,int RL);/ 插入操作bool DeleteChild(BTNode<T>* p,int RL); /刪除操作void PreTraBiTree();/ 遞歸算法：先序遍歷二叉樹void InTraBiTree();/ 遞歸算法：中序遍歷二叉樹void PostTraBiTree();/ 遞歸算法：后序遍歷二叉樹void PreTraBiTree_N();/ 非遞歸算法：先序遍歷二叉樹void InTraBiTree_N();/ 非遞歸算法：中序遍歷二叉樹void

5、 LevelTraBiTree(); / 利用隊(duì)列層次遍歷二叉樹int LeafCount();/ 計(jì)算葉子結(jié)點(diǎn)的個(gè)數(shù)BTNode<T>* SearchNode(T e);/ 尋找到結(jié)點(diǎn)值為e的結(jié)點(diǎn)，返回指向結(jié)點(diǎn)的指針void DisplayBTreeShape(BTNode<T>*bt,int level=1);/二叉樹的樹形顯示算法template <class T>void BinaryTree<T>:DisplayBTreeShape(BTNode<T>*bt,int level) if(bt)/空二叉樹不顯示 Display

6、BTreeShape(bt->rchild,level+1);/顯示右子樹 cout<<endl; /顯示新行 for(int i=0;i<level-1;i+) cout<<" " /確保在第level列顯示節(jié)點(diǎn) cout<<bt->data; /顯示節(jié)點(diǎn) DisplayBTreeShape(bt->lchild,level+1);/顯示左子樹 /if/DisplayBTreetemplate <class T>static int clear(BTNode<T>*bt) /銷毀一棵二叉樹

7、if(bt)/根結(jié)點(diǎn)不空 clear(bt->lchild); /遞歸調(diào)用Clear()函數(shù)銷毀左子樹clear(bt->rchild); /遞歸調(diào)用Clear()函數(shù)銷毀右子樹cout<<"釋放了指針"<<bt<<"所指向的空間。"<<endl;delete bt; /釋放當(dāng)前訪問(wèn)的根結(jié)點(diǎn) return 0;template <class T>void BinaryTree<T>:CreateBiTree(T end)/創(chuàng)立一棵二叉樹：先序序列的順序輸入數(shù)據(jù)，end為結(jié)

8、束的標(biāo)志cout<<"請(qǐng)按先序序列的順序輸入二叉樹,-1為空指針域標(biāo)志："<<endl;BTNode<T>*p;T x;cin>>x;/輸入根結(jié)點(diǎn)的數(shù)據(jù)if(x=end) return ;/end 表示指針為空，說(shuō)明樹為空p=new BTNode<T>/申請(qǐng)內(nèi)存if(!p)cout<<"申請(qǐng)內(nèi)存失?。?quot;<<endl;exit(-1);/申請(qǐng)內(nèi)存失敗退出p->data=x;p->lchild=NULL;p->rchild=NULL;BT=p;/根結(jié)點(diǎn)cre

9、ate(p,1,end);/創(chuàng)立根結(jié)點(diǎn)左子樹，1為標(biāo)志，表示左子樹create(p,2,end);/創(chuàng)立根結(jié)點(diǎn)右子樹，2為標(biāo)志，表示右子樹template <class T>static int create(BTNode<T>*p,int k,T end)/靜態(tài)函數(shù)，創(chuàng)立二叉樹，k為創(chuàng)立左子樹還是右子樹的標(biāo)志，end為空指針域的標(biāo)志BTNode<T>*q;T x;cin>>x;if(x!=end)/先序順序輸入數(shù)據(jù)q=new BTNode<T>q->data=x;q->lchild=NULL;q->rchild=N

10、ULL;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)立右子樹return 0;template <class T>bool BinaryTree<T>:IsEmpty()/判斷二叉樹是否為空if(BT=NULL) return true;/樹根結(jié)點(diǎn)為空，說(shuō)明樹為空return false;template <class T>int BinaryTree<T>:BiTreeDepth()/利

11、用遞歸算法計(jì)算樹的深度BTNode<T>*bt=BT;/樹根結(jié)點(diǎn)int depth=0;/開(kāi)始的時(shí)候數(shù)的深度初始化為0if(bt)/如果樹不為空Depth(bt,1,depth);return depth;template <class T>static int Depth(BTNode<T>* p,int level,int &depth)/這個(gè)函數(shù)由BiTreeDepth()函數(shù)調(diào)用完成樹的深度的計(jì)算/其中p是根結(jié)點(diǎn)，Level 是層，depth用來(lái)返回樹的深度if(level>depth) depth=level;if(p->lch

12、ild) Depth(p->lchild,level+1,depth);/遞歸的遍歷左子樹，并且層數(shù)加1if(p->rchild) Depth(p->rchild,level+1,depth);/遞歸的遍歷右子樹，并且層數(shù)加1return 0;template <class T>bool BinaryTree<T>:RootValue(T &e)/假設(shè)二叉樹不為空用e返回根結(jié)點(diǎn)的值，函數(shù)返回true，否那么函數(shù)返回falseif(BT!=NULL)/判斷二叉樹是否為空e=BT->data;/假設(shè)不空，那么將根結(jié)點(diǎn)的數(shù)據(jù)賦值給ereturn

13、 true;/操作成功，返回truereturn false;/二叉樹為空，返回falsetemplate <class T>BTNode<T>*BinaryTree<T>:GetRoot()/獲取根信息return BT;/返回根結(jié)點(diǎn)的指針，假設(shè)二叉樹為空那么返回NULLtemplate <class T>bool BinaryTree<T>:Assign(T e,T value)/結(jié)點(diǎn)賦值if(SearchNode(e)!=NULL)(SearchNode(e)->data=value;return true;return

14、false;template <class T>T BinaryTree<T>:GetParent(T e)/獲取雙親信息BTNode<T>*Queue200,*p;int rear,front;rear=front=0;if(BT)Queuerear+=BT;while(rear!=front)p=Queuefront+;if(p->lchild&&p->lchild->data=e|p->rchild&&p->rchild->data=e)return p->data;elseif

15、(p->lchild) Queuerear+=p->lchild;if(p->rchild) Queuerear+=p->rchild;return NULL;template <class T>T BinaryTree<T>:GetRightChild(T e)/如果二叉樹存在，e是二叉樹中的一個(gè)結(jié)點(diǎn)，右子樹存在那么返回右子樹的結(jié)點(diǎn)值，否那么返回0并提示右子樹為空BTNode<T>*p=SearchNode(e);if(p->rchild) return p->rchild->data;/右子樹不空，返回右子樹根結(jié)

16、點(diǎn)的值cout<<"結(jié)點(diǎn)"<<e<<"的右子樹為空"<<endl;return 0;template <class T>T BinaryTree<T>:GetLeftChild(T e)/如果二叉樹存在，e是二叉樹中的一個(gè)結(jié)點(diǎn)，左子樹存在那么返回左子樹的結(jié)點(diǎn)值，否那么返回0并提示左子樹為空BTNode<T>*p=SearchNode(e);if(p->lchild) return p->lchild->data;cout<<"結(jié)點(diǎn)&

17、quot;<<e<<"的左子樹為空"<<endl;return 0;template <class T>T BinaryTree<T>:GetLeftSibling(T e)/獲取左兄弟信息if(BT!=NULL)return leftsibling(BT,e);else/二叉樹為空cout<<"二叉樹為空！"<<endl;return 0;template <class T>T leftsibling(BTNode<T>*p,T e)T q=0;

18、if(p=NULL) return 0;elseif(p->rchild)if(p->rchild->data=e)if(p->lchild) return p->lchild->data;elsereturn NULL;q=leftsibling(p->lchild,e);if(q)return q;q=leftsibling(p->rchild,e);if(q)return q;return 0;/-template <class T>T BinaryTree<T>:GetRightSibling(T e)/獲取右兄弟

19、信息if(BT!=NULL)return rightsibling(BT,e);else/二叉樹為空cout<<"二叉樹為空！"<<endl;return 0;template <class T> T BinaryTree<T>:rightsibling(BTNode<T>*p,T e)BTNode<T> *q=SearchNode(e);BTNode<T> *pp;if(q)pp=SearchNode(GetParent(e);if(pp)if(pp->rchild) return

20、pp->rchild->data;else return 0;else return 0;return 0;template <class T>bool BinaryTree<T>:InsertChild(BTNode<T>* p,BTNode<T>* c,int LR)/插入孩子if(p)if(LR=0)c->rchild=p->lchild;p->lchild=c;elsec->rchild=p->rchild;p->rchild=c;return true;return false;/p為空/

21、-template <class T>bool BinaryTree<T>:DeleteChild(BTNode<T>* p,int RL) /刪除結(jié)點(diǎn)if(p)if(RL=0)clear(p->lchild);/釋放p右子樹的所有結(jié)點(diǎn)空間p->lchild=NULL;elseclear(p->rchild);p->rchild=NULL;return true;/刪除成功return false;/p為空/-template <class T>void BinaryTree<T>:PreTraBiTree()

22、/先序遍歷二叉樹cout<<"-"<<endl;cout<<"先序遍歷二叉樹:"BTNode<T>*p;p=BT;/根結(jié)點(diǎn)PreTraverse(p); /從根結(jié)點(diǎn)開(kāi)始先序遍歷二叉樹cout<<endl;cout<<"-"<<endl;template <class T>static int PreTraverse(BTNode<T>*p)if(p!=NULL)cout<<p->data<<'

23、; '/輸出結(jié)點(diǎn)上的數(shù)據(jù)PreTraverse(p->lchild);/遞歸的調(diào)用前序遍歷左子樹PreTraverse(p->rchild);/遞歸的調(diào)用前序遍歷右子樹return 0;/-template <class T>void BinaryTree<T>:InTraBiTree()/中序遍歷二叉樹cout<<"-"<<endl;cout<<"中序遍歷二叉樹:"BTNode<T>*p;p=BT;/根結(jié)點(diǎn)InTraverse(p);/從根結(jié)點(diǎn)開(kāi)始中序遍歷二叉樹

24、cout<<endl;cout<<"-"<<endl;template <class T>static int InTraverse(BTNode<T>*p)if(p!=NULL)InTraverse(p->lchild);/遞歸的調(diào)用中序遍歷左子樹cout<<p->data<<' '/輸出結(jié)點(diǎn)上的數(shù)據(jù)InTraverse(p->rchild);/遞歸的調(diào)用中序遍歷右子樹return 0;/-template <class T>void Bina

25、ryTree<T>:PostTraBiTree()/后序遍歷二叉樹cout<<"-"<<endl;cout<<"后序遍歷二叉樹:"BTNode<T>*p;p=BT;/根結(jié)點(diǎn)PostTraverse(p);/從根結(jié)點(diǎn)開(kāi)始遍歷二叉樹cout<<endl;cout<<"-"<<endl;template <class T>static int PostTraverse(BTNode<T>*p)if(p!=NULL)Post

26、Traverse(p->lchild);/遞歸調(diào)用后序遍歷左子樹PostTraverse(p->rchild);/遞歸調(diào)用后序遍歷右子樹cout<<p->data<<' '/輸出結(jié)點(diǎn)上的數(shù)據(jù)return 0;/-template <class T>void BinaryTree<T>:PreTraBiTree_N()/cout<<"-"<<endl;cout<<"先序(非遞歸)遍歷二叉樹得："BTNode<T> *Stack2

27、00;/利用指針數(shù)組作為棧int top=0;BTNode<T>*p=BT;/將根結(jié)點(diǎn)的指針賦值給pwhile(p!=NULL|top!=0)while(p!=NULL)cout<<p->data<<" "Stacktop+=p->rchild;p=p->lchild;if(top!=0)p=Stack-top;cout<<"n-"<<endl;/-template <class T>void BinaryTree<T>:InTraBiTree_N()/

28、非遞歸中序遍歷二叉樹cout<<"-"<<endl;cout<<"中序(非遞歸)遍歷二叉樹得："int top=0;BTNode<T> *Stack200;BTNode<T> *p=BT;while(p|top)while(p)Stacktop+=p;p=p->lchild;if(top)p=Stack-top;cout<<p->data<<' 'p=p->rchild;cout<<"n-"<<

29、endl;/-template <class T>void BinaryTree<T>:LevelTraBiTree()/利用隊(duì)列Queue層次遍歷二叉樹BTNode<T> *Queue100;/利用一維數(shù)組作為隊(duì)列，存放結(jié)點(diǎn)的指針BTNode<T> *b;int front,rear;/指向隊(duì)列的頭和尾下標(biāo)front=rear=0;/隊(duì)列初始為空cout<<"-"<<endl;if(BT)/假設(shè)二叉樹不為空。Queuerear+=BT;/二叉樹的根結(jié)點(diǎn)指針進(jìn)隊(duì)列。while(front!=rear)/

30、隊(duì)列不為空。b=Queuefront+;/隊(duì)首的元素出隊(duì)列if(b)cout<<b->data<<' '/輸出結(jié)點(diǎn)的值if(b->lchild) Queuerear+=b->lchild;/如果左子樹不空，進(jìn)隊(duì)。if(b->rchild) Queuerear+=b->rchild;/如果右子樹不空，進(jìn)隊(duì)。cout<<"n-"<<endl;template <class T>int BinaryTree<T>:LeafCount()/計(jì)算葉子的個(gè)數(shù)int co

31、unt=0;return Leaf(BT,count);template <class T>static int Leaf(BTNode<T>* p,int &count)/static int count=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);/遞歸遍歷右子樹return count;template <

32、class T>BTNode<T>* BinaryTree<T>:SearchNode(T e)/結(jié)點(diǎn)查詢BTNode<T>*t;if(BT)if(BT->data=e)return BT;t=search(BT->lchild,e);/在左子樹中查找if(t)return t;t=search(BT->rchild,e);/在右子樹查找if(t) return t;return NULL;template <class T>static BTNode<T>* search(BTNode<T>*bn

33、,T e)BTNode<T>*t;if(bn)if(bn->data=e)return bn;t=search(bn->lchild,e);/遞歸查找左子樹if(t) return t;t=search(bn->rchild,e);/遞歸查找右子樹if(t) return t;return NULL;/-(2).#include"BinaryTree.cpp"#include"windows.h"int main()int MainMenu=-1;BinaryTree<int> T;BinaryTree<i

34、nt> t;while(MainMenu!=6)system("cls");cout<<"-主菜單-"<<endl;cout<<"1-創(chuàng)立二叉樹(元素類型為整數(shù)) "<<endl;cout<<"2-樹形顯示二叉樹"<<endl;cout<<"3-獲取二叉樹信息 >>【進(jìn)入子菜單】"<<endl;cout<<"4-對(duì)二叉樹操作 >>【進(jìn)入子菜單】&qu

35、ot;<<endl;cout<<"5-遍歷二叉樹 >>【進(jìn)入子菜單】"<<endl;cout<<"6-退出"<<endl;cout<<"-"<<endl;cout<<"請(qǐng)選擇操作： "cout<<"bb"cin>>MainMenu;switch(MainMenu)case 1:T.CreateBiTree(-1);break;case 2:cout<<&

36、quot;下面顯示的是一棵左轉(zhuǎn)了90度的樹!"<<endl;T.DisplayBTreeShape(T.GetRoot();/第一個(gè)參數(shù)是根結(jié)點(diǎn)指針，第二個(gè)參數(shù)為默認(rèn)的1 cout<<endl;system("pause");break;case 3:int op;/cin>>op;do/system("cls");cout<<" -3-獲取二叉樹信息-"<<endl;cout<<"0. 返回主菜單"<<endl;cout

37、<<"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. 左兄弟值"&

38、lt;<endl;cout<<"8. 右兄弟值"<<endl;cout<<"9. 葉子結(jié)點(diǎn)的個(gè)數(shù)"<<endl;cout<<"10.樹形顯示二叉樹"<<endl;cout<<" -"<<endl;cout<<"請(qǐng)選擇操作： "cout<<"bbb"cin>>op;switch(op)case 1:int root;if(T.RootValu

39、e(root)=true)cout<<"樹根結(jié)點(diǎn)的值為："<<root<<endl;elsecout<<"二叉樹為空"<<endl;system("pause");break;case 2:if(T.IsEmpty()=true)cout<<"二叉樹為空！"<<endl;else cout<<"二叉樹不空！"<<endl;system("pause");break;ca

40、se 3:cout<<"二叉樹的深度為："<<T.BiTreeDepth()<<endl;system("pause");break;case 4:cout<<"請(qǐng)輸入結(jié)點(diǎn)值："int node1;cin>>node1;cout<<"該結(jié)點(diǎn)的雙親結(jié)點(diǎn)為："<<T.GetParent(node1)<<endl;system("pause");break;case 5:cout<<"

41、請(qǐng)輸入結(jié)點(diǎn)值："int node2;cin>>node2;cout<<"該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)值為："<<T.GetLeftChild(node2)<<endl;system("pause");break;case 6:cout<<"請(qǐng)輸入結(jié)點(diǎn)值："int node3;cin>>node3;cout<<"該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)值為："<<T.GetRightChild(node3)<<endl;system

42、("pause");break;case 7:cout<<"請(qǐng)輸入結(jié)點(diǎn)值："int node4;cin>>node4;cout<<"該結(jié)點(diǎn)的左兄弟結(jié)點(diǎn)值為："<<T.GetLeftSibling(node4)<<endl;system("pause");break;case 8:cout<<"請(qǐng)輸入結(jié)點(diǎn)值："int node5;cin>>node5;cout<<"該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)值為：&q

43、uot;<<T.GetRightSibling(node5)<<endl;system("pause");break;case 9:cout<<"二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)為："<<T.LeafCount()<<endl;system("pause");break;case 10:cout<<"下面顯示的是一棵左轉(zhuǎn)了90度的二叉樹!"<<endl;T.DisplayBTreeShape(T.GetRoot();/第一個(gè)參數(shù)是根結(jié)點(diǎn)指針，第

44、二個(gè)參數(shù)為默認(rèn)的1 cout<<endl;system("pause");break;default:break;while(op!=0);break;case 4:int op2;docout<<" -4 對(duì)二叉樹進(jìn)行操作-"<<endl;cout<<"0. 返回主菜單"<<endl;cout<<"1. 銷毀二叉樹"<<endl;cout<<"2. 給指定結(jié)點(diǎn)賦值"<<endl;cout

45、<<"3. 插入"<<endl;cout<<"4. 刪除"<<endl;cout<<"5. 顯示二叉樹"<<endl;cout<<" -"<<endl;cout<<"請(qǐng)選擇操作： "cout<<"bb"cin>>op2;switch(op2)case 0:break;case 1:T.ClearBiTree();cout<<"

46、;已經(jīng)將二叉樹銷毀！"<<endl;system("pause");break;case 2:int ChangeValue;/要改變的結(jié)點(diǎn)值int NewValue;/修改之后的結(jié)點(diǎn)值cout<<"請(qǐng)輸入要修改的結(jié)點(diǎn)值："cin>>ChangeValue;cout<<"請(qǐng)輸入修改之后的結(jié)點(diǎn)值："<<endl;cin>>NewValue;if(T.SearchNode(ChangeValue) (T.SearchNode(ChangeValue)->

47、;data=NewValue;cout<<"修改成功！"<<endl;elsecout<<"修改失?。?quot;<<endl;system("pause");break;case 3:cout<<"請(qǐng)創(chuàng)立一棵沒(méi)有右子樹的二叉樹："<<endl;t.CreateBiTree(-1);cout<<"請(qǐng)輸入要插入的二叉樹的結(jié)點(diǎn)值"<<endl;int invalue;cin>>invalue;cout&

48、lt;<"請(qǐng)選擇插入左子樹0還是右子樹1"int lr;cin>>lr;if(T.SearchNode(invalue)&&t.GetRoot()&&(t.GetRoot()->rchild)=NULL)t.InsertChild(T.SearchNode(invalue),t.GetRoot(),lr);cout<<"操作成功！"<<endl;cout<<"操作以后的二叉樹為："<<endl;t.PreTraBiTree();elsecout<<"操作失??！"<&l