遍歷二叉樹課程設(shè)計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：39 大?。?55.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩38頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)　　課程設(shè)計說明書　　題目: 遍歷二叉樹　　　 　　院系：計算機科學(xué)與工程系 　　2010年6月25日<

2、;p>　　目錄　　一、需求分析2　　1.主功能模塊2　　2.創(chuàng)建樹模塊2　　3.遍歷樹模塊2　　二、概要設(shè)

3、計3　　1.功能設(shè)計3　?。?）創(chuàng)建二叉樹3　?。?）先序遞歸遍歷3　　（3）中序遞歸遍歷3　?。?）后序遞歸遍歷3<p

4、>　?。?）先序非遞歸遍歷3　　（6）中序非遞歸遍歷4　?。?）后序非遞歸遍歷4　　（8）層序非遞歸遍歷4　　2.算法流程圖4　　三、詳細(xì)設(shè)計12　　1.界

5、面設(shè)計12　　2.詳細(xì)代碼分析14　?。?）主模塊14　　（2）創(chuàng)建樹模塊15　?。?）遍歷樹模塊16　　（4）源程序清單16　　3.調(diào)試分析35</p&g

6、t;　　（1）調(diào)試結(jié)果35　?。?）算法分析36　　四、心得體會37　　五、參考文獻(xiàn)38　　需求分析　　在現(xiàn)實世界層次化的數(shù)據(jù)模型中，數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系

7、紛繁復(fù)雜。其中很多關(guān)系無法使用簡單的線性結(jié)構(gòu)表示清楚，比如祖先與后代的關(guān)系、整體與部分的關(guān)系等。于是人們借鑒自然界中樹的形象創(chuàng)造了一種強大的非線性結(jié)構(gòu)——樹。樹形結(jié)構(gòu)的具體形式有很多種，其中最常用的就是二叉樹。而二叉樹的多層次遍歷遍歷則是二叉樹的重要內(nèi)容。　　本程序用Microsoft Visual C++ 6.0編寫，可以實現(xiàn)對二叉樹的多種方式的創(chuàng)建、采用遞歸和非遞歸等兩種方式先序、中序、后序

8、進(jìn)行遍歷。　　主功能模塊　　通過合理的界面設(shè)計，根據(jù)提示信息，使用者可以方便快捷地運行本程序來完成創(chuàng)建、遍歷二叉樹等操作。界面美觀，人性化，程序智能，安全性高。　　創(chuàng)建樹模塊　　當(dāng)進(jìn)入程序運行界面

9、后，根據(jù)提示輸入需要建立的二叉樹，共有三種方法來創(chuàng)建二叉樹,即：1：廣義表構(gòu)造法、2：先序和中序構(gòu)造法、3：中序和后序構(gòu)造法。建立完二叉樹后自動進(jìn)入下一個功能模塊。　　遍歷樹模塊　　實現(xiàn)對該二叉樹的先序遞歸遍歷、先序非遞歸遍歷、中序遞歸遍歷、中序非遞歸遍歷、后序遞歸遍歷、后序非遞歸遍歷、層序非遞歸遍歷等方式的遍歷操作

10、，并輸出各遍歷序列。當(dāng)對該二叉樹進(jìn)行層序非遞歸遍歷時，直接輸出該樹的邏輯結(jié)構(gòu)圖，以便更直觀地顯示其層次關(guān)系。　　概要設(shè)計　　功能設(shè)計　　創(chuàng)建二叉樹　　利用二叉

11、樹模板類，創(chuàng)建二叉樹時產(chǎn)生類模板，調(diào)用類的構(gòu)造函數(shù)來創(chuàng)建，修改二叉樹的結(jié)構(gòu)時，可以調(diào)用賦值語句直接把廣義表轉(zhuǎn)換成二叉樹。相關(guān)類或函數(shù)如下：　　class BinaryTree;　　BinaryTree();　　BinaryTree<T>& operator=(const string&

12、 str);　　先序遞歸遍歷　　若二叉樹為空，則空操作；否則（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。相關(guān)函數(shù)如下：　　void PreOrderTraverse(const BinaryTreeNode<T>* p) const;</p

