二叉樹實驗報告及代碼

重慶交通大學綜合性設計性實驗報告姓名姚遠學號631106060113班級：計信息一班實驗項目名稱：二叉樹實驗項目性質：設計性實驗實驗所屬課程：數(shù)據(jù)結構實驗室(中心)：407機房指導教師：魯云平實驗完成時間：2013年5月10日一、實驗目的1.建立二叉樹2.計算結點所在的層次3.統(tǒng)計結點數(shù)量和葉結點數(shù)量4.計算二叉樹的高度5.計算結點的度6.找結點的雙親和子女7.二叉樹的遍歷8.二叉樹的輸出等等二、實驗內容及要求1.二叉樹的結點結構,二叉樹的存儲結構由學生自由選擇和設定2.實驗完成后上交打印的實驗報告,報告內容與前面所給定的實驗模板相同3.將實驗報告電子版和源代碼在網(wǎng)絡教學平臺提交三、實驗設備及軟件VISUALC++軟件四、設計方案㈠題目（老師給定或學生自定）二叉樹的應用㈡設計的主要思路在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（leftsubtree）和“右子樹”（rightsubtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。二叉樹的每個結點至多只有二棵子樹(不存在出度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的i-1次方個結點；深度為k的二叉樹至多有2^(k)-1個結點；對任何一棵二叉樹T，如果其終端結點數(shù)(即葉子結點數(shù))為n0，出度為2的結點數(shù)為n2，則n0=n2+1。㈢主要功能實現(xiàn)二叉樹的各項操作。五、主要代碼#include<iostream.h>#include<stdio.h>#include<stdlib.h>typedefstructBinTreeNode//二叉樹結點類定義{ chardata; //數(shù)據(jù)域BinTreeNode*leftChild,*rightChild;//左子女、右子女鏈域}*BTree;BinTreeNode*p,*q,*f;intNodeNum,Leaf;intNodeDu,nodeloc=1;voidCreateBinTree(BTree&T);voidpreOrder(BTreeT);voidinOrder(BTreeT);voidpostOrder(BTreeT);intTreeNodes(BTreeT);intLeafNodes(BTreeT);intTreeNodedu(BTreeT,charch);voidNodeLoc(BTreeT,charc,intnodeloc);intHeight(BTreeT);BTreeParent(BTreeT,charc);BTreeNodeRC(BTreeT,charc);BTreeNodeLC(BTreeT,charc);voidCreateBinTree(BTree&T){charitem; cin>>item;if(item!='#') { T=(BTree)malloc(sizeof(BinTreeNode)); T->data=item; if(T==NULL) { cerr<<"存儲分配錯誤!"<<endl; exit(1); } CreateBinTree(T->leftChild); //遞歸建立左子樹 CreateBinTree(T->rightChild);//遞歸建立右子樹 } else T=NULL; };voidinOrder(BTreeT){if(T!=NULL) {inOrder(T->leftChild);//遍歷左子樹cout<<T->data<<""; inOrder(T->rightChild);//遍歷右子樹 }};voidpreOrder(BTreeT){if(T!=NULL) { cout<<T->data<<""; preOrder(T->leftChild);//遍歷左子樹 preOrder(T->rightChild);//遍歷右子樹 }};voidpostOrder(BTreeT){if(T!=NULL) { postOrder(T->leftChild); //遍歷左子樹 postOrder(T->rightChild); //遍歷右子樹 cout<<T->data<<""; }};intTreeNodes(BTreeT)//利用二叉樹后序遍歷算法計算二叉樹的結點個數(shù){inthl,hr; if(T!=NULL) { hl=TreeNodes(T->leftChild); hr=TreeNodes(T->rightChild); NodeNum=NodeNum+1; returnNodeNum; }};intLeafNodes(BTreeT)//利用二叉樹后序遍歷算法計算二叉樹的葉結點個數(shù){ if(T!=NULL) { LeafNodes(T->leftChild); LeafNodes(T->rightChild); if(T->leftChild==NULL&&T->rightChild==NULL) Leaf=Leaf+1; } returnLeaf;};intTreeNodedu(BTreeT,charch){ if(T==NULL) returnNULL; else { if(T->data==ch&&T->leftChild!=NULL&&T->rightChild==NULL) NodeDu=1; elseif(T->data==ch&&T->rightChild!=NULL&&T->leftChild==NULL) NodeDu=1; elseif(T->data==ch&&T->leftChild!=NULL&&T->rightChild!=NULL) NodeDu=2; elseif(T->data==ch&&T->leftChild==NULL&&T->rightChild==NULL) NodeDu=0; TreeNodedu(T->leftChild,ch); TreeNodedu(T->rightChild,ch); returnNodeDu; }}voidNodeLoc(BTreeT,charc,intnodeloc){if(T!=NULL) { if(T->data==c) cout<<nodeloc<<endl; NodeLoc(T->leftChild,c,nodeloc+1); NodeLoc(T->rightChild,c,nodeloc+1); }};intHeight(BTreeT)//利用二叉樹后序遍歷算法計算二叉樹的高度{ inthl,hr,hm;if(T==NULL) return0; //空樹高度為0 else { hl=Height(T->leftChild);hr=Height(T->rightChild); hm=hl>hr?hl:hr; return(hm+1); }};BTreeParent(BTreeT,charc){BTreep; if(T==NULL)returnNULL;if((T->leftChild!=NULL&&T->leftChild->data==c)||(T->rightChild!=NULL&&T->rightChild->data==c)) returnT; //找到,返回父結點地址else { if((p=Parent(T->leftChild,c))!=NULL) returnp;//遞歸在左子樹中搜索 else returnParent(T->rightChild,c);//遞歸在左子樹中搜索 } returnNULL;};BTreeNodeLC(BTreeT,charc){ if(T==NULL)returnNULL;elseif(T->data==c) { if(T->leftChild) { returnT->leftChild; } } else { if(NodeLC(T->leftChild,c)!=NULL) returnNodeLC(T->leftChild,c); elseif(NodeLC(T->rightChild,c)!=NULL) returnNodeLC(T->rightChild,c); else returnNULL; }}BTreeNodeRC(BTreeT,charc){ if(T==NULL)returnNULL;elseif(T->data==c) { if(T->rightChild) { returnT->rightChild; } } else { if(NodeRC(T->leftChild,c)!=NULL) returnNodeRC(T->leftChild,c); elseif(NodeRC(T->rightChild,c)!=NULL) returnNodeRC(T->rightChild,c); else returnNULL; }}voidmain(){ BTreeT; intnodes,leafnodes,height,nodedu; cout<<"創(chuàng)建二叉樹，請輸入完全二叉樹的先序序列，用'#'代表虛結點:"<<endl; CreateBinTree(T); inti; do{ cout<<"****************1:輸出前序遍歷結果************************"<<endl; cout<<"****************2:輸出中序遍歷結果************************"<<endl; cout<<"****************3:輸出后序遍歷結果************************"<<endl; cout<<"****************4:輸出二叉樹的高度************************"<<endl; cout<<"****************5:輸出二叉樹的結點數(shù)**********************"<<endl; cout<<"****************6:輸出二叉樹的葉結點數(shù)********************"<<endl; cout<<"****************7:輸出二叉樹任意結點的度數(shù)****************"<<endl; cout<<"****************8:輸出二叉樹任意結點所在層次**************"<<endl; cout<<"****************9:輸出二叉樹任意結點的雙親結點值**********"<<endl; cout<<"****************10:輸出二叉樹任意結點的子女結點值*********"<<endl; cout<<"****************11:退出程序*******************************"<<endl; cout<<"請輸入要執(zhí)行的功能代碼的編號（1-10）："<<endl; cin>>i; cout<<endl; switch(i) { case1: cout<<"前序遍歷結果為:"<<endl; preOrder(T); break; case2: cout<<"中序遍歷結果為:"<<endl; inOrder(T); break; case3: cout<<"后序遍歷結果為:"<<endl; postOrder(T); break; case4: height=Height(T); cout<<"二叉樹的高度為："<<height<<endl; break; case5: nodes=TreeNodes(T); cout<<"二叉樹的結點數(shù)為："<<nodes<<endl; break; case6: leafnodes=LeafNodes(T); cout<<"二叉樹的葉結點數(shù)為："<<leafnodes<<endl; break; case7: charch1; cout<<"請輸入該結點的值