數(shù)據(jù)結構課程設計實驗報告-二叉樹的實現(xiàn)

1、數(shù)據(jù)結構實驗報告題目：二義樹的實現(xiàn)學號:姓名：東南大學成賢學院計算機系實驗題目1.實驗目的1. 掌握二叉樹的基本操作，理解遞歸算法。2. 實驗內(nèi)容1.將下圖所示二叉樹采用二叉鏈表進行存儲，然后進行各種操作測試。2. 實驗步驟1. 啟動 vc6.0：開始菜單一程序一microsoft visual studio 6.0 microsoft visual c+ 6.02. 建立工程：文件(file)新建(new)在彈出的對話框屮選擇工程標簽(project ) -* 選中選項：win32 console application (不能選別的)輸入工程名(project name )選 擇工程的存放

2、位置(location) -*單擊"確定按鈕(0k)-在彈出的対話框中選中選項： an empty project ->單擊"完成按鈕(finish)在彈出的對話框中單擊“確定"按鈕(0k )。3. 創(chuàng)建頭文件：文件(file)-新建(new)-在彈出的對話框屮選擇文件標簽(files)- 選中選項：c/c+ header file -*輸入頭文件名(此處定義為"bin_tree_node.h n) f單擊"確 定按鈕(ok)obin_tree_node.h 內(nèi)容如下：二叉樹結點類模板template ele mtype>stru

3、ct bintree node數(shù)據(jù)成員：elemtyp e data;/ 數(shù)據(jù)域bint reenode<ei emtype> *leftchild; / 左孩子bint reenode<ei emtype> *rightchild ;/ 右孩子； 4 .創(chuàng)建頭文件：文件(file)新建(new )在彈出的對話框屮選擇文件標簽(files ) f選中選項:c/c+ he ader file-*輸入頭文件名(此處定義為u binary_tree.h ”)單擊"確 定按鈕(0k )。binary_tree.h定義了鏈隊的類模板，代碼如下：#ifndef_binna

4、ry_t ree_h_#de fine _bin nary_tree_h_/二叉樹類模板template el emtype>cla ssbinaryt reeprivat e:/二叉樹的數(shù)據(jù)成員：bintr eenode<ele mtype> *ro ot;/二叉樹的私有函數(shù)：void preorderh elp(bintre enode<elem type> *r);/ 先序遍歷voi dlnorderh elp(bintre enode<elem type> *r);/ 中序遍歷voi dpostorde rhelp(bint reenode&l

5、t;ei emtype> *r);/ 后序遍歷v oid creat(bintreenod e<elemtype > *r, intflag,elemtypee mptelem type end);遞歸創(chuàng)建子樹bi ntreenode elemtype>*getroot(); 返回根指針bintreeno de e> * locate (bintreeno de e> *r, ele mtype e); 査找元素值為 e 的結 點，返回指針.b intreenode *leftchil d(elemtype e);定位指定元素的左孩子，返回其指針。bintr

6、e enode type>*par ent(bintre enode type>*r, e lemtype e); /定位指定元素的 父結點bintre enode type>*lef tsibling(e lemtypee);定位指定元素的左兄弟intsi ze(bintree node ype> *r);intdepth (bintreeno de e> *r);i nt leaf(bi ntreenode elemtype>*r); /統(tǒng)計并返回葉子結點個數(shù)vo id clear(b intreenode *r);v oid displa ytreee

7、help (bintreeno de<elemtyp e> *r, int level);按樹狀形式顯示以r為根的二叉樹，level為層次數(shù)，可設根結點的層次數(shù)為1 pu blic:/二叉樹公共方法聲明：b inarytree( );/無參數(shù)的構造函數(shù)模板void createbit ree();/ 構造二叉樹bintre enode<elem type> *get root();返回二叉樹的根voi dlnorder();/二叉樹的中序遍歷void pr eorder();/二叉樹的先序遍歷void posto rder();/二叉樹的后序遍歷vo idlevelor

