數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-二叉樹(shù)

《算法與數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報(bào)告教師評(píng)閱意見(jiàn)：簽名：年月曰實(shí)驗(yàn)成績(jī)：一、實(shí)驗(yàn)?zāi)康?、實(shí)現(xiàn)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)2、熟悉二叉樹(shù)基本術(shù)語(yǔ)的含義3、掌握二叉樹(shù)相關(guān)操作的具體實(shí)現(xiàn)方法二、實(shí)驗(yàn)內(nèi)容及要求1.建立二叉樹(shù)計(jì)算結(jié)點(diǎn)所在的層次統(tǒng)計(jì)結(jié)點(diǎn)數(shù)量和葉結(jié)點(diǎn)數(shù)量計(jì)算二叉樹(shù)的高度計(jì)算結(jié)點(diǎn)的度找結(jié)點(diǎn)的雙親和子女二叉樹(shù)前序、中序、后序遍歷的遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)及層次遍歷二叉樹(shù)的復(fù)制二叉樹(shù)的輸出等三、系統(tǒng)分析（1）數(shù)據(jù)方面：該二叉樹(shù)數(shù)據(jù)元素采用字符char型，并且約定“#”作為二叉樹(shù)輸入結(jié)束標(biāo)識(shí)符。并在此基礎(chǔ)上進(jìn)行二叉樹(shù)相關(guān)操作。（2）功能方面：能夠?qū)崿F(xiàn)二叉樹(shù)的一些基本操作，主要包括：采用廣義表建立二叉樹(shù)。計(jì)算二叉樹(shù)高度、統(tǒng)計(jì)結(jié)點(diǎn)數(shù)量、葉節(jié)點(diǎn)數(shù)量、計(jì)算每個(gè)結(jié)點(diǎn)的度、結(jié)點(diǎn)所在層次。判斷結(jié)點(diǎn)是否存在二叉樹(shù)中。尋找結(jié)點(diǎn)父結(jié)點(diǎn)、子女結(jié)點(diǎn)。遞歸、非遞歸兩種方式輸出二叉樹(shù)前序、中序、后序遍歷。進(jìn)行二叉樹(shù)的復(fù)制。四、系統(tǒng)設(shè)計(jì)（1）設(shè)計(jì)的主要思路二叉樹(shù)是的結(jié)點(diǎn)是一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根節(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)、互不相交的二叉樹(shù)組成。根據(jù)實(shí)驗(yàn)要求，以及課上老師對(duì)于二叉樹(shù)存儲(chǔ)結(jié)構(gòu)、基本應(yīng)用的講解，同時(shí)課后研究書(shū)中涉及二叉樹(shù)代碼完成二叉樹(shù)模板類(lèi)，并將所需實(shí)現(xiàn)各個(gè)功能代碼編寫(xiě)完成，在建立菜單對(duì)功能進(jìn)行調(diào)試。（2）數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)有數(shù)組方式和鏈表方式。但用數(shù)組來(lái)存儲(chǔ)二叉樹(shù)有可能會(huì)消耗大量的存儲(chǔ)空間，故在此選用鏈表存儲(chǔ)，提高存儲(chǔ)空間的利用率。根據(jù)二叉樹(shù)的定義，二叉樹(shù)的每一個(gè)結(jié)點(diǎn)可以有兩個(gè)分支，分別指向結(jié)點(diǎn)的左、右子樹(shù)。因此，二叉樹(shù)的結(jié)點(diǎn)至少應(yīng)包括三個(gè)域，分別存放結(jié)點(diǎn)的數(shù)據(jù)，左子女結(jié)點(diǎn)指針,右子女結(jié)點(diǎn)指針。這將有利于查找到某個(gè)結(jié)點(diǎn)的左子女與右子女，但要找到它的父結(jié)點(diǎn)較為困難。該實(shí)驗(yàn)采取二叉鏈表存儲(chǔ)二叉樹(shù)中元素，具體二叉樹(shù)鏈表表示如下圖所示。leftChlidrightChild圖1二叉樹(shù)的鏈表表示（3）基本操作的設(shè)計(jì)二叉樹(shù)關(guān)鍵主要算法：利用廣義表進(jìn)行二叉樹(shù)的建立。該算法首先通過(guò)重載輸入符號(hào)，在重載函數(shù)中調(diào)用CreatBinTree函數(shù)，該函數(shù)有兩個(gè)參數(shù)，第一個(gè)參數(shù)為輸入流，用于傳遞用戶輸入的二叉樹(shù)字符串，第二個(gè)參數(shù)則是二叉樹(shù)的根結(jié)點(diǎn)root。再通過(guò)棧操作是實(shí)現(xiàn)二叉樹(shù)。遞歸與非遞歸兩種方式實(shí)現(xiàn)前序、中序、后序的遍歷。遞歸實(shí)現(xiàn)三種遍歷的函數(shù)均只有一個(gè)參數(shù)即二叉樹(shù)根節(jié)點(diǎn)root，遞歸結(jié)束條件則是結(jié)點(diǎn)為空。當(dāng)結(jié)點(diǎn)不為空時(shí)，根據(jù)三種遍歷的方式不同而代碼順序不同。其中前序遍歷訪問(wèn)結(jié)點(diǎn)順序是：根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)；中序遍歷訪問(wèn)結(jié)點(diǎn)順序是：左子樹(shù)、根結(jié)點(diǎn)、右子樹(shù)；后序遍歷訪問(wèn)結(jié)點(diǎn)順序是：左子樹(shù)、右子樹(shù)、根結(jié)點(diǎn)。具體算法以及流程圖見(jiàn)報(bào)告實(shí)驗(yàn)分析部分。涉及二叉樹(shù)性質(zhì)的一些計(jì)算例如樹(shù)的高度，結(jié)點(diǎn)所處層次，結(jié)點(diǎn)的度等。在進(jìn)行二叉樹(shù)相關(guān)性質(zhì)計(jì)算函數(shù)中參數(shù)為二叉樹(shù)根節(jié)點(diǎn)root，再通過(guò)需要計(jì)算不同性質(zhì)實(shí)現(xiàn)不同遞歸代碼。需要注意的是不同計(jì)算的遞歸結(jié)束條件不同。對(duì)于結(jié)點(diǎn)父節(jié)點(diǎn)與子女結(jié)點(diǎn)的尋找。對(duì)于結(jié)點(diǎn)父結(jié)點(diǎn)與子女結(jié)點(diǎn)的查找函數(shù)均有2個(gè)參數(shù)，一個(gè)是二叉樹(shù)根結(jié)點(diǎn)root以及需要查找結(jié)點(diǎn)的數(shù)據(jù)域data。具體實(shí)現(xiàn)方式是通過(guò)遞歸遍歷每一個(gè)二叉樹(shù)結(jié)點(diǎn)，當(dāng)匹配到需要查找結(jié)點(diǎn)數(shù)據(jù)域時(shí)再進(jìn)行對(duì)于該結(jié)點(diǎn)父結(jié)點(diǎn)或子女結(jié)點(diǎn)的輸出，若未匹配成功則輸出二叉樹(shù)中不存在該結(jié)點(diǎn)。五、編程環(huán)境與實(shí)驗(yàn)步驟（1）編程環(huán)境操作系統(tǒng)：Windows操作系統(tǒng)；編程工具軟件：VisualStudio2017（2）實(shí)驗(yàn)步驟程序相關(guān)文件有：BinTreeNode.h、BinaryTree.h、Queue.h、SeqStack.h四個(gè)頭文件以及主函數(shù)調(diào)試文件main.cpp（3）編譯參數(shù)無(wú)編譯參數(shù)，在Vs2017或其他版本中新建項(xiàng)目然后將程序相關(guān)文件添加到解決方案中對(duì)應(yīng)位置中調(diào)試即可。六、實(shí)現(xiàn)代碼#include"BinTreeNode.h"#include"SeqStack.h"#include"Queue.h"enumtag{L,R};externintnumber;externboolflag;externboolflag1;externboolflag2;template<classT>classBinaryTree{public:BinTreeNode<T>*root;//二叉樹(shù)根指針TRefValue;//數(shù)據(jù)輸入停止標(biāo)志public:BinaryTree（）{root=NULL;}BinaryTree（Tvalue）{root=NULL;RefValue=value;}