13、>　　中序遞歸遍歷　　若二叉樹為空，則空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。相關(guān)函數(shù)如下：　　void InOrderTraverse(const BinaryTreeNode<T>* p) const;<p&g

14、t;　　后序遞歸遍歷　　若二叉樹為空，則空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。相關(guān)函數(shù)如下：　　void PostOrderTraverse(const BinaryTreeNode<T>* p) const;

15、　　先序非遞歸遍歷　　若二叉樹為空，則空操作；否則引入棧模擬遞歸工作棧，初始時棧為空。相關(guān)函數(shù)如下：　　void PreOrderTraverse() const;　　中序非遞歸遍歷　　若二叉樹為空，則空操作；否則

16、引入棧模擬遞歸工作棧，初始時棧為空。相關(guān)函數(shù)如下：　　void InOrderTraverse() const;　　后序非遞歸遍歷　　若二叉樹為空，則空操作；否則引入棧和標(biāo)記模擬遞歸工作棧，初始時棧為空。相關(guān)函數(shù)如下：　　void P

17、ostOrderTraverse() const;　　層序非遞歸遍歷　　按照樹的層次從左到右訪問樹的結(jié)點，層序遍歷用于保存結(jié)點的容器是隊列。相關(guān)函數(shù)如下：　　void LevelOrderTraverse() const;<b&

18、gt;　　算法流程圖　　圖2-1 創(chuàng)建而二叉樹　　圖2-2 前序遞歸遍歷　　圖2-3 中序遞歸遍歷　　圖2-4 后序遞歸遍歷　　圖2-5 先序非遞歸遍歷　　圖

19、2-6 中序非遞歸遍歷　　圖2-7 后序非遞歸遍歷　　圖2-8 層序非遞歸遍歷　　詳細(xì)設(shè)計　　界面設(shè)計　　圖3-1 系統(tǒng)運行主界面</p&g

20、t;　　圖3-2 創(chuàng)建二叉樹界面　　圖3-3 某二叉樹層序遍歷界面　　詳細(xì)代碼分析　　主模塊　　本模塊定義了系統(tǒng)運行主界面的相關(guān)內(nèi)容和相關(guān)操作函數(shù)，源代碼如下：</

21、p>　　int main()　　{　　system("color A9"); //設(shè)置屏幕背景和字體顏色　　cout<<endl<<endl<<endl<<endl<

22、;<endl;　　cout<<string(35,'*')<<"遍歷二叉樹"<<string(35,'*')<<endl;　　cout<<string(31,' ')<<"1：創(chuàng)建二叉樹"&

23、lt;<endl;　　cout<<string(31,' ')<<"2：先序遍歷(遞歸)"<<endl;　　cout<<string(31,' ')<<"3：先序遍歷(非遞歸)"<<endl;</p&

24、gt;　　cout<<string(31,' ')<<"4：中序遍歷(遞歸)"<<endl;　　cout<<string(31,' ')<<"5：中序遍歷(非遞歸)"<<endl;　　cou

25、t<<string(31,' ')<<"6：后序遍歷(遞歸)"<<endl;　　cout<<string(31,' ')<<"7：后序遍歷(非遞歸)"<<endl;　　cout<<string(31,

26、' ')<<"8：層序遍歷(非遞歸)"<<endl;　　cout<<string(31,' ')<<"9：重新顯示所有菜單"<<endl;　　cout<<string(31,' ')<<

27、;"0：關(guān)閉窗口";　　if(second>=0)　　{　　cout<<"(剩"<<setw(2)<<second<<"秒)";<p

28、>　　}　　cout<<endl<<endl<<string(80,'*');while(!isdigit(ch)) //合法性判斷　　{　　center("

29、您的輸入有誤，請重新輸入：",0);　　ch=getch();　　cout<<ch<<endl;　　}　　BinaryTree<char> t; //構(gòu)造空二叉樹</p&g

30、t;　　while(1) //菜單操作無限循環(huán)　　{　　bool mark=1; //設(shè)置重新顯示所有菜單時的輸出標(biāo)記　　switch(ch)　　{...}

31、;　　}　　}　　創(chuàng)建樹模塊　　本模塊包括兩個類——二叉樹結(jié)點類、二叉樹類，源代碼如下：　　class Binary