8、 der();/按層遍歷int locate(ele mtype e);查找元素值為e的結點。int ge tleft(elem type e, el emtype ;讀取指定元素的左孩子int ge tparent(ei emtypee,elemtype f);讀取指定元素的父元素int getleftsib ling(elemt ype e, ele ;讀取指定元素的左兄弟int ins ertchild(e lemtype e,elemtype x ,elemtype y);為指定元素e插入左、右孩子int setele m(elemtype e, elemt ype x);更新指定元素

9、int size();intdep th();in t leaf(); 統(tǒng)計并返回葉子結點個數(shù)virtua i "binaryt ree();/ 銷毀二叉樹void d isplaytree ();；函數(shù)實現(xiàn)由學生自己完成#end if5.創(chuàng)建源程序文件main.cpp :文件(file)新建(new)在彈出的對話框中選擇文件標 簽(files)選中選項：c+ source file 輸入源程序文件名(main) -*單擊"確定"按鈕(0k)omain.cpp文件內(nèi)容如下：#incl ude "binar y_tree.h"/ 二叉樹類int

10、main (void)利用swtich構造菜單，對二叉樹操作進行測試。(初始化，構造二叉樹，圖形顯示， 前序，中序，后序遍歷結果，求結點個數(shù)，二叉樹深度，葉子結點樹，查找結點，找指定 結點的左孩子，雙親，左兄弟，插入新的左、右孩子。注意：1 在編程過程中注意及時保存編寫內(nèi)容。3.實驗結果1. binary_tree.h 的代碼2. mai n.cpp 的代碼3. 運行結果截圖(可以有多張)1、binary_tree.h#pragma once ftincludc ” stdafx.h"using namespace std;/二叉樹類模板template <class elcm

11、typc>class binarytrecprivate:/二叉樹的數(shù)據(jù)成員：bi ntrccnodc<blcmtype>*root;/二叉樹的私有函數(shù)：void preorderllelp(bintreexodeelemtype>*r) ;/ 先序遍歷void inorderhelp(bintreexodeelemtype>*r) ;/ 中序遍歷vo i d postorderhelp (bi ntreenode<elemtype> *r);/ 后序遍歷void creat(bintrccnode<hiemtypc> *r,int fla

12、g, elcmtypc empty, elcmtypc end);/遞歸創(chuàng)建子樹bintreenode<elemtype> *getroot () ;/返回根指針bintreenode<elemtype> *locate(bintreenode<elemtype> *r, elemtype e) ;/查找元素值為e 的結點，返回指針.bintrccnoclcelcmtype>*lcftchi.ld (elcmtypcc);定位指定元素的左孩子，返回其指針。bintreenode<elemtype>* parent (bintreexode&

13、lt;elemtype>*r, elemtype e);/定位指定元索的 父結點bi ntrccnode<e1emtype>* leftsib1ing(eiemtypc e):定位指定元素的左兄弟intsize(ihntreexode<elemtype> *r);intdepth(bintreenode<elemtype> *r);intleaf (bintreexode<elemtype> *r) ; /統(tǒng)計并返冋葉了結點個數(shù)voidclear(bintrccnodc<hlemtype> *r);void displaytrc

14、cehclp(bintrcexodc<l'lcmtypc> *r, int love.);/按樹狀形式顯示以r為根的二叉樹，level為層次數(shù)，可設根結點的層次數(shù)為1int size;public:/二叉樹公共方法聲明：binarytreeo ;/無參數(shù)的構造函數(shù)模板void createbitreeo ;/ 構造二叉樹/bintreenode<elen)type> *getroot ();/ 返回二叉樹的根void tnorder() ;/二叉樹的中序遍歷void preorder() ; /二-義樹的先斥遍歷void postordcro ; /二叉樹的后序

15、遍歷void levelorder () ;/按層遍歷intlocate(：:leintype e);查找元素值為e的結點。int getleft (:- 1 emtypc e, elcmtypc &c):讀取指定元素的左孩子int getparent(elemtype e, elemtype &f);/讀取指定元索的父元索int getleftsibling(elemtype e, elemtype &s);讀取指定元素的左兄弟int inscrtchiid(elemtype c, elemtype x, elemtype y); /為指定元素e插入左、右孩子int

16、setelem(elenitypee, elemtype x);/更新指定元素intsize();intdcptho ;int leaf (); 統(tǒng)計并返回葉子結點個數(shù) virtuapbinarytree();/ 銷毀一叉樹 void displaytree();；template <class elemtypevoid binarytree<elemtype>:preorderllelp(bintreenodeelemtype>*1)/privateif (r != null)coutr->data，z "/ 訪問根結點preorderhelp (r-

17、>leftch訂d);/ 遍歷左子樹 preorderhelp(i>rightchiid) ;/ 遍歷右了樹templateclass elemtype>void binarytree<elemtype>:preorder()/public(preorderl le 1 p (root);template <class elemtype>void binarytree<elemtype>:inorderhelp(bintreenode<elemtype> *r)/ privateif (r!=null)(inorderhelp(

18、r->leftchild);/ 遍歷左子樹 cout « r* ”;/訪問根結點inorderhelp(r->rightchild);/ 遍歷右子樹template <class elemtype>void binarytree<k1cmtypc>:inordcr()/ publicinorderhelp(root);template <class elemtype>void binarytree<k 1 cmtypc>:postorderllelp(bintrecnodcelcmtypc>*r)/ private(i

19、f (r != null)postorderhelp(r->leftchiid);/ 遍歷左子樹postordcrhelp (r->rightchi id);/ 遍丿力右子樹cout « r->da/，"/ 訪問根結點teniplateclass elemtype>void binarytrcc<elcnitrpc>:postordcr 0/ public(postorderhelp (root);teniplateclass elemtype> voidbinarrtrcc<elcmtypc>: level order

20、 0linkqueue<bintreexode<elemtypt > *>q;bintreeode<elemtype> *t 二 root:if (t !=nill) q. inqueue(t); / 如果根非空，則入隊 whilcdq. empty 0)q. outqueue(t);cout" ”；/if (t->leftchild!=nlll)/左孩子非空q. inqueue(t->leftchild);/ 左孩子入隊if (t->rightch訂dunull)/右孩子非空q. inqueue(t->rightchild

21、);/ 右孩子入隊teniplateclass elcmtype>binarytree<elemtype>:binarytree()root = null;template <classelcmtypc>void binarytree<elemtype>:createbitree()bintrccnode<elcmtype>* r;elcmtypccnd, empty, x;cout « 按先序序列的順序輸入-棵二叉樹"« endl;cout "輸入的結束標志是："；cin>>e

22、nd;cout 輸入的空結點標志是：；cin>> empty;cout << "請開始輸入："« endl;cin»x;r = newb i nt reeode<elemtype>r>data= x;r->leftchild= r->rightchild = null;root = r;creat (r, 0, empty, end);創(chuàng)建根結點的左子樹creat (r, 1, empty, end) ;/創(chuàng)建根結點的右子樹template <class elcmtypc>void bin

23、arytree<elemtype>:creat(bintreexode<elemtype> *r, int flag, elemtype empty,elemtype end)bintrccnodc<elemtype>*p;e1emtype x;cin >> x;if(x !=endx !=empty)p 二 newbiritreeode<elemtype> p->data= x; p->leftchild=p->rightchiid = null;if (flag= 0) r->lcftchild=p;/p為

24、左子樹 else r->rightchild= p;/p為右子樹size+;creat (p, 0, empty, end);遞歸創(chuàng)建左子樹creat (p, 1, empty, end) ;/遞歸創(chuàng)建右子樹template <class elemtype>bintreenode<elemtype>*binary ii .e<eiemtype>:getroot()return root;template <class elemtype>b i nt reenode<elemtype>*b i na iree<eiemtyp

25、e>:locate(bintreeodc<h1cmtypc> *r,elemtype e) /privateif (r=null)return null:if (廠一data 二二e)return r;bintrccnode<eiemtype> *p= locate(r->1eftchi1d, e);if(p =null)p = locate(r->rightchiid,c);returnp;template <class elemtype>int binarytrce<eicmtypc>:locate(eicmtypee) /

26、publicif(locate(root, e) = null)return false;el sereturn true;templateclass elemtype>bintreenode<elemtype>*binarytree<elemtype>:leftchi 1 d(eleintype e) /privatebintrccnoclc<elcmtypc>* cp= locate (root, c);if (ep = null) return null; 找不到結點eif (ep->leftch訂d二二null) /e無左孩子return

27、 null;return cp->leftchiid;/返ale左孩了的指針template <class elemtype>int binarytree<elemtype>:getleft(elemtype e, elemtype &c)/public bintrccnode<eiemtype>* p=leftchi1d(e);if(p=null)return false; /c無左孩子c= p->data;return true;template <class elcmtype>elemtype c)bintrccnode

28、<elcmtypc>* binarytrce<elcmtype>:parent(bintrccnoclc<elcmtypc>*r, /privatebintreeode<eleintype>* p;if (r=null)return null;if (r->lcftch訂d!=null&&i>lcftch訂d->data =c) | (r->rightchild!=xlll&&r->rightchild->data =e) return r;/r是e的父結點，返回結點r的指針p

29、parent (r->leftchi id, e) ;/遞歸調(diào)用r的左 了樹if (p = null) p =parent(r->rightchiid, c);return p;template <class elemtype>int binarytree<blemtypo>: :getparent(lilemtype e, elemtypc &f) /public if(root=null|root->data =e)return false;bintreenode<elemtype> *p = parent(root, e);i

30、f (p =null) return false; 樹中無元素ef= p->data;return true;template <class elemtype>bintrcc.odc<eleintype>* binarytreo<eleintype>:leftsibling(:jcmtypc c)/private(if (root->data=e) return null;bi ntreenodee 1 enitype>*p 二 parent (root, e);if(p =null)return null;/無e結點if (p->l

31、cftchild->clata =c)/c 是其父親的左孩子return null;returnp->leftchild; /返回e的左兄弟指針template <classklemtypc>int binarytrcc<elemtype>:getleftsibling(elenitype e, elemtype &s)if(root->data=e)return false; /根結點無兄弟bintrecnode<elemtype> *p =leftsibling(c);if (p = null) rcturnfalsc; /e無

32、左兄弟s= p->data;return true;template <class elemtype>int binarytrcc<elcmtype>:insertchild(elemtype e, elemtype x, elemtype y)b i ntreenodee 1 enitype>*ep, *xp, *yp;ep = locate (root, e) ;/定位元素cif(cp=null)return false; /找不到元素cxp = new bintreexode<elemtype>:xp->data 二x;xp->

33、rightchiid = null;yp = now bintrccode<e1emtypc>:yp->data =y;yp->leftchild = null;xp->leftch訂d = ep->leftchild;ep->leftchild = xp; /結點x置為結點e的左孩子 yp->rightchilcl = cp->rightchild;ep->rightchild = yp;/結點y置為結點e的右孩子size 二size + 2;return true;template <class elcmtype>in

34、t binarytree<elemtype>:sete1em(elemtype e, elemtype x)bi ntrccnodceicmtypc>*p = locate(root,e);if(p =null)return false;p->data =x;returntrue;template <class elcmtype>int binarrtrcc<elcmtypc>:size()/public(returnsize(root);template <class elcmtype>int binarrtrcc<elcmt

35、ypc>:size(bi nt reenode<e1emtype>*r) /privateif (r = null)returno;else+ 1；/privatereturn size(r->lcftchild) + size(r->rightchild)二叉樹的結點總數(shù)為左右子樹的結點數(shù)之和加1template <class elemtype>int binarylree<e1emtypc>:depth()/pub1icreturndeplh(tool);templateclass elemtype>i ntbi narytree

36、celcmtypc>:depth(bi ntreexodeelemtype>*r) if (r = null)returno;elseintleftl), rightl);lcftd= depth (r->lcftchild);rightd=depth(r->rightchiid);returnl+ (leftd>rightd?leftd : rightd); /二叉樹的深度為左右子樹的深度的最大值template <class elemtype>int binarytree<elemtype>:leaf()/publicrcturnlca

37、f(root);template <class elemtype>int binarytree<elemtype>:leaf(bintreexode<elemtype> *r)/private if (r=null)return 0：if (r->leftchild = nullr->rightchild = null)return1;returnleaf(r->leftchiid) + leaf(r>rightchiid);遞歸遍歷左子樹和右子樹template <class elemtype>void binarytr

38、ee<elemtype>:clear(bintreexode<elemtype> *r)/private(if (r != null)clear(r->leftchild); 后序遞歸clear(r->rightchiid);deleter;size;templateclass elen)type>bin a r y t ree<l: 1 en)t y pe>: : “bin arytree ()clear(root);root=xull;template <class elemtype>void binarytrce<h

39、lemtypp>: :displa3rtreeelielp(bintreeode<h 1 cmtypp> *r, int if (r!=null)di splaytreeehelp(r->r i ghtch ild, 1 eve1+ 1);顯示右子樹cout << cndl;/顯示新行for (int i= 0;i < level- 1;i+)cout « “；/確保在笫level列顯示結點coutr->data;/ 顯示結點displaytreeehelp(r->leftchild, level-*- 1);template &

40、lt;class elemtype>void binarytrec<elcmtype>:displaytree()displaytreeehelp (root,1);cout endl;#e nd if2、st da fx h#pragma once #includc z，targetvcr h"nclude bin_tree_node.h #include 1k_queue h #includc <iostream> ftincludc <cstdlib>3 main.cppinclude "stdafx. h"usin

41、g namespacestd;intmain() binarytree<int> bl;intc =0;inttmpl, tinp2, tmp3;while(c!= 15) cout « cndl «創(chuàng)建二叉樹"cout<< endl "2.中序遍歷"；cout « endl « "3.先序遍歷"cout « endl<< "4.后序遍歷"； cout endl << "5.按層遍歷"cout <<

42、; cndl << "6.查找節(jié)點"； cout« endl "7.讀取左孩子"； cout «endl < "8.讀取父元素" cout << endl << "9.讀取左兄弟"； cout << endl "10.插入左右孩子"； cout<< endl "11.更新元素"；cout «endl « "12.葉子結點個數(shù)"； cout « endl « "13.圖形顯示"； cout << endl << "14.銷毀二叉樹"； cout <