BinaryTree(BinaryTree<T>&s){root=Copy(s.root);}//復(fù)制構(gòu)造函數(shù)BinTreeNode<T>*Copy(BinTreeNode<T>*orignode);~BinaryTree(){destroy(root);}voiddestroy(BinTreeNode<T>*&subTree);voidFind_Father(BinTreeNode〈T〉*(&subTree),Tdata);//找父節(jié)點(diǎn)voidFind_Children(BinTreeNode<T>*(&subTree),Tdata);//找子女節(jié)點(diǎn)voidFind(BinTreeNode<T〉*(&subTree),Tdata);//查找結(jié)點(diǎn)intHeight(BinTreeNode<T〉*subTree); //返回樹(shù)高度intSize(BinTreeNode<T〉*subTree); //返回結(jié)點(diǎn)數(shù)//返回結(jié)點(diǎn)所在層次//返回結(jié)點(diǎn)的度以及葉節(jié)點(diǎn)//取根voidlevel(BinTreeNode<T〉*subTree);//返回結(jié)點(diǎn)所在層次//返回結(jié)點(diǎn)的度以及葉節(jié)點(diǎn)//取根voidDujisuan(BinTreeNode<T〉*subTree);個(gè)數(shù)BinTreeNode<T〉*getRoot(){returnroot;}boolIsempty(){return(root==NULL)?true:false;} //判二叉樹(shù)是否為空voiddgpreOrder(BinTreeNode<T〉*subTree);//遞歸實(shí)現(xiàn)前序遍歷voiddginOrder(BinTreeNode<T〉*subTree); //遞歸實(shí)現(xiàn)中序遍歷voiddgpostOrder(BinTreeNode<T〉*subTree); //遞歸實(shí)現(xiàn)后序遍歷voidPrintBTree(BinTreeNode<T〉*BT);voidpreOrder(BinTreeNode<T〉*subTree); //非遞歸實(shí)現(xiàn)前序遍歷voidinOrder(BinTreeNode<T〉*subTree); //非遞歸實(shí)現(xiàn)中序遍歷voidpostOrder(BinTreeNode<T〉*subTree); //非遞歸實(shí)現(xiàn)后序遍歷voidCreateBinTree(istream&in,BinTreeNode<T〉*&BT);voidTraverse(BinTreeNode<T〉*subTree,ostream&out);template<classT〉friendistream&operator〉〉(istream&in,BinaryTree<T〉&Tree); //重載操作：輸入template<classT〉friendostream&operator<<(ostream&out,BinaryTree<T〉&Tree); //重載操作：輸出};template<classT〉voidBinaryTree<T〉::destroy(BinTreeNode<T〉*&subTree){if(subTree!=NULL){destroy(subTree-〉leftChild);destroy(subTree-〉rightChild);deletesubTree;}}template<classT〉voidBinaryTree<T〉::CreateBinTree(istream&in,BinTreeNode<T〉*&BT){SeqStack<BinTreeNode<T〉*〉s;BT=NULL;//置空二叉樹(shù)BinTreeNode<T>*p,*t;intk=0;Tch;in>>ch;while(ch!=RefValue){switch(ch){case'(':s.Push(p);k=1;break;case')':s.Pop(t);break;case',':k=2;break;default:p=newBinTreeNode<T>(ch);if(BT==NULL)BT=p;elseif(k==1){s.getTop(t);t->leftChild=p;}if(k==2){s.getTop(t);t->rightChild=p;}}in>>ch;}}template<classT>voidBinaryTree<T>::Traverse(BinTreeNode<T>*subTree,ostream&out){if(subTree!=NULL){out<<subTree->data<<"";Traverse(subTree->leftChild,out);Traverse(subTree->rightChild,out);}}template<classT>voidBinaryTree<T>::dginOrder(BinTreeNode<T>*subTree){if(subTree!=NULL){dginOrder(subTree->leftChild);cout<<subTree->data<<"";dginOrder(subTree->rightChild);}}template<classT>voidBinaryTree<T>::dgpostOrder(BinTreeNode<T>*subTree){if(subTree!=NULL){dgpostOrder(subTree->leftChild);dgpostOrder(subTree->rightChild);cout<<subTree->data<<"";template<classT>voidBinaryTree<T>::dgpreOrder(BinTreeNode<T>*subTree){if(subTree!=NULL){cout<<subTree->data<<"";dgpreOrder(subTree->leftChild);dgpreOrder(subTree->rightChild);}}template<classT>intBinaryTree<T>::Height(BinTreeNode<T>*subTree){if(subTree==NULL)return0;else{inti=Height(subTree->leftChild);intj=Height(subTree->rightChild);return(i<j)?j+1:i+1;}}template<classT>intBinaryTree<T>::Size(BinTreeNode<T>*subTree){if(subTree==NULL)return0;elsereturn1+Size(subTree->leftChild)+Size(subTree->rightChild);}template<classT>voidBinaryTree<T>::PrintBTree(BinTreeNode<T>*BT){if(BT!=NULL){cout<<BT->data;if(BT->leftChild!=NULL||BT->rightChild!=NULL){cout<<"(";PrintBTree(BT->leftChild);cout<<",";if(BT->rightChild!=NULL)PrintBTree(BT->rightChild);cout<<")";}}}template<classT>voidBinaryTree<T>::preOrder(BinTreeNode<T>*subTree){SeqStack<BinTreeNode<T>*>S;BinTreeNode<T>*p=subTree;BinTreeNode<T>*n=NULL;S.Push(n);while(p!=NULL){cout<<p->data<<"";if(p->rightChild!=NULL)S.Push(p->rightChild);if(p->leftChild!=NULL)p=p->leftChild;elseS.Pop(p);}}template<classT>voidBinaryTree<T>::inOrder(BinTreeNode<T>*subTree){SeqStack<BinTreeNode<T>*>S;BinTreeNode<T>*p=root;BinTreeNode<T>*n=NULL;S.Push(n);do{while(p!=NULL){S.Push(p);p=p->leftChild;}if(!S.IsEmpty()){S.Pop(p);if(p!=n){cout<<p->data<<"";p=p->rightChild;}}}while(p!=NULL||!S.IsEmpty());}template<classT>structstkNode{BinTreeNode<T>*ptr;tagta;stkNode(BinTreeNode<T>*N=NULL):ptr(N),ta(L){}};template<classT>voidBinaryTree<T>::postOrder(BinTreeNode<T>*subTree){SeqStack<stkNode<T>>S;stkNode<T>w;BinTreeNode<T>*p=root;do{while(p!=NULL){w.ptr=p;w.ta=L;S.Push(w);p=p->leftChild;}intcontinuel=1;while(continuel&&!S.IsEmpty()){S.Pop(w);p=w.ptr;switch(w.ta){caseL:w.ta=R;S.Push(w);continuel=0;p=p->rightChild;break;caseR:cout<<p->data<<"";break;}}}while(!S.IsEmpty());cout<<endl;}template<classT>istream&operator>>(istream&in,BinaryTree<T>&Tree){Tree.CreateBinTree(in,Tree.root);returnin;}template<classT>ostream&operator<<(ostream&out,BinaryTree<T>&Tree){out<<"二叉樹(shù)的前序遍歷"<<endl;Tree.Traverse(Tree.root,out);out<<endl;returnout;}template<classT>BinTreeNode<T>*BinaryTree<T>::Copy(BinTreeNode<T>*orignode){if(orignode==NULL)returnNULL;BinTreeNode<T>*temp=newBinTreeNode<T>;temp->data=orignode->data;temp->leftChild=Copy(orignode->leftChild);temp->rightChild=Copy(orignode->rightChild);returntemp;}template<classT>voidBinaryTree<T>::level(BinTreeNode<T>*subTree){if(subTree==NULL)return;else{Queue<BinTreeNode<T>*>Q;BinTreeNode<T>*n;n=NULL;Q.EnQueue(subTree);Q.EnQueue(n);intlevel=1;while(!Q.IsEmpty()){BinTreeNode<T>*node;Q.DeQueue(node);if(NULL==node){if(Q.IsEmpty())break;level++;Q.EnQueue(n);continue;}cout<<"第"<<level<<"層結(jié)點(diǎn):"<<node->data<<endl;if(NULL!=node->leftChild)Q.EnQueue(node->leftChild);if(NULL!=node->rightChild)Q.EnQueue(node->rightChild);}}}template<classT>voidBinaryTree<T>::Dujisuan(BinTreeNode<T>*subTree){if(subTree==NULL)return;else{Queue<BinTreeNode<T>*>Q;intcount=-1;Q.EnQueue(subTree);while(!Q.IsEmpty()){BinTreeNode<T>*node;Q.DeQueue(node);if(node->leftChild!=NULL&&node->rightChild!=NULL)count=2;elseif(node->leftChild==NULL&&node->rightChild==NULL){count=0;number++;}elsecount=1;cout<<node-〉data〈〈"的度為："〈〈count〈〈endl;if(NULL!=node->leftChild)Dujisuan(node->leftChild);if(NULL!=node->rightChild)Dujisuan(node->rightChild);}}}template<classT>voidBinaryTree〈T〉：：Find_Father(BinTreeNode〈T〉*(&subTree),Tdata)//找父節(jié)點(diǎn)利用了遞歸的思想，基本結(jié)構(gòu)還是前序遍歷{if(subTree==NULL)return;if(subTree-〉leftChild!=NULL)//當(dāng)左孩子存在的時(shí)候才進(jìn)行判斷，否則程序出錯(cuò){if(subTree-〉leftChild-〉data==data){cout<<"該節(jié)點(diǎn)的父結(jié)點(diǎn)是："<<subTree-〉data<<endl;flag=true;//全局變量設(shè)置了一個(gè)標(biāo)志flag=false，如果找到父結(jié)點(diǎn)，則flag賦值為true}}if(subTree-〉rightChild!=NULL)//如左子樹(shù)所示{if(subTree-〉rightChild-〉data==data){cout<<"該節(jié)點(diǎn)的父結(jié)點(diǎn)是："<<subTree-〉data<<endl;flag=true;}}Find_Father(subTree-〉leftChild,data);Find_Father(subTree-〉rightChild,data);}template<classT〉voidBinaryTree〈T〉：：Find_Children(BinTreeNode〈T〉*(&subTre),Tdata)//找子女節(jié)點(diǎn)利用了遞歸的思想，基本結(jié)構(gòu)還是前序遍歷{if(subTree==NULL)return;else{if(subTree-〉data==data){flag2=true;//全局變量設(shè)置了一個(gè)標(biāo)志flag2=false,如果找到父結(jié)點(diǎn)，則flag2賦值為trueif(subTree->leftChild!=NULL){cout<<"該節(jié)點(diǎn)的左子女結(jié)點(diǎn)是:"<<subTree->leftChild->data<<endl;}if(subTree->rightChild!=NULL){cout<<"該節(jié)點(diǎn)的右子女結(jié)點(diǎn)是:"<<subTree->rightChild->data<<endl;}if(subTree->leftChild==NULL){cout<<"該節(jié)點(diǎn)的左子女結(jié)點(diǎn)為空"<<endl;}if(subTree->rightChild==NULL){cout<<"該節(jié)點(diǎn)的右子女結(jié)點(diǎn)為空"<<endl;}}else{Find_Children(subTree->leftChild,data);Find_Children(subTree->rightChild,data);}}}template<classT>voidBinaryTree<T>::Find(BinTreeNode<T>*(&subTree),Tdata){if(subTree==NULL)return;else{if(subTree->data==data)flag1=true;else{Find(subTree->leftChild,data);Find(subTree->rightChild,data);}}}七、測(cè)試結(jié)果與說(shuō)明菜單界面：