32、TreeNode　　{　　private:　　T data; //存儲該結(jié)點的數(shù)據(jù)　　BinaryTreeNode<T> *parent; //存

33、儲該結(jié)點的父指針　　BinaryTreeNode<T> *left; //存儲該結(jié)點的左孩子指針　　BinaryTreeNode<T> *right; //存儲該結(jié)點的右孩子指針　　public:　　Bi

34、naryTreeNode();　　BinaryTreeNode(const T& t);　　T GetData() const;　　bool IsLeftChild() const;　　bool IsRightChild() const;&

35、lt;p>　　BinaryTreeNode<T>* GetParent() const;　　BinaryTreeNode<T>* GetLeftChild() const;　　BinaryTreeNode<T>* GetRightChild() const;　　Binar

36、yTreeNode<T>* GetLeftBrother() const;　　BinaryTreeNode<T>* GetRightBrother() const;　　void Assign(const T& t);　　void SetParent(BinaryTreeNode&l

37、t;T>* q);　　void SetLeftChild(BinaryTreeNode<T>* q);　　void SetRightChild(BinaryTreeNode<T>* q);　　~BinaryTreeNode();<b&g

38、t;　　};　　class BinaryTree　　{　　private:　　BinaryTreeNode<T>* root; //二叉樹根節(jié)點

39、;　　public:　　BinaryTree(); //二叉樹構(gòu)造函數(shù)聲明　　bool IsEmpty() const; //二叉樹判空函數(shù)聲明　　BinaryTreeNode<T>* GetRoot() const;

40、 //取得根節(jié)點函數(shù)聲明　　BinaryTree<T>& operator=(const string& str); //二叉樹賦值函數(shù)聲明　　~BinaryTree(); //二叉樹析構(gòu)函數(shù)聲明　　private:&

41、lt;p>　　void NodeCounter(const BinaryTreeNode<T>* p,int& sum) const; //統(tǒng)計二叉樹結(jié)點個數(shù)函數(shù)聲明　　void Destroy(BinaryTreeNode<T>* p); //二叉樹級聯(lián)釋放結(jié)點內(nèi)存函數(shù)聲明　　int Depth(const B

42、inaryTreeNode<T>* p) const; //計算二叉樹深度函數(shù)聲明　　};　　遍歷樹模塊　　本模塊包括了各種遍歷二叉樹的函數(shù)，源代碼如下：　　void LevelOr

43、derTraverse() const; //二叉樹的層序遍歷(非遞歸)成員函數(shù)聲明　　void PreOrderTraverse() const; //二叉樹的先序遍歷(非遞歸)成員函數(shù)聲明　　void PreOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉樹的先序遍歷(遞歸)

44、成員函數(shù)聲明　　void InOrderTraverse() const; //二叉樹的中序遍歷(非遞歸)成員函數(shù)聲明　　void InOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉樹的中序遍歷(遞歸)成員函數(shù)聲明　　void PostO

45、rderTraverse() const; //二叉樹的后序遍歷(非遞歸)成員函數(shù)聲明　　void PostOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉樹的后序遍歷(非遞歸)成員函數(shù)聲明　　源程序清單

46、　　BinaryTreeNode.h　　#include<cassert>　　#include<string>　　#include<stack>　　template<class T>

