實(shí)驗(yàn)三 二叉樹的基本運(yùn)算

實(shí)驗(yàn)三二叉樹的基本運(yùn)算一、實(shí)驗(yàn)?zāi)康?、使學(xué)生熟練掌握二叉樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。2、熟練掌握二叉樹的各種遍歷算法。二、實(shí)驗(yàn)內(nèi)容1、問題描述建立一棵二叉樹，試編程實(shí)現(xiàn)二叉樹的如下基本操作：

(1).按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹T；

(2).對(duì)這棵二叉樹進(jìn)行遍歷：先序、中序、后序以及層次遍歷，分別輸出結(jié)點(diǎn)的遍歷序列；

(3).求二叉樹的深度/結(jié)點(diǎn)數(shù)目/葉結(jié)點(diǎn)數(shù)目；(選做)

(4).將二叉樹每個(gè)結(jié)點(diǎn)的左右子樹交換位置。（選做）2、基本要求從鍵盤接受輸入（先序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以先序來建立）。3、測(cè)試數(shù)據(jù)如輸入：abc00de0g00f000（其中ф表示空格字符）

先序：a->b->c->d->e->g->f中序：a->b->c->d->e->g->f后序：a->b->c->d->e->g->f三、程序代碼#include<malloc.h> #include<iostream.h> #defineOK1 #defineERROR-1 typedefcharTElemType; inti; typedefstructBiTNode{ TElemTypedata; structBiTNode*lchild,*rchild; }BiTNode,*BiTree; intCreateBiTree(BiTree&T)//創(chuàng)建二叉樹 { chara; cin>>a; if(a=='0')T=NULL; else{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))){returnERROR;} T->data=a; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } returnOK; } intPreOrderTraverse(BiTree&T)//先序遍歷二叉樹 { if(T) { //cout<<"此為先序遍歷"<<endl; cout<<T->data<<"->"; if(PreOrderTraverse(T->lchild)) if(PreOrderTraverse(T->rchild)) returnOK; returnERROR; }elsereturnOK; } intInOrderTraverse(BiTree&T)//中序遍歷二叉樹 { if(T) { //cout<<"此為中序遍歷"<<endl; if (InOrderTraverse(T->lchild)) { cout<<T->data<<"->"; if(InOrderTraverse(T->rchild)) returnOK; } returnERROR; }elsereturnOK; } intPostOrderTraverse(BiTree&T) //后序遍歷二叉樹 { if(T) { //cout<<"此為后序遍歷"<<endl; if(PostOrderTraverse(T->lchild)) if(PostOrderTraverse(T->rchild)) { cout<<T->data<<"->"; i++; return(OK); } return(ERROR); } else return(OK); } intCountDepth(BiTree&T)//計(jì)算二叉樹的深度 { if(T==NULL) { return0; } else { intdepl=CountDepth(T->lchild); intdepr=CountDepth(T->lchild); if(depl>depr) { returndepl+1; } else { returndepr+1; } } } voidmain()//主函數(shù) { BiTreeT; cout<<"請(qǐng)輸入二叉樹節(jié)點(diǎn)的值以創(chuàng)建樹"<<endl; CreateBiTree(T); cout<<"此為先序遍歷"; PreOrderTraverse(T); cout<<"end"<<endl; cout<<"此為中序遍歷"; InOrderTraverse(T); cout<<"end"<<endl; cout<<"此為后序遍歷"; PostOrderTraverse(T); cout<<"end"<<endl<<"此樹節(jié)點(diǎn)數(shù)是"<<i<<endl<<"此樹深度是"<<CountDepth(T)<<endl; }四、調(diào)試結(jié)果及運(yùn)行界面：實(shí)驗(yàn)心得通過這次程序上機(jī)實(shí)驗(yàn)讓我認(rèn)識(shí)到了以前還不太了解的二叉樹的性質(zhì)和作用，這次實(shí)驗(yàn)的的確確的加深了我對(duì)它的理解。還有很多很多知識(shí)我是通過看書本、請(qǐng)教同學(xué)老師的，但是想深一層，這都是暴露了我對(duì)知識(shí)掌握得不牢固的表現(xiàn)，我不能夠過分依賴，而是應(yīng)該平常多多上機(jī)實(shí)踐來鞏固知識(shí)，發(fā)現(xiàn)問題并解決問題。把學(xué)過的二叉樹的操作的知識(shí)強(qiáng)化，能夠把課堂上學(xué)的知識(shí)通過自己設(shè)計(jì)的程序表示出來，加深了對(duì)理論知識(shí)的理解。最佳答案#include<stdio.h>#include<malloc.h>#defineM10typedefintDataType;/*元素的數(shù)據(jù)類型*/typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BitTNode,*BiTree;intfront=0,rear=0;BitTNode*que[10];BitTNode*creat(){BitTNode*t;DataTypex;scanf("%d",&x);if(x==0)t=NULL;else{t=(BitTNode*)malloc(sizeof(BitTNode));t->data=x;t->lchild=creat();t->rchild=creat();}return(t);}/*creat*//*前序遍歷二叉樹t*/voidpreorder(BiTreet){if(t!=NULL){printf("%4d",t->data);preorder(t->lchild);preorder(t->rchild);}}/*中序遍歷二叉樹t*/voidinorder(BiTreet){if(t!=NULL){inorder(t->lchild);printf("%4d",t->data);inorder(t->rchild);}}/*后序遍歷二叉樹t*/voidpostorder(BiTreet){if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf("%4d",t->data);}}voidenqueue(BitTNode*t){if(front!=(rear+1)%M){rear=(rear+1)%M;que[rear]=t;}}/*enqueue*/BitTNode*delqueue(){if(front==rear)returnNULL;{front=(front+1)%M;return(que[front]);}}/*delqueue*//*按層次遍歷二叉樹t*/voidlevorder(BiTreet){BitTNode*p;if(t!=NULL){enqueue(t);while(front!=rear){p=delqueue();printf("%4d",p->data);if(p->lchild!=NULL)enqueue(p->lchild);if(p->rchild!=NULL)enqueue(p->rchild);}}}/*levorder*////////////////////////////////////////////////////////////////////計(jì)算二叉樹深度、所有結(jié)點(diǎn)總數(shù)、葉子結(jié)點(diǎn)數(shù)、雙孩子結(jié)點(diǎn)個(gè)數(shù)、單孩子結(jié)點(diǎn)個(gè)數(shù)的算法intBTreeDepth(BitTNode*BT){intleftdep,rightdep;if(BT==NULL)return(0);else{leftdep=BTreeDepth(BT->lchild);rightdep=BTreeDepth(BT->rchild);if(leftdep>rightdep)return(leftdep+1);elsereturn(rightdep+1);}}intnodecount(BitTNode*BT){if(BT==NULL)return(0);elsereturn(nodecount(BT->lchild)+nodecount(BT->rchild)+1);}intleafcount(BitTNode*BT){if(BT==NULL)return(0);elseif(BT->lchild==NULL&&BT->rchild==NULL)return(1);elsereturn(leafcount(BT->lchild)+leafcount(BT->rchild));}intnotleafcount(BitTNode*BT){if(BT==NULL)return(0);elseif(BT->lchild==NULL&&BT->rchild==NULL)return(0);elsereturn(notleafcount(BT->lchild)+notleafcount(BT->rchild)+1);}intonesoncount(BitTNode*BT){if(BT==NULL)return(0);elseif((BT->lchild==NULL&&BT->rchild!=NULL)||(BT->lchild!=NULL&&BT->rchild==NULL))return(onesoncount(BT->lchild)+onesoncount(BT->rchild)+1);elsereturn(onesoncount(BT->lchild)+onesoncount(BT->rchild));}inttwosoncount(BitTNode*BT){if(BT==NULL)return(0);elseif(BT->lchild==NULL||BT->rchild==NULL)return(twosoncount(BT->lchild)+twosoncount(BT->rchild));elseif(BT->lchild!=NULL&&BT->rchild!=NULL)return(twosoncount(BT->lchild)+twosoncount(BT->rchild)+1);}main(){BitTNode*root;root=creat();printf("\n按先序遍歷次序生成的二叉樹");printf("\n前序遍歷二叉樹");preorder(root);printf("\n中序遍歷二叉樹");inorder(root);printf("\n后序遍歷二叉樹");postorder(root);printf("\n層次順序遍歷二叉樹");levorder(root);printf("\n二叉樹深度:%d\n",BTreeDepth(root));printf("總結(jié)點(diǎn)個(gè)數(shù):%d\n",nodecount(root));printf("葉子結(jié)點(diǎn)個(gè)數(shù):%d\n",leafcount(root));printf("非葉子結(jié)點(diǎn)個(gè)數(shù):%d\n",notleafcount(root));printf("具有雙孩子結(jié)點(diǎn)個(gè)數(shù):%d\n",twosoncount(root));printf("具有單孩子結(jié)點(diǎn)個(gè)數(shù):%d\n",onesoncount(root));}#include"iostream.h"#include"stdlib.h"#include"conio.h"#include"stdio.h"char*str="";//二叉樹結(jié)點(diǎn)的定義typedefstructBTNode{chardata;structBTNode*lc;structBTNode*rc;}BTNode,*BiTree;//教材P131算法6.4：二叉樹的建立voidCreat(BiTree&T){charch;ch=getche();//cin.get(ch);if(ch=='@')T=NULL;else{T=newBTNode;T->data=ch;Creat(T->lc);Creat(T->rc);}}//先序遍歷voidPreOrder(BiTreeT){inti=0;if(T){cout<<T->data<<'';str[i]=T->data;i++;PreOrder(T->lc);PreOrder(T->rc);}}//中序遍歷voidInOrder(BiTreeT){if(T){InOrder(T->lc);cout<<T->data<<'';InOrder(T->rc);}}//后序遍歷voidPostOrder(BiTreeT){if(T){PostOrder(T->lc);PostOrder(T->rc);cout<<T->data<<'';}}voidmain(){intc;BiTreeT;printf("Inputnodesofbinarytree:(NULL<=>'@')\n");Creat(T);while(1){cout<<"\nPleaseselectaservice:\n";cout<<"\n1:PreOrderTraverse\n2:InOrderTraverse\n3:PostOrderTraverse\n0:Exit\n";cin>>c;switch(c){case1:{cout<<"\nPreOrdertraverse:\n";PreOrder(T);break;}case2:{cout<<"\nInOrdertraverse:\n";InOrder(T);break;}case3:{cout<<"\nPostOrdertraverse:\n";PostOrder(T);break;}default:{cout<<"GameOver!\n";exit(1);}}}}#include"stdio.h"#include"string.h"#defineNULL0typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreate(BiTreeT){charch;ch=getchar();if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))printf("Error!");T->data=ch;T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}returnT;}voidP