:夏射的応半操柞 1.述立 2：HW:賓樹(shù)離度 3:址卄站點(diǎn)藪址 勺：汁算站點(diǎn)的度歴尸節(jié)點(diǎn)數(shù)M 』：汁弊站點(diǎn)所在層決 心判斷站點(diǎn)是否在：更樹(shù)中 7：?找站亢璽姑山 氏：』找給點(diǎn)荘子女納匕 9*更樹(shù)軫山 10:'.ZW的缶序洞歷輸出遍UI買(mǎi)現(xiàn) 11：：更射閭小用他歷端出誦UI哦現(xiàn) 12:：義時(shí)怖汗庁遢側(cè)軸出期歸實(shí)現(xiàn) 13：:臾射的訶庁過(guò)側(cè)輛川11閒01實(shí)現(xiàn) 14::屋射的屮庁前切輸山#過(guò)』I蟲(chóng)現(xiàn) is-■.^wnuii-庁迪冊(cè)輸山也血！n生觀 ⑹対的癥制 1T:退山:； SSaSS*^!^?］*********?二叉樹(shù)建立::叉樹(shù)的毘本操作1:建匸二叉樹(shù)—— 2：計(jì)算:義樹(shù)高度 3：統(tǒng)計(jì)結(jié)點(diǎn)數(shù)量 -4:計(jì)算結(jié)點(diǎn)的度及葉節(jié)點(diǎn)數(shù)量--5:汁算結(jié)點(diǎn)所在層探 -6：判斷結(jié)心是rf/1--叉樹(shù)巾- 7:亍找結(jié)點(diǎn)父結(jié)點(diǎn) 8：詁找結(jié)點(diǎn)其子女結(jié)點(diǎn) 9：二義樹(shù)輸出 io：二叉樹(shù)的前序遍歷輸岀遞歸實(shí)現(xiàn)一［遞01實(shí)現(xiàn)一 d遞！/I實(shí)現(xiàn)--：：：1：IT二出菲遞歸實(shí)現(xiàn)啲屮序遍歷輸出1f的斤序遍刃輸出非通歸實(shí)現(xiàn)111213二叉樹(shù)的中序遍歷輸出的啟序遍厲鞠的前蘿遍jffiSii-叉椀14:：叉標(biāo)1516：樹(shù)的方制17:退出：-；；；：：：：：：、：、請(qǐng)輸入你的i^ff/1-171：1輸入廣義壷建立二叉樹(shù)：a￡b（d（gJ,e（h」），c（f（」）」博程樹(shù)完成］?統(tǒng)計(jì)結(jié)點(diǎn)數(shù)量:統(tǒng)計(jì)結(jié)點(diǎn)數(shù)量:二叉樹(shù)高度計(jì)算: 二貝樹(shù)恂卑車(chē)捉件 1：準(zhǔn)立1￥^ 士訐煤次鉗祐成 3:如卜粘點(diǎn)戟旺 霽訃報(bào)琳點(diǎn)(即星如F戈點(diǎn)款斌 5：訃哥外點(diǎn)睛住圧找 枳列葩姑點(diǎn)啟許在：冥崗屮 7:"找站點(diǎn)父鈿玄; S:丄找結(jié)點(diǎn)M『立結(jié)點(diǎn) 廠■艾輸細(xì)】 16：：夏射詁訕皆過(guò)肪卿I血ui啦現(xiàn) 11：艾射的屮申堀山箱；|］塢!JI實(shí)觀 12::義樹(shù)的躲用謝疔輸||\訥?；颥F(xiàn) 13；_更樹(shù)恂前廳辿的輸Ih非誦舊賓現(xiàn) 14. wisui^ 15::里啟的拆川過(guò)肪體淇Wising現(xiàn) L&:樹(shù)的塑制 L丁：jy”h 4>0|0|44MR朋R*4>o|ol4RRRRm*4>：?4m*RRRHoMo|oM<tiR0*btHo|o|o|o|oHaPPPm轉(zhuǎn)i酬ft人誓:們選抒【1-;門(mén)：謨樹(shù)社庸廈旳： :夏材的耳母提作 1：建立二丈護(hù) 』:：計(jì)算.XHrtJiC ?斑ii站山獨(dú)M: j計(jì)鏑點(diǎn)跑度矗葉*點(diǎn)數(shù)1卜 5:訃算結(jié)點(diǎn)所任圧出 6:判商注點(diǎn)昂仰冼-.JtM'l'— -.$崔站點(diǎn)父汕點(diǎn) 念.』找緒點(diǎn)其早女拈點(diǎn); ：_Jt 芮輸 ll1, m 1：- L2： 13： 14_ 15: l&MfMjj 17：iUll\;X** ***?=^c**H=M=B**?=?**”W=fc***?=&**H=M=B”*?=I=B**>^=l=t請(qǐng)輸入臨的進(jìn)擇［l-l?h站IEJMI11過(guò)川徘HlJSil［尖現(xiàn)一阿刊屮jj幟」怖卅闕號(hào)理一:的后序遍加輸II闔！I烘現(xiàn)一:菱.X:玄新的⑥」i輸山垃甘麺比制 結(jié)點(diǎn)度計(jì)算以及葉節(jié)點(diǎn)數(shù)量:該捕菇點(diǎn)數(shù)童為T(mén)9結(jié)點(diǎn)所在層次計(jì)算:iffiff的I卩IF吩為樹(shù)岀14〕'j實(shí)觀一JCWm'l'i^.UjWJiKjiiu^^—更M帕M庁唱山備：I】堪I11實(shí)現(xiàn)一XWWilOimuj?lli韭熾U(xiǎn)1先觀一埜禪的中庁堵國(guó)埔出|=腳】實(shí)與一蟲(chóng)甘51后廳遍.Uj輸山■:刪I梟鬼一-:蠱囲的基豐隹臨一 ］；jti:更擁 ；：訃邯ixwrtJit 艶班訃結(jié)戊皴訃 船訃片第戊帕度以?：w點(diǎn)散試 5：nrrsAAfiirfL^ T:苕醱點(diǎn)鼻青在二又樹(shù)中一 7:J拙姑戌父站點(diǎn) 總:胡羽結(jié)貞H騎止 血股何響侖&出山樹(shù)|僦01實(shí)理 II：；艾樹(shù)的屮序JB.M輸川謝UI實(shí)理 12:Jt射曲汗庁追山軸lh訥叮實(shí)現(xiàn) 13::兄媽聞和衍創(chuàng)山軸IIIII：逵|1珅；膽 ：聖：黑罰啊小序?yàn)殄絴|：軸山抵觀 15:嗔樹(shù)的心Z0.U-i輸||}||：坯［1琥應(yīng) 疋胃的殳制 ］7：］^>||： 口忖導(dǎo)■口 ■口口.忖忖域■口口峙■口 吋*請(qǐng)輸A悔的ASL1-17］； :哭榊的加本操邯 ］址錄：里斑 2:l|J7LXWrtt'J. $扯LI細(xì) 小辣菇國(guó)兩度盤(pán)才節(jié)點(diǎn) $;訃外結(jié)點(diǎn)聽(tīng)在出祝——- 7一冏曲結(jié)點(diǎn)址吾圧'.X^IJ- 7:尋找錯(cuò)點(diǎn)$￡嘉A 心尋找站點(diǎn)礎(chǔ)F女銷(xiāo)點(diǎn)—— -二XHKi出 10：二— 11：- 12：- 13:二 14；— 15:二 ic-wiH)^iw 1?叮出：一4=n矚事4=|工￡4=l=i：￡￡4=i=S：￡#iH昭事=t=US常4=??！?=口桔注=常事=中席屮瑤京4=口聃*i陽(yáng)《人陽(yáng)的選并【1-17】=E--?■.>9-■-IE--■-.貢r(shí)araltlli.ltt■應(yīng)rsra-対的的的的的射躬的恥］k汕山:第電翎i處I'JrJi