47、　　class BinaryTreeNode　　{　　private:　　T data; //存儲該結(jié)點的數(shù)據(jù)　　BinaryTreeNode<T>

48、; *parent; //存儲該結(jié)點的父指針　　BinaryTreeNode<T> *left; //存儲該結(jié)點的左孩子指針　　BinaryTreeNode<T> *right; //存儲該結(jié)點的右孩子指針　　public:

49、　　BinaryTreeNode();　　BinaryTreeNode(const T& t);　　T GetData() const;　　bool IsLeftChild() const;　　bool IsRightChild() const

50、;　　BinaryTreeNode<T>* GetParent() const;　　BinaryTreeNode<T>* GetLeftChild() const;　　BinaryTreeNode<T>* GetRightChild() const;&l

51、t;p>　　BinaryTreeNode<T>* GetLeftBrother() const;　　BinaryTreeNode<T>* GetRightBrother() const;　　void Assign(const T& t);　　void SetParent(Bi

52、naryTreeNode<T>* q);　　void SetLeftChild(BinaryTreeNode<T>* q);　　void SetRightChild(BinaryTreeNode<T>* q);　　~BinaryTreeNode();&l

53、t;p>　　};　　template<class T>　　BinaryTreeNode<T>::BinaryTreeNode():data(0),parent(NULL),left(NULL),right(NULL){}　　template<

54、;class T>　　BinaryTreeNode<T>::BinaryTreeNode(const T&t):data(t),parent(NULL),left(NULL),right(NULL){}　　template<class T>　　bool BinaryTreeN

55、ode<T>::IsLeftChild() const　　{　　return (this==this->parent->GetLeftChild());　　}　　templ

56、ate<class T>　　bool BinaryTreeNode<T>::IsRightChild() const　　{　　return (this==this->parent->GetRightChild());

57、　　}　　template<class T>　　T BinaryTreeNode<T>::GetData() const　　{　　return data;

58、　　}　　template<class T>　　BinaryTreeNode<T>* BinaryTreeNode<T>::GetParent() const　　{</b&g

59、t;　　return parent;　　}　　template<class T>　　BinaryTreeNode<T>* BinaryTreeNode<T>::GetLeftChild() cons

60、t　　{　　return left;　　}　　template<class T>　　BinaryTreeNode<T>* Bina

61、ryTreeNode<T>::GetRightChild() const　　{　　return right;　　}　　template<class T>

62、　　BinaryTreeNode<T>* BinaryTreeNode<T>::GetLeftBrother() const　　{　　assert(IsRightChild());　　return this->parent-

63、>GetLeftChild();　　}　　template<class T>　　BinaryTreeNode<T>* BinaryTreeNode<T>::GetRightBrother() const<

64、p>　　{　　assert(IsLeftChild());　　return this->parent->GetRightChild();　　}　　template<clas

65、s T>　　void BinaryTreeNode<T>::Assign(const T& t)　　{　　data=t;　　}<

66、;/p>　　template<class T>　　void BinaryTreeNode<T>::SetParent(BinaryTreeNode<T>* q)　　{　　parent=q;<

67、;/b>　　}　　template<class T>　　void BinaryTreeNode<T>::SetLeftChild(BinaryTreeNode<T>* q)

68、　{　　left=q;　　}　　template<class T>　　void BinaryTreeNode<T>::SetRightChild(Bin

69、aryTreeNode<T>* q)　　{　　right=q;　　}　　template<class T>&l

70、t;p>　　BinaryTreeNode<T>::~BinaryTreeNode(){}　　BinaryTree.h　　#include<iostream>　　#include<cmath>　　#include<vector

71、>　　#include<stack>　　#include<queue>　　#include"BinaryTreeNode.h" //二叉樹結(jié)點模板類頭文件　　using namespace std;

