二叉樹的基本 操作

二叉樹的基本操作二叉樹的基本操作二叉樹的基本操作xxx公司二叉樹的基本操作文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度//二叉樹的基本操作#include<>typedefstructnode//定義結(jié)點(diǎn){chardata;structnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;//定義二叉樹voidCreateBinTree(BinTree&T);//先序創(chuàng)建二叉樹voidPreOrder(BinTreeT);//先序遍歷二叉樹voidInOrder(BinTreeT);//中序遍歷二叉樹voidPostOrder(BinTreeT);//后序遍歷二叉樹intonechild(BinTreeT);//求度為1的結(jié)點(diǎn)的個(gè)數(shù)intleafs(BinTreeT);//求葉子結(jié)點(diǎn)的個(gè)數(shù)inttwochild(BinTreeT);//度為2的結(jié)點(diǎn)的個(gè)數(shù)voidtranslevel(BinTreeb);//層序遍歷二叉樹voidmain(){intn;BinTreeT;charch1,ch2;cout<<"歡迎進(jìn)入二叉樹測(cè)試程序的基本操作"<<endl;cout<<"--------------請(qǐng)選擇------------"<<endl;ch1='y';while(ch1=='y'||ch1=='Y'){cout<<"1---------建立二叉樹\n"; cout<<"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<<"請(qǐng)輸入按先序建立二叉樹的結(jié)點(diǎn)序列：\n"; CreateBinTree(T); cout<<endl; break;case'2': cout<<"二叉樹的先序遍歷序列：\n"; PreOrder(T); cout<<endl; break;case'3': cout<<"二叉樹的中序遍歷序列：\n"; InOrder(T); cout<<endl; break;case'4': cout<<"二叉樹的后序遍歷序列：\n"; PostOrder(T); cout<<endl; break; case'5':cout<<"二叉樹的單孩子結(jié)點(diǎn)數(shù)：\n"; n=onechild(T); cout<<n<<endl; cout<<endl; break; case'6':cout<<"二叉樹的雙孩子結(jié)點(diǎn)數(shù)：\n"; n=twochild(T); cout<<n<<endl; cout<<endl; break; case'7':cout<<"二叉樹的葉子結(jié)點(diǎn)數(shù)：\n"; n=leafs(T); cout<<n<<endl; cout<<endl; break;case'8':cout<<"二叉樹的層序遍歷序列：\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*)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(BinTreeT){ if(T) { cout<<T->data; PreOrder(T->lchild); PreOrder(T->rchild); }}//層序遍歷二叉樹//采用一個(gè)隊(duì)列q，先將二叉樹的根結(jié)點(diǎn)入隊(duì)列，然后退隊(duì)列，輸出該結(jié)點(diǎn)，若它有左子樹，便將左子樹根結(jié)點(diǎn)入隊(duì)列，若它有右子樹，便將右子樹根結(jié)點(diǎn)入隊(duì)列，如此直到隊(duì)列空為止。//因?yàn)殛?duì)列的特點(diǎn)是先進(jìn)先出，從而達(dá)到按層序遍歷的目的。#defineMAXLEN100voidtranslevel(BinTreeb){structnode{BinTreevec[MAXLEN];intf,r;}q;//定義隊(duì)列q，f表示隊(duì)頭指針，r隊(duì)尾指針=0;//置隊(duì)列為空隊(duì)列=0;if(b!=NULL)cout<<b->data<<"";[]=b;//結(jié)點(diǎn)指針進(jìn)入隊(duì)列=+1;//隊(duì)尾指針后移while<//隊(duì)列不為空{(diào)b=[];//隊(duì)頭出隊(duì)列=+1;if(b->lchild!=NULL)//輸出左孩子，并入隊(duì)列{cout<<b->lchild->data<<"";[]=b->lchild;=+1;}if(b->rchild!=NULL)//輸出右孩子，并入隊(duì)列{cout<<b->rchild->data<<"";[]=b->rchild;=+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); else return(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){ intn