第軋；糾船:DR-FG查找結(jié)點(diǎn)是否在樹(shù)中::冥樹(shù)的幕本燥作 I；建/：叉稠 2：計(jì)算二叉樹(shù)高度 3：觥計(jì)軸點(diǎn)數(shù)量 4:計(jì)尊站點(diǎn)的度及葉節(jié)點(diǎn)數(shù)雖 打:計(jì)算站點(diǎn)所花接次 &判斷結(jié)點(diǎn)是否在：：叉樹(shù)屮一7：尋找站點(diǎn)父結(jié)點(diǎn) 8：尋找站點(diǎn)實(shí)F女結(jié)點(diǎn)9::叉樹(shù)輸出 10::義樹(shù)的就序遍M輸出遞歸實(shí)現(xiàn)一11:二叉樹(shù)的中序遍刃輸他型JU實(shí)現(xiàn)-?12：更樹(shù)旳甘仔遲M輸出通,丈現(xiàn)--13:瑕樹(shù)的詢(xún)宇遍Uj輪出IE遞M實(shí)現(xiàn)14:二叉樹(shù)的中序遍刃輸出非違歸實(shí)現(xiàn)1Q.叉岡的后庁詭彷輸書(shū)II邇01實(shí)現(xiàn)1氐材前復(fù)制 口:退出； 宰宰宰**輩諮宰宰**累笨宰常寧宰宰卑宰**器笨宰卑輩慕卑宰容卑耳辛卑宰宰卑卑*#字宰宰卑寺*零宰■宰宰宰常謎*請(qǐng)輸入你的選擇［117'；6輸入需荽3找酣點(diǎn).數(shù)抓域：該結(jié)點(diǎn)存桿「乜一隈樹(shù)IM查找結(jié)點(diǎn)父結(jié)點(diǎn):查找結(jié)點(diǎn)子女結(jié)點(diǎn); ■.XMfi^j-4^hpfl L：建世 】；il?諾，xwfM 3:亦陽(yáng)點(diǎn)酣t 5:止朮站點(diǎn)直祜血出 &判噺綁j陞甲淞'.XW'I 7：，f找站點(diǎn)父站點(diǎn) $：6?找姑點(diǎn)H；『女甜點(diǎn) P:冥粧輸止 雖次曲的『Y遍扔輸山血ui或現(xiàn) 11：:里闿的中序堆加楷山i型說(shuō)規(guī) 12:1XM啊阻I1渥山惟；I；遞HI生理 U::更防的血庁也山惱出IIMUI實(shí)現(xiàn) 14:iXWirj'F'J^JJj播山II閭叮蟲(chóng)現(xiàn) 措垃勰計(jì)序刪矗IIMl刪I實(shí)現(xiàn) ———————^J■j￡J*|*■——————————— ■■■■ ■■■■9oK+=+：+b?■■bMoK+s■■■?+=+3o|o|*■■■■toMoK+“■■琲7:艾樹(shù)的陥屮尙冊(cè)4EDGEHCF]需熨件找卻點(diǎn)議戡域！E選『氏狗攵鮎左址:E :叉捷的陀+掃忙 ]:iJ'-i斥 2：UI?浪榊藥進(jìn) 3；統(tǒng)訃站點(diǎn)StH 4!計(jì)克駄點(diǎn)犀血&葉1VA?Ilk til竊紳點(diǎn)所A雄衣 6刈用斜:點(diǎn)堆悄:iW'l1 F：J找站點(diǎn)丈紡立 日；沖百站點(diǎn)"fit瑋點(diǎn) g‘'Xf*r^i'i! 】*：腳由前用刪瀚I(xiàn)皿01實(shí)卑一 ；l：:菟抽為屮岸竭山輸岀蜃艸咲疑一 12：:丈樹(shù)的打厲尅以胸也型U|實(shí)臣一 13;--XW^JajJ?-fij-'jSi；j'i：1：馴儀現(xiàn) ll!iXM^J'I'.'i-：血出怖H申型U1實(shí)現(xiàn) li：:更樹(shù)的黛用遍聽(tīng)輸出：1；通1）1尖現(xiàn) 圧:國(guó)時(shí)U制 「：遐II，,： ?f_t??WM*?3M?St??t~t? “2M?林”UMHfc人標(biāo)的誥擇[]-17]|:冥厠的前.字塩聽(tīng)AliDGEd：7[■.I'd^rt找:"I亡放附戰(zhàn)=遵節(jié)戍曲忘『軸點(diǎn)號(hào):D阪W點(diǎn)時(shí)和廣女昴巾匹E二叉樹(shù)輸出結(jié)果（前序）::更歯的賊牛提低i：ifei—Xn 2:tF#-XwSJK出蛻訃汕點(diǎn)毅lit 4：比殊站燈的磁葉書(shū)點(diǎn)數(shù)童 ；:匚卜京站貞所住雄機(jī) 心判啣納點(diǎn)陞和在二乂 7:丄找紬點(diǎn)丈結(jié)點(diǎn) 0;*找鮎點(diǎn)苴只立納門(mén); ：I廠浪甬亦f17網(wǎng)山衙H1堆HI除現(xiàn) ]■?.鋼耳的中Ii制加協(xié)11堆艸實(shí)現(xiàn) 12:二成射的橋用國(guó)也愉出型斡企現(xiàn) %「.艮榊的汕產(chǎn)思山愉HIII遲V哄現(xiàn) ：4：:XW的中片函山輸山II觀艸奚現(xiàn) ：5：:昊槪陌后序JH歷輸出II?迎門(mén)實(shí)現(xiàn)一16:樹(shù)恂女制 ：7:退出： 卄**屮艸*屮**41"乂沁"沁沁乂4卄**屮艸*iffWAWiift[1-171=9:巽対的前厚遍帀rtBDGEHCFI三種方式（前序、中序、后序）輸出二叉樹(shù)（遞歸）:ABDGEHCFI 二見(jiàn)側(cè)]的軀本蜒萍 —— ）：扯丸-；叉?zhèn)? -T:片彌二叉樹(shù)奇廈 ——.__乳統(tǒng)計(jì)訊険應(yīng)一——■~■—— ——.__右f燈站點(diǎn)的廈艮叫中點(diǎn)敢賊—— ——.__5；計(jì)燈軸點(diǎn)斷在底出-一-■~■—— ——.__—6:刻晰納點(diǎn)是否任二叉WI'一—— ——.__丁：邸我站必父紡點(diǎn) ■一一■—— ——.__3：店鉗銷(xiāo)貞莫子玄鈿蟲(chóng)?一-■—— 16:'■.更蔽lirJli總歷擅11陽(yáng)UI啖便 ]：：戊插旳典為輸I血曲第觀 12:'.XW^if.VirtiJJjtftll1,砂0[實(shí)理 u::SLWIW誼庁恵歷描;hII：腆rJjffi 14；:更樹(shù)帥口廳君折摘ihII：逛（H尖理 ]5：:史捕帕hi庁AJJ/ffiH；lbi￡iJ[兀罠 16:K怕it制 ”！菇出= 杠忖■忖fcf■忖fcf■忖*t?忖*t*t=t?忖E?□*7^*忖fct*忖*t*補(bǔ)*補(bǔ)*+i陽(yáng)也人馀的遠(yuǎn)丼[卜ITh11GDQSIEAFIC——.__丄號(hào)滯侗啟展掛作 ■一一■——一 ]；建立二更閒 士片?。褐錁?shù)戰(zhàn)眶 —31密訐型點(diǎn)JEIt ————_t.if?算酬點(diǎn)的墮皿葉廿也散樂(lè) ——10；——.___土才燈站點(diǎn)斷在層抉-一-一一■——一——__訂U斷瑚點(diǎn)址否在二覽甜即——一——.___7:里找站點(diǎn)囂苛點(diǎn)一_一一■——_————&；*戰(zhàn)納必M早女卸i點(diǎn)?一一■——一 二更沖舖]*|| ——10；"iwwwf電歷輸：i*.謹(jǐn).：■12:ia：14：1&;??更開(kāi)■的審.1報(bào)說(shuō)防摘出id'I｛實(shí)視-一■-穗的后｛J眉刃輸tbWi$K~?.史樹(shù)的幗子增厲輸岀IFlfiU仗現(xiàn)■.旻特的屮庁越歷摘出II：.：■12:ia：14：1&;]6：H — 杠詡b4>3Efvfcida4ci獻(xiàn)iff愉入俅的選#[i-ins12謂門(mén)實(shí)現(xiàn)-I遞門(mén)實(shí)現(xiàn)-1非遞歸實(shí)現(xiàn)[7遞UI丈現(xiàn)I二遞謂門(mén)實(shí)現(xiàn)-I遞門(mén)實(shí)現(xiàn)-1非遞歸實(shí)現(xiàn)[7遞UI丈現(xiàn)I二遞UI實(shí)現(xiàn)13：二叉樹(shù)的陸序遍歷輸；14:二叉樹(shù)的中序遍歷輸;15:二更樹(shù)的后序遍歷輸;16：樹(shù)的復(fù)制-17:退出:1:建立:叉樹(shù) 么訃事二叉樹(shù)高底 3:統(tǒng)i-結(jié)點(diǎn)裁昌 4:訃算結(jié)點(diǎn)的度及葉仃點(diǎn)數(shù)晝 ￡:計(jì)算結(jié)點(diǎn)所在層次 6;判斷站點(diǎn)是否在一義樹(shù)中-；:-十扌龍結(jié)點(diǎn)父結(jié)點(diǎn)8:尋找結(jié)點(diǎn)皿產(chǎn)女結(jié)點(diǎn)-9-:叉材輜出 ?16:二更樹(shù)的前序遍也輸出遊歸憲現(xiàn)-11:二叉樹(shù)的中序遍加輸出越歸實(shí)現(xiàn)-12：一?叉樹(shù)的肩序遍歷輸出遶歸實(shí)現(xiàn)-IT--13ABDGEHCFIGDBIIEAFIC 二叉樹(shù)的基本操作亠叉樹(shù)的基木操作 1：建心二艾樹(shù) ■2:itS】叉樹(shù)高度-3:統(tǒng)計(jì)結(jié)點(diǎn)數(shù)星 4:計(jì)算結(jié)點(diǎn)的挾及葉節(jié)點(diǎn)數(shù)量5:計(jì)算結(jié)點(diǎn)所在層冼 6:判斷結(jié)點(diǎn)是否在-更樹(shù)中一在3找結(jié)點(diǎn)父結(jié)點(diǎn) R找結(jié)點(diǎn)其了女結(jié)點(diǎn)--仝一叉樹(shù)輸出 10:-X＞的血序遍歷能；□:_義樹(shù)的申岸通厲備12:-X樹(shù)的肓序遍歷輸；13：:叉樹(shù)的前序迥歷輸出非謹(jǐn)歸實(shí)現(xiàn)14：:艮樹(shù)的中庁遍M笹出非遞[H賓現(xiàn)15：:叉材的后序遍也蠕出非遞in實(shí)現(xiàn)1土樹(shù)的復(fù)制 17:退出: 出眾#常出需*壽*巖龍#蹤常培*臨*臨*出眾#蹤*巖*將*巖培出眾#常*:臨*臨*常培#蹤常臨*臨*臨爭(zhēng)出眾#蹤*臨請(qǐng)輸入你的選擇[1-17：.：14字宰***黑*累未睿*****水黑*黑家*****累*用卡累******:*****岸*束*黑家黑*黑家*當(dāng)*宰豐半請(qǐng)輸入你的選擇[1-171:15SDHEBIFCA三種方式（前序、中序、后序）輸出二叉樹(shù)（非遞歸）二叉樹(shù)復(fù)制: 件 1一竝"-，xtd 2訃卑「艾神高度 3一統(tǒng)計(jì)站點(diǎn)數(shù)雖 4-訃鼎豹點(diǎn)的度段葉肖I'i黴吐 氏訃節(jié)站點(diǎn)所任涇披 E劌前納點(diǎn)是仟比-.XW中 7：已找汕點(diǎn)艾第亢 &-孑找拈點(diǎn)黑廣女軸點(diǎn) 16「閲牖f庁坍冊(cè)輸已.砂歸實(shí)現(xiàn) 1];二更刪砂|嚇砸山耶付期口實(shí)m 12;:上樹(shù)的用“述川甬出型叮宦現(xiàn) 母：義樹(shù)的訶用遍揚(yáng)劉I；村副I實(shí)現(xiàn) 14:：貿(mào)制的屮序軸血翻IM砂門(mén)實(shí)現(xiàn) 仍;—戈制的質(zhì)“遍山抽hi■遜口實(shí)現(xiàn) 托劇的如制 1；■:mt* 卡甘*學(xué)卑甘卑黑卑*鼻半曲半工出甘*#卑甘舉學(xué)**鼻舉沖半工卑■車(chē)掃!*也!申學(xué)卑七出注七申甘詩(shī)輸入悔的ifc#[l-17]=16新樹(shù)帝序通歷揃;hABDGEHCFI址制述功.八、實(shí)驗(yàn)分析（1）算法的性能分析二叉樹(shù)涉及主要算法有利用廣義表進(jìn)行二叉樹(shù)的建立、遞歸與非遞歸兩種方式實(shí)現(xiàn)前序、中序、后序的遍歷、二叉樹(shù)性質(zhì)的一些計(jì)算例如樹(shù)的高度，結(jié)點(diǎn)所處層次，結(jié)點(diǎn)的度等。下面對(duì)主要的算法進(jìn)行分析。在二叉樹(shù)的建立米用廣義表進(jìn)行建立。該算法的基本思路是：依次保存廣義表的字符串中輸入字符。若是字母（假設(shè)以字母作為結(jié)點(diǎn)的值），則表示是結(jié)點(diǎn)的值，為它建立一個(gè)新的結(jié)點(diǎn)，并把該結(jié)點(diǎn)作為左子女（當(dāng)k=l）或有子女（k=2）鏈接到其父結(jié)點(diǎn)上。若是左括號(hào)“（”，則表明子表的開(kāi)始，將k置為1；若遇到的是右括號(hào)“）”，則表明子表結(jié)束。若遇到的是逗號(hào)“，”，則表示以左子女為根的子樹(shù)處理完畢，應(yīng)接著處理以右子女為根的子樹(shù)，將k置為2。以此種方式處理每一個(gè)字符，直到讀入結(jié)束符“#”為止。在此算法中使用了一個(gè)棧，在進(jìn)入子表之前將根結(jié)點(diǎn)指針進(jìn)棧，以便括號(hào)內(nèi)的子女鏈接之用。在子表處理結(jié)束時(shí)退棧。下面分析前序、中序、后序遍歷，由于方法大致類(lèi)似，故在此只對(duì)非遞歸實(shí)現(xiàn)中序遍歷進(jìn)行分析。該算法需要使用一個(gè)棧，以記錄遍歷過(guò)程中回退的路徑。在一棵子樹(shù)中首先訪問(wèn)的是中序下的第一個(gè)結(jié)點(diǎn)，它位于從根開(kāi)始沿leftChild鏈走到最左下角的結(jié)點(diǎn)，該結(jié)點(diǎn)的leftChild指針為NULL。訪問(wèn)它的數(shù)據(jù)后，再遍歷該結(jié)點(diǎn)的右子樹(shù)。此右子樹(shù)又是二叉樹(shù)，重復(fù)執(zhí)行上面的過(guò)程，直到該子樹(shù)圖2非遞歸實(shí)現(xiàn)二叉樹(shù)中序遍歷

下面分析二叉樹(shù)中利用性質(zhì)進(jìn)行相關(guān)計(jì)算。在此只對(duì)計(jì)算結(jié)點(diǎn)所在層次算法進(jìn)行詳細(xì)分析，其余計(jì)算與該算法有所類(lèi)似。具體算法是：利用隊(duì)列實(shí)現(xiàn)二叉樹(shù)層次順序訪問(wèn)。在訪問(wèn)