72、　　const int MAX=1024;　　template<class T>　　class BinaryTree　　{　　private:

73、　　BinaryTreeNode<T>* root; //二叉樹根節(jié)點　　public:　　BinaryTree(); //二叉樹構(gòu)造函數(shù)聲明　　bool IsEmpty() const; //二叉樹判空函數(shù)聲明<

74、/p>　　BinaryTreeNode<T>* GetRoot() const; //取得根節(jié)點函數(shù)聲明　　BinaryTree<T>& operator=(const string& str); //二叉樹賦值函數(shù)聲明　　void LevelOrderTraverse() cons

75、t; //二叉樹的層序遍歷(非遞歸)成員函數(shù)聲明　　void PreOrderTraverse() const; //二叉樹的先序遍歷(非遞歸)成員函數(shù)聲明　　void PreOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉樹的先序遍歷(遞歸)成員函數(shù)聲明

76、　　void InOrderTraverse() const; //二叉樹的中序遍歷(非遞歸)成員函數(shù)聲明　　void InOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉樹的中序遍歷(遞歸)成員函數(shù)聲明　　void PostOrderTraverse() con

77、st; //二叉樹的后序遍歷(非遞歸)成員函數(shù)聲明　　void PostOrderTraverse(const BinaryTreeNode<T>* p) const; //二叉樹的后序遍歷(非遞歸)成員函數(shù)聲明　　~BinaryTree(); //二叉樹析構(gòu)函數(shù)聲明　　pri

78、vate:　　void NodeCounter(const BinaryTreeNode<T>* p,int& sum) const; //統(tǒng)計二叉樹結(jié)點個數(shù)函數(shù)聲明　　void Destroy(BinaryTreeNode<T>* p); //二叉樹級聯(lián)釋放結(jié)點內(nèi)存函數(shù)聲明

79、　　int Depth(const BinaryTreeNode<T>* p) const; //計算二叉樹深度函數(shù)聲明　　};　　template<class T>　　BinaryTree<T>::BinaryTree

80、():root(NULL){} //二叉樹構(gòu)造函數(shù)定義　　template<class T>　　BinaryTree<T>& BinaryTree<T>::operator=(const string& str) //二叉樹賦值函數(shù)定義　　{

81、　　Destroy(root);　　root=NULL;　　BinaryTreeNode<T> *index[MAX];　　BinaryTreeNode<T> *p=NULL;　　int

82、 top=-1,sum=0,number=0;　　int mark=1;　　for(int i=0;i<str.size();i++)　　{　　char ch=str[i];　　swit

83、ch(ch)　　{　　case '(':　　{　　index[++top]=p;

84、　mark=1;　　break;　　}　　case ')':　　{

85、;　　mark=1;　　top--;　　break;　　}　　case '

86、;,':　　{　　mark++;　　break;　　}<p&g

87、t;　　default:　　{　　p=new BinaryTreeNode<T>(ch);　　sum++;　　if(root==NULL)<

88、/p>　　{　　root=p;　　}　　else　　{

89、　　if(mark==1)　　{　　index[top]->SetLeftChild(p);　　}　　else if(mark==2)</p&

90、gt;　　{　　index[top]->SetRightChild(p);　　}　　}　　}

91、　　}　　}　　NodeCounter(root,number);　　if(sum>number)　　{<

92、;/p>　　Destroy(root);　　root=NULL;　　}　　return *this;　　}　　template

93、<class T>　　bool BinaryTree<T>::IsEmpty() const //二叉樹判空函數(shù)定義　　{　　return (root==NULL);　　}

94、;　　template<class T>　　BinaryTreeNode<T>* BinaryTree<T>::GetRoot() const //取得根節(jié)點函數(shù)定義　　{　　return root

95、;　　}　　template<class T>　　void BinaryTree<T>::LevelOrderTraverse() const //二叉樹的層序遍歷(非遞歸)成員函數(shù)定義

