二叉樹(shù)的基本操作技巧

1、/先序創(chuàng)建二叉樹(shù)/先序遍歷二叉樹(shù)/中序遍歷二叉樹(shù)/后序遍歷二叉樹(shù)/求度為1的結(jié)點(diǎn)的個(gè)數(shù)/求葉子結(jié)點(diǎn)的個(gè)數(shù)/度為2的結(jié)點(diǎn)的個(gè)數(shù)/層序遍歷二叉樹(shù)/二叉樹(shù)的基本操作#include<iostream.h>typedefstructnode/定義結(jié)點(diǎn)chardata;structnode*lchild,*rchild;BinTNode;typedefBinTNode*BinTree;/定義二叉樹(shù)voidCreateBinTree(BinTree&T);voidPreOrder(BinTreeT);voidInOrder(BinTreeT);voidPostOrder(BinTree

2、T);intonechild(BinTreeT);intleafs(BinTreeT);inttwochild(BinTreeT);voidtranslevel(BinTreeb);voidmain()intn;BinTreeT;charch1,ch2;cout<<"歡迎進(jìn)入二叉樹(shù)測(cè)試程序的基本操作"<<endl;cout<<"請(qǐng)選擇<<endl;ch1='y'while(ch1='y'|ch1='Y')cout<<"1建立二叉樹(shù)n"co

3、ut<<"2先序遍歷n"cout<<"3中序遍歷n"cout<<"4后序遍歷n"cout<<"5單孩子結(jié)點(diǎn)數(shù)n"cout<<"6雙孩子結(jié)點(diǎn)數(shù)n"cout<<"7葉子結(jié)點(diǎn)數(shù)n"cout<<"8層序遍歷n"cout<<"X退出n"cin>>ch2;switch(ch2)case'1':cout<<"

4、;請(qǐng)輸入按先序建立二叉樹(shù)的結(jié)點(diǎn)序列：n”;CreateBinTree(T);cout<<endl;break;case'2':cout<<"二叉樹(shù)的先序遍歷序列：n"PreOrder(T);cout<<endl;break;case'3':cout<<"二叉樹(shù)的中序遍歷序列：n"InOrder(T);cout<<endl;break;case'4':cout<<"二叉樹(shù)的后序遍歷序列：n"PostOrder(T);c

5、out<<endl;break;case'5':cout<<"二叉樹(shù)的單孩子結(jié)點(diǎn)數(shù)：n"n=onechild(T);cout<<n<<endl;cout<<endl;break;case'6':cout<<"二叉樹(shù)的雙孩子結(jié)點(diǎn)數(shù)：n"n=twochild(T);cout<<n<<endl;cout<<endl;break;case'7':cout<<"二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)：n&qu

6、ot;n=leafs(T);cout<<n<<endl;cout<<endl;break;case'8':cout<<"二叉樹(shù)的層序遍歷序列：n"translevel(T);cout<<endl;break;case'x':case'X':ch1='x'break;voidCreateBinTree(BinTree&T)(charch;cin>>ch;if(ch='0')T=NULL;else(T=(BinTNode

7、*)newBinTNode;T->data=ch;CreateBinTree(T->lchild);CreateBinTree(T->rchild);)voidInOrder(BinTreeT)(if(T)(InOrder(T->lchild);cout<<T->data;InOrder(T->rchild);)voidPostOrder(BinTreeT)(if(T)(PostOrder(T->lchild);PostOrder(T->rchild);cout<<T->data;)voidPreOrder(BinT

8、reeT)(if(T)(cout<<T->data;PreOrder(T->lchild);PreOrder(T->rchild);/層序遍歷二叉樹(shù)采用一個(gè)隊(duì)列q,先將二叉樹(shù)的根結(jié)點(diǎn)入隊(duì)列，然后退隊(duì)列，輸出該結(jié)點(diǎn)，若它有左子樹(shù)，便將左子樹(shù)根結(jié)點(diǎn)入隊(duì)列，若它有右子樹(shù)，便將右子樹(shù)根結(jié)點(diǎn)入隊(duì)列，如此直到隊(duì)列空為止。/因?yàn)殛?duì)列的特點(diǎn)是先進(jìn)先出，從而達(dá)到按層序遍歷的目的。#defineMAXLEN100voidtranslevel(BinTreeb)(structnode(BinTreevecMAXLEN;intf,r;q;定義隊(duì)列q,f表示隊(duì)頭指針，r隊(duì)尾指針q.f=0;

9、/置隊(duì)列為空隊(duì)列q.r=0;if(b!=NULL)cout<<b->data<<""q.vecq.r=b;/結(jié)點(diǎn)指針進(jìn)入隊(duì)列q.r=q.r+1;/隊(duì)尾指針后移while(q.f<q.r)/隊(duì)列不為空(b=q.vecq.f;/隊(duì)頭出隊(duì)列q.f=q.f+1;if(b->lchild!=NULL)輸出左孩子，并入隊(duì)列(cout<<b->lchild->data<<""q.vecq.r=b->lchild;q.r=q.r+1;if(b->rchild!=NULL)輸出右孩子

10、，并入隊(duì)列(cout<<b->rchild->data<<""q.vecq.r=b->rchild;q.r=q.r+1;intonechild(BinTreeT)/求度為1的結(jié)點(diǎn)的個(gè)數(shù)(if(T=NULL)return0;elseif(T->lchild=NULL&&T->rchild!=NULL|T->lchild!=NULL&&T->rchild=NULL)return(onechild(T->lchild)+onechild(T->rchild)+1);elsereturn(onechild(T->lchild)+onechild(T->rchild);intleafs(BinTreeT)(intnum1,num2;if(T=NULL)return0;elseif(T->lchild=NULL&&T->rchild=NULL)return1;else(num1=leafs(T->lchild);num2=leafs(T->rchild);returnnum1+num2;)inttwochild(BinTreeT)(intnu