96、{　　if(root==NULL)　　{　　cout<<string(15,' ')<<"二叉樹為空，請先創(chuàng)建二叉樹！ "<<endl;<

97、;b>　　return;　　}　　int sum=Depth(root);　　queue<BinaryTreeNode<T> *> list;　　list.push(root);<

98、;/p>　　BinaryTreeNode<T> *p=new BinaryTreeNode<T>(' ');　　int number=1;　　while(number<=pow(2,sum)-1)　　{

99、　　BinaryTreeNode<T>* temp=list.front();　　list.pop();　　int i=floor(log10(number)/log10(2))+1;　　int j=number+1-pow(2,i-1);

100、　　if(number==pow(2,i-1))　　{　　cout<<string((81-pow(2,sum))/2+pow(2,sum-i)-1,' ');　　}

101、　　else　　{　　cout<<string(pow(2,sum-i+1)-1,' ');　　}　　cout

102、<<temp->GetData();　　if(floor(log10(number+1)/log10(2))==log10(number+1)/log10(2))　　{　　cout<<endl;<b

103、>　　}　　number++;　　if(temp->GetLeftChild()!=NULL)　　{　　list.push(temp->GetLeftChil

104、d());　　}　　else　　{　　list.push(p);　　}<

105、/p>　　if(temp->GetRightChild()!=NULL)　　{　　list.push(temp->GetRightChild());　　}&

106、lt;b>　　else　　{　　list.push(p);　　}　　}

107、　delete p;　　}　　template<class T>　　void BinaryTree<T>::PreOrderTraverse(const BinaryTreeNode<T>* p) const //二叉

108、樹的先序遍歷(遞歸)成員函數(shù)定義　　{　　if(root==NULL)　　{　　cout<<"二叉樹為空，請先創(chuàng)建二叉樹！";<p&g

109、t;　　return;　　}　　if(p==NULL)　　{　　return;

110、　　}　　cout<<p->GetData();　　PreOrderTraverse(p->GetLeftChild());　　PreOrderTraverse(p->GetRightChild());&

111、lt;b>　　}　　template<class T>　　void BinaryTree<T>::PreOrderTraverse() const //二叉樹的先序遍歷(非遞歸)成員函數(shù)定義　　{&l

112、t;p>　　if(root==NULL)　　{　　cout<<"二叉樹為空，請先創(chuàng)建二叉樹！";　　return;　　}

113、　　stack<BinaryTreeNode<T> *> list;　　BinaryTreeNode<T> *p=root;　　while(!list.empty() || p!=NULL)　　{&

114、lt;/p>　　while(p!=NULL)　　{　　list.push(p);　　cout<<p->GetData();　　p=p->GetLeftChild();</p&g

115、t;　　}　　p=list.top();　　list.pop();　　p=p->GetRightChild();　　}<

116、b>　　}　　template<class T>　　void BinaryTree<T>::InOrderTraverse(const BinaryTreeNode<T>* p) const //二叉樹的中序遍歷(遞歸)成員函數(shù)定義

117、　{　　if(root==NULL)　　{　　cout<<"二叉樹為空，請先創(chuàng)建二叉樹！";　　return;<p

118、>　　}　　if(p==NULL)　　{　　return;　　}　　In

119、OrderTraverse(p->GetLeftChild());　　cout<<p->GetData();　　InOrderTraverse(p->GetRightChild());　　}　　templ

120、ate<class T>　　void BinaryTree<T>::InOrderTraverse() const //二叉樹的中序遍歷(非遞歸)成員函數(shù)定義　　{　　if(root==NULL)<b&

121、gt;　　{　　cout<<"二叉樹為空，請先創(chuàng)建二叉樹！";　　return;　　}　　stack<BinaryTreeNode<

122、T> *> list;　　BinaryTreeNode<T> *p=root;　　while(!list.empty() || p!=NULL)　　{　　while(p!=NULL)&l

123、t;p>　　{　　list.push(p);　　p=p->GetLeftChild();　　}　　p=list.top();　　list.po

124、p();　　cout<<p->GetData();　　p=p->GetRightChild();　　}　　}　　template&

125、lt;class T>　　void BinaryTree<T>::PostOrderTraverse(const BinaryTreeNode<T>* p) const //二叉樹的后序遍歷(遞歸)成員函數(shù)定義　　{　　if(root==NUL

126、L)　　{　　cout<<"二叉樹為空，請先創(chuàng)建二叉樹！";　　return;　　}

127、　　if(p==NULL)　　{　　return;　　}　　PostOrderTraverse(p->GetLeftChild());

128、;　　PostOrderTraverse(p->GetRightChild());　　cout<<p->GetData();　　}　　template<class T>　　vo

129、id BinaryTree<T>::PostOrderTraverse() const //二叉樹的后序遍歷(非遞歸)成員函數(shù)定義　　{　　if(root==NULL)　　{　　co

130、ut<<"二叉樹為空，請先創(chuàng)建二叉樹！";　　return;　　}　　stack<BinaryTreeNode<T> *> list;　　B

131、inaryTreeNode<T> *p=root;　　BinaryTreeNode<T> *q;　　bool flag;　　while(!list.empty() || p!=NULL)　　{

132、;　　while(p!=NULL)　　{　　list.push(p);　　p=p->GetLeftChild();　　}<

133、;b>　　q=NULL;　　flag=1;　　while(flag && !list.empty())　　{　　p=list.top();</p&g

134、t;　　if(p->GetRightChild()==q)　　{　　cout<<p->GetData();　　list.pop();　　q=p;<

135、;/p>　　if(list.empty())　　{　　p=NULL;　　}　　}</p

136、>　　else　　{　　p=p->GetRightChild();　　flag=0;　　}</b&g

137、t;　　}　　}　　}　　template<class T>　　BinaryTree<T>:

138、:~BinaryTree() //二叉樹析構(gòu)函數(shù)定義　　{　　Destroy(root);　　}　　template<class T>

139、void BinaryTree<T>::Destroy(BinaryTreeNode<T>* p) //二叉樹級聯(lián)釋放結(jié)點內(nèi)存函數(shù)定義　　{　　if(p!=NULL)　　{<p&g

140、t;　　Destroy(p->GetLeftChild());　　Destroy(p->GetRightChild());　　delete p;　　p=NULL;

141、}　　}　　template<class T>　　void BinaryTree<T>::NodeCounter(const BinaryTreeNode<T>* p,int& sum) const //統(tǒng)計二叉

142、樹結(jié)點個數(shù)函數(shù)定義　　{　　if(p==NULL)　　{　　return;　　}

143、;　　sum++;　　NodeCounter(p->GetLeftChild(),sum);　　NodeCounter(p->GetRightChild(),sum);　　}</

144、p>　　template<class T>　　int BinaryTree<T>::Depth(const BinaryTreeNode<T>* p) const //計算二叉樹深度函數(shù)聲明　　{　　if(p=

145、=NULL)　　{　　return 0;　　}　　int h1=Depth(p->GetLeftChild());<p&g

146、t;　　int h2=Depth(p->GetRightChild());　　return h1>h2 ? h1+1 : h2+1;　　}　　遍歷二叉樹.cpp　　#include&l

147、t;iostream>　　#include<iomanip>　　#include<string>　　#include<ctime>　　#include<conio.h>　　#i

148、nclude"BinaryTree.h" //二叉樹模板類頭文件　　using namespace std;　　char limittime(int i); //限時輸入函數(shù)聲明　　void menu(int second=30); //菜單輸出函數(shù)聲明&l

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

遍歷二叉樹課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

遍歷二叉樹課程設(shè)計

文檔簡介

溫馨提示

最新文檔

評論

免費下載