




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、淮陰工學院實踐報告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目:二叉樹遍歷系 別: 計算機工程學院 專 業(yè): 軟件工程 班 級: 軟件1111 學生姓名: 周淼 學 號: 1111315217 起止日期: 2012年12月24日2012年12月30日指導(dǎo)教師: 寇海洲 摘要:現(xiàn)代社會生活中,計算機扮演著重要角色,而隨著計算機運行速度的不斷加快,對數(shù)據(jù)的處理能力也日益增強,因此,程序所涉及的數(shù)據(jù)成爆發(fā)式增長。隨之而來的問題就是如何科學有效的對數(shù)據(jù)進行操作,使得計算機的時間和空間利用率最高。針對這樣的問題,我選擇了二叉樹對數(shù)據(jù)的各種操作作為我的課程設(shè)計主題,希望通過課程設(shè)計來提高對數(shù)據(jù)的處理能力,促進對數(shù)據(jù)結(jié)構(gòu)課程的
2、理解,在日后面向?qū)ο蟮某绦蛟O(shè)計中科學的規(guī)劃數(shù)據(jù)結(jié)構(gòu)。在本次課程設(shè)計中,二叉樹的建立使用了遞歸算法,遍歷則同時使用了遞歸與非遞歸的算法,同時,在遍歷算法的實現(xiàn)中使用了棧結(jié)構(gòu)與隊列結(jié)構(gòu),這大大方便了二叉樹的遍歷。在前序、中序、后續(xù)遍歷算法中,分別實現(xiàn)了遞歸與非遞歸算法,從實際應(yīng)用中體驗了遞歸這一算法的優(yōu)越性。關(guān)鍵詞:二叉樹建立,遞歸與非遞歸,遍歷,棧,隊列編號: 47 淮陰工學院 軟件工程 專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計答辯記錄課題名稱: 二叉樹的算法 班 級 軟件1111 學 號 1111315217 姓 名 周淼 答 辯 記 錄問題1:課題中涉及到哪些數(shù)據(jù)結(jié)構(gòu)和算法?答: 1)數(shù)組,二叉樹,棧,隊列,線
3、性表2)二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法,層次序遍歷非遞歸算法,棧、隊列的實現(xiàn)算法問題2:課題研究和設(shè)計中的關(guān)鍵技術(shù)是什么?答:關(guān)鍵技術(shù)是二叉樹的建立,以及棧結(jié)構(gòu)、隊列的算法實現(xiàn)問題3:課題的主要功能和模塊有哪些?答:1)主要功能:根據(jù)數(shù)據(jù)建立二叉樹,實現(xiàn)二叉樹的中序、前序、后序遍歷2)模塊:棧的應(yīng)用,隊列結(jié)構(gòu)的應(yīng)用,二叉樹的操作問題4:課題在實現(xiàn)過程中遇到的主要難點有哪些?答:遍歷二叉樹過程中棧結(jié)構(gòu)以及隊列的使用問題5:課題中未能實現(xiàn)的功能有哪些?答:以樹形結(jié)構(gòu)輸出完全二叉樹 記錄人:寇海洲 2012 年 12 月 28日目錄1需求分析51.1二叉樹與樹結(jié)構(gòu)51.2面向?qū)ο蟮某?/p>
4、序設(shè)計51.3二叉樹遍歷的應(yīng)用51.4軟件運行環(huán)境:Visual C+ 6.0版本52概要設(shè)計62.1 總體功能結(jié)構(gòu)62.2數(shù)據(jù)結(jié)構(gòu)部分設(shè)計62.2.1結(jié)點結(jié)構(gòu)62.2.2 二叉樹結(jié)構(gòu)73詳細設(shè)計123.1建立二叉樹123.1.1功能描述123.1.2算法原理123.1.3 具體程序123.2 前序遍歷133.2.1 功能原理133.2.2 算法原理133.2.3 具體程序133.3 中序遍歷143.3.1 功能原理143.3.2 算法原理143.3.3 具體程序143.4 后序遍歷153.4.1功能原理153.4.2 算法原理153.4.3 具體程序163.5層次序非遞歸遍歷173.5.1
5、功能原理173.5.2 算法原理173.5.3 具體程序173.6 棧結(jié)構(gòu)183.6.1 功能原理183.6.2算法原理183.6.3 具體程序183.7 隊列結(jié)構(gòu)193.7.1 功能原理193.7.2 算法原理193.7.3 具體程序194調(diào)試與操作說明20致 謝23參考文獻24附錄:251需求分析1.1二叉樹與樹結(jié)構(gòu)樹結(jié)構(gòu)的是建立在數(shù)據(jù)邏輯結(jié)構(gòu)基礎(chǔ)上的數(shù)據(jù)結(jié)構(gòu)類型,二叉樹則是樹結(jié)構(gòu)中最常見和使用最多的類型。通過對二叉樹的操作,可以實現(xiàn)多種數(shù)據(jù)操作,如排序、查找等。一個好的二叉樹遍歷算法應(yīng)包含以下功能:1)以遞歸和非遞歸方法建立二叉樹或完全二叉樹;2)實現(xiàn)二叉樹的前序遍歷、中序遍歷、后序遍歷
6、;3)每種遍歷算法皆以遞歸和非遞歸方法實現(xiàn);4)在具體實現(xiàn)時應(yīng)用其他數(shù)據(jù)結(jié)構(gòu)類型對數(shù)據(jù)進行操作,如:棧,隊列,數(shù)組。1.2面向?qū)ο蟮某绦蛟O(shè)計在面向?qū)ο蟮某绦蛟O(shè)計中,模板的使用很普遍,因此,如何在程序設(shè)計中使用模板使得方法的實現(xiàn)與定義分開,程序模塊化,既方便了程序設(shè)計者,又為程序的后期維護帶來便利。1.3二叉樹遍歷的應(yīng)用當數(shù)據(jù)以數(shù)組或文檔形式存儲在內(nèi)存時,其數(shù)據(jù)之間雖有邏輯聯(lián)系,卻過于分散,因此,建立二叉樹以存儲數(shù)據(jù)并且遍歷該二叉樹,可以從邏輯上理順數(shù)據(jù)之間的關(guān)系,使得原本分數(shù)的數(shù)據(jù)排列的有序且可靠。一個好的二叉樹應(yīng)用算法其空間復(fù)雜度與時間復(fù)雜度必然最低,這樣給程序帶來時間和空間上的極大優(yōu)化。1
7、.4軟件運行環(huán)境:Visual C+ 6.0版本2概要設(shè)計2.1 總體功能結(jié)構(gòu)二叉樹的遍歷,主要包含以下功能:1)建立二叉樹:遞歸方法、非遞歸方法2)中序遍歷:遞歸方法、非遞歸方法3)前序遍歷:遞歸方法、非遞歸方法4)后序遍歷:遞歸方法、非遞歸方法5)棧結(jié)構(gòu)使用:遍歷時輸入臨時變量以保存6)隊列結(jié)構(gòu)使用:完全二叉樹遍歷時用以存儲數(shù)據(jù)2.2數(shù)據(jù)結(jié)構(gòu)部分設(shè)計2.2.1結(jié)點結(jié)構(gòu) 二叉樹結(jié)點結(jié)構(gòu)中包數(shù)據(jù)域(data),指針域(*leftChild,*rightChild)。結(jié)點結(jié)構(gòu)的代碼如下:struct BinTreeNode/樹結(jié)點T data;BinTreeNode<T> *left
8、Child;BinTreeNode<T> *rightChild;BinTreeNode():leftChild(NULL), rightChild(NULL)BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL):leftChild(l), rightChild(r)data = x; 棧結(jié)構(gòu)結(jié)點包含數(shù)據(jù)域(data),指針域(*link),實現(xiàn)代碼如下:struct StackNode/棧結(jié)點T data;StackNode<T> *link;StackNode
9、(T d = 0, StackNode<T> *next = NULL):link(next),data(d);隊列結(jié)構(gòu)結(jié)點包含數(shù)據(jù)域(data),指針域(*link),實現(xiàn)代碼如下:struct LinkNodeT data;LinkNode<T> *link;LinkNode(LinkNode<T> *ptr=NULL)link = ptr;LinkNode(const T &item, LinkNode<T> *ptr = NULL)data = item;link = ptr;2.2.2 二叉樹結(jié)構(gòu) 二叉樹包含了遞歸、非遞歸建樹過
10、程,遞歸、非遞歸的前序遍歷、中序遍歷、后續(xù)遍歷過程。二叉樹的類定義包含各種操作,實現(xiàn)代碼如下:template <typename T>class BinaryTree/二叉樹類定義public:BinaryTree():root(NULL)BinaryTree(T value):root(NULL)RefValue = value;BinaryTree(BinaryTree<T> &s)if (this != &s)root=Copy(s.root);BinaryTree()destroy(root);BinTreeNode<T> *Par
11、ent(BinTreeNode <T> *t)return (root = NULL | root = t)?NULL:Parent(root, t);BinTreeNode<T> *LeftChild(BinTreeNode<T> *t)return (t != NULL)?t->leftChild:NULL;BinTreeNode<T> *RightChild(BinTreeNode<T> *t)return (t != NULL)?t->rightChild:NULL;void PreOrder(void (*vis
12、it)(BinTreeNode<T> *t)PreOrder(root, visit);void InOrder(void (*visit)(BinTreeNode<T> *t)InOrder (root, visit);void PostOrder(void (*visit)(BinTreeNode<T> *t)PostOrder(root, visit);void CreateCompBinTree(T *CBT, int num)/建立完全二叉樹CreateCompBinTree(CBT, num, 0, root);void levelOrder(v
13、oid (*visit)(BinTreeNode<T> *t);/層次序遍歷void PreOrder1(void (*visit) (BinTreeNode<T> *t);/非遞歸前序遍歷void InOrder1(void (*visit) (BinTreeNode<T> *t);/非遞歸中序遍歷void PostOrder1(void (*visit) (BinTreeNode<T> *t);/非遞歸后序遍歷friend istream& operator >> (istream &in, BinaryTree&
14、lt;T> &Tree)/輸入二叉樹Tree.CreateBinTree(in, Tree.root);return in;棧結(jié)構(gòu)的定義中,包含了對數(shù)據(jù)的入棧、出棧、清空等基本操作,實現(xiàn)代碼如下template <typename T>class LinkedStackprivate:StackNode<T> *top;public:LinkedStack():top(NULL)/無頭結(jié)點LinkedStack()makeEmpty();void Push(const T &x);bool Pop(T &x);bool IsEmpty()c
15、onstreturn top=NULL;bool IsFull()constreturn false;void makeEmpty();friend ostream& operator << (ostream &os, LinkedStack<T> &s)os<<"Stack Size: "<<s.getSize()<<endl;StackNode<T> *p=s.top;int i=0;while (p)os<<+i<<": "<
16、;<p->data<<endl;p=p->link;return os;template <typename T>void LinkedStack<T>:makeEmpty()StackNode<T> *p;while (top)p=top;top=top->link;delete p;隊列的類定義,實現(xiàn)了對數(shù)據(jù)的入隊、出隊操作,實現(xiàn)代碼如下:template <typename T>class LinkedQueue/無頭結(jié)點public:LinkedQueue()rear = NULL;front = NU
17、LL;LinkedQueue()makeEmpty();bool EnQueue(const T &x);bool DeQueue(T &x);void makeEmpty();bool IsEmpty()constreturn front = NULL;friend ostream& operator << (ostream &os, LinkedQueue<T> &Q)LinkNode<T> *p = Q.front;int i = 0;while (p)os << "#" <
18、< +i << ": " << p->data << endl;p = p->link;os << "Queue Size: " << Q.getSize() << endl;return os;void output();protected:LinkNode<T> *front, *rear;3詳細設(shè)計3.1建立二叉樹 3.1.1功能描述 二叉樹是程序的核心,如何合理的建立至關(guān)重要。本實例中使用遞歸和非遞歸方法分別建立二叉樹,二叉樹的數(shù)據(jù)來源于程序開始
19、時建立的數(shù)組。建立后的二叉樹保存,并且留作之后的遍歷使用。3.1.2算法原理 本實例使用的是完全二叉樹,首先建立頭結(jié)點,并且保存數(shù)據(jù),然后根據(jù)遞歸方法,分別建立其左右孩子結(jié)點,且左右孩子結(jié)點的指針域指向空。3.1.3 具體程序以遞歸方式建立二叉樹,每次建立一個結(jié)點后,將其左右孩子指針域置空,成為葉子結(jié)點。具體實現(xiàn)代碼如下:template <typename T>void BinaryTree<T>:CreateBinTree(istream &in, BinTreeNode<T> *& subTree)T item;if (in >&
20、gt; item)if (item != RefValue)subTree = new BinTreeNode<T>(item);/Create Rootassert(subTree);CreateBinTree(in, subTree->leftChild);/ Create left child treeCreateBinTree(in, subTree->rightChild);/ Create reght child treeelsesubTree = NULL;/建立完全二叉樹template<typename T>void BinaryTree&
21、lt;T>:CreateCompBinTree(T *CBT, int num, int rt, BinTreeNode<T> *& subTree)if (rt >= num)subTree = NULL;elsesubTree = new BinTreeNode<T>(CBTrt);CreateCompBinTree(CBT, num, 2*rt+1, subTree->leftChild);CreateCompBinTree(CBT, num, 2*rt+2, subTree->rightChild);3.2 前序遍歷3.2.1 功
22、能原理 通過前序遍歷,將二叉樹中的數(shù)據(jù)按照前序遍歷的結(jié)果輸出,達到前序便利的目的,方便數(shù)據(jù)的使用。3.2.2 算法原理前序遍歷使用了遞歸與非遞歸兩種方法,在程序頭文件中定義了兩個函數(shù)分別實現(xiàn)其功能。遞歸時,輸出第一個結(jié)點數(shù)據(jù)時,找到數(shù)據(jù),然后找到其后面的數(shù)據(jù),然后依次遞歸輸出。非遞歸時,使用棧和隊列結(jié)構(gòu),將部分數(shù)據(jù)保存在棧或隊列中,等待將數(shù)據(jù)放到合適位置。3.2.3 具體程序1)遞歸算法實現(xiàn):template <typename T>void BinaryTree<T>:PreOrder(BinTreeNode<T>* subTree, void (*vis
23、it)(BinTreeNode<T> *t)if (subTree != NULL)visit(subTree);PreOrder(subTree->leftChild, visit);PreOrder(subTree->rightChild, visit);2)非遞歸算法實現(xiàn):template <typename T>void BinaryTree<T>:PreOrder1(void (*visit) (BinTreeNode<T> *t) ) LinkedStack<BinTreeNode<T>*> S;B
24、inTreeNode<T> *p = root; S.Push (NULL);while (p!=NULL) visit(p); /訪問結(jié)點if (p->rightChild != NULL)S.Push (p->rightChild); /預(yù)留右指針在棧中if (p->leftChild != NULL) p=p->leftChild;/進左子樹else S.Pop(p);/左子樹為空,由堆棧彈出3.3 中序遍歷3.3.1 功能原理 通過中序遍歷,將二叉樹中的數(shù)據(jù)按照中序序遍歷的結(jié)果輸出,達到中序遍歷的目的,實現(xiàn)數(shù)據(jù)的最優(yōu),方便數(shù)據(jù)的使用。3.3.2 算法
25、原理中序遍歷使用了遞歸與非遞歸兩種方法,在程序頭文件中定義了兩個函數(shù)分別實現(xiàn)其功能。遞歸時,輸出第一個結(jié)點數(shù)據(jù)時,找到數(shù)據(jù),然后依次找到其后面的數(shù)據(jù),然后依次遞歸輸出。非遞歸時,使用棧和隊列結(jié)構(gòu),將部分數(shù)據(jù)保存在棧與隊列中,等待將數(shù)據(jù)放到合適位置。3.3.3 具體程序1)遞歸算法實現(xiàn):template <typename T>void BinaryTree<T>:InOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *t)if (subTree != NULL)InOrder(
26、subTree->leftChild, visit); visit(subTree);InOrder(subTree->rightChild, visit);2)非遞歸算法實現(xiàn):template <typename T> void BinaryTree<T>:InOrder1(void (*visit) (BinTreeNode<T> *t) /非遞歸中序遍歷 LinkedStack<BinTreeNode<T>*> S; BinTreeNode<T> *p = root; while(p!=NULL | !S
27、.IsEmpty ()while (p!= NULL) /遍歷指針向左下移動S.Push (p); /該子樹沿途結(jié)點進棧p=p->leftChild;if (!S.IsEmpty() /棧不空時退棧S.Pop(p);visit (p);/退棧, 訪問p=p->rightChild;/遍歷指針進到右子女3.4 后序遍歷3.4.1功能原理 通過后序遍歷,將二叉樹中的數(shù)據(jù)按照后序遍歷的結(jié)果輸出,達到后序遍歷的目的,實現(xiàn)數(shù)據(jù)的最優(yōu),方便數(shù)據(jù)的使用。3.4.2 算法原理后序遍歷使用了遞歸與非遞歸兩種方法,在程序頭文件中定義了兩個函數(shù)分別實現(xiàn)其功能。遞歸時,輸出第一個結(jié)點數(shù)據(jù)時,找到數(shù)據(jù),然后
28、依次找到其后面的數(shù)據(jù),然后依次遞歸輸出。非遞歸時,使用棧和隊列結(jié)構(gòu),將部分數(shù)據(jù)保存在棧與隊列中,等待將數(shù)據(jù)放到合適位置。3.4.3 具體程序1)遞歸算法實現(xiàn):template <typename T>void BinaryTree<T>:PostOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *t)if (subTree != NULL )PostOrder(subTree->leftChild, visit);PostOrder(subTree->rightCh
29、ild, visit);visit (subTree);2)非遞歸算法實現(xiàn):template <typename T>void BinaryTree<T>:PostOrder1(void (*visit) (BinTreeNode<T> *t)/非遞歸后序遍歷LinkedStack<stkNode<T> > S;stkNode<T> w; BinTreeNode<T> *p=root; /p是遍歷指針do while (p != NULL) w.ptr = p;w.tag = stkNode<T>:
30、L;/枚舉類型定義在struct stkNode中,如定義為全局性就簡單了S.Push (w); p = p->leftChild; int continue1 = 1; while (continue1 && !S.IsEmpty () S.Pop (w); p = w.ptr; switch (w.tag) /判斷棧頂?shù)膖ag標記 case stkNode<T>:L: w.tag = stkNode<T>:R; S.Push (w); continue1 = 0; p = p->rightChild; break; case stkNod
31、e<T>:R: visit (p); break; while (!S.IsEmpty();/繼續(xù)遍歷其他結(jié)點 cout << endl;3.5層次序非遞歸遍歷3.5.1 功能原理 層次序非遞歸遍歷,依據(jù)的是遞歸原理,每次遍歷一個結(jié)點后,同時讓其左右孩子入隊,以便達到層次序的目的。3.5.2 算法原理每次遍歷完一個結(jié)點后,檢查該結(jié)點是否為葉子結(jié)點,如果是葉子結(jié)點則繼續(xù)下一結(jié)點的遍歷,否則其左右孩子入隊,繼續(xù)遍歷。3.5.3 具體程序template <typename T>void BinaryTree<T>:levelOrder (void (
32、*visit) (BinTreeNode<T> *t) /層次序遍歷 if (root = NULL) return; LinkedQueue<BinTreeNode<T> *> Q; BinTreeNode<T> *p=root; visit(p); Q.EnQueue(p); while (!Q.IsEmpty () Q.DeQueue (p); if (p->leftChild != NULL) visit (p->leftChild); Q.EnQueue (p->leftChild); if (p->rightC
33、hild != NULL) visit (p->rightChild); Q.EnQueue(p->rightChild); 3.6 棧結(jié)構(gòu)3.6.1 功能原理 運用棧結(jié)構(gòu),在非遞歸算法中,未輸出的數(shù)據(jù)暫時存入棧中,依據(jù)先進后出原則,方便了二叉樹的遍歷。3.6.2算法原理二叉樹的結(jié)點信息,保存在棧中。第一個入棧的數(shù)據(jù)元素保存在棧底,后進棧的在上方,現(xiàn)出棧。3.6.3 具體程序template <typename T>void LinkedStack<T>:Push(const T &x)top = new StackNode<T>(x,
34、top);template <typename T>bool LinkedStack<T>:Pop(T &x)if (IsEmpty()return false;StackNode<T> *p = top;top=top->link;x=p->data;delete p;return true;3.7 隊列結(jié)構(gòu)3.7.1 功能原理 運用隊列結(jié)構(gòu),在層次序遍歷算法中,未輸出的數(shù)據(jù)暫時存入隊列中,依據(jù)先進先出原則,方便了二叉樹的遍歷。3.7.2 算法原理層次序遍歷二叉樹信息時,二叉樹的結(jié)點信息保存在隊列中。第一個入隊的數(shù)據(jù)元素保存隊首,后入隊
35、的元素依次連接上,先入隊的先出隊。3.7.3 具體程序template <typename T>void LinkedQueue<T>:makeEmpty()LinkNode<T> *p;while (front)p = front;front = front->link;delete p;template <typename T>bool LinkedQueue<T>:EnQueue(const T &x)if (!front)front = rear = new LinkNode<T>(x);if (!f
36、ront)return false;elserear->link = new LinkNode<T>(x);if (!(rear->link)return false;rear = rear->link;return true;template <typename T>bool LinkedQueue<T>:DeQueue(T &x)if (IsEmpty()return false;LinkNode<T> *p = front;x = front->data;front = front->link;dele
37、te p;return true;template <typename T>void LinkedQueue<T>:output()LinkNode<T> *p = front; int i = 1;while (i <= getSize()cout << p->data << " "<<endl;p = p->link; i+;4調(diào)試與操作說明操作說明:當程序運行后,會在控制臺提示一下文字:“從數(shù)組數(shù)據(jù)建立完全二叉樹:”,“ 輸入二叉樹的元素總個數(shù):”,然后從鍵盤輸入二叉樹元素個數(shù),
38、緊接著系統(tǒng)會自動運行,得到各種遍歷結(jié)果。運行截圖:完全二叉樹32個元素時的運行截圖總結(jié)這次的課程設(shè)計我選擇了二叉樹的遍歷,因為樹結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)課程的典型內(nèi)容,而且綜合使用了多種邏輯結(jié)構(gòu),具有代表性,可以鍛煉個人編程能力。在剛開始選題后,我感覺無從下手,一是因為沒有實踐經(jīng)驗,二是因為對數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容沒有把握到位,然后在參考一些專業(yè)書籍并且學習了之前其他人的課程設(shè)計,才逐漸可以上手去自己做。在做了一小段后我發(fā)現(xiàn)如果不使用數(shù)組來建立二叉樹是很麻煩的一件事,每個結(jié)點的信息都靠鍵盤輸入是不合理的,于是運用了數(shù)組這一數(shù)據(jù)類型。在之后的遞歸算法中,我遇到的最大困難是如何實現(xiàn)遞歸,為此我參考了一本專業(yè)書籍
39、,學會了如何正確使用遞歸方法,這也讓我感覺到學習與應(yīng)用是不可分開的。對于非遞歸算法,我使用了棧結(jié)構(gòu)和隊列結(jié)構(gòu),分別用于前序遍歷、中序、后序遍歷、非遞歸層次序遍歷方法中。使用棧和隊列的過程中,我在實踐中又學習了棧和隊列的一些知識,提高了各種邏輯結(jié)構(gòu)之間的綜合運用能力。在后期測試階段,我參考了許多課程設(shè)計案例,他們都運用了switch()語句,這樣雖然看著有條理,卻不適合用在二叉樹的遍歷上,因為遍歷結(jié)果顯而易見并不十分復(fù)雜,沒有必要使程序復(fù)雜化,因此我采用的是程序運行輸出模式??傮w來說,在本次課程設(shè)計中,我深刻體會了再面向?qū)ο蟪绦蛟O(shè)計中數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法,既學到了專業(yè)知識,也體會到“溫故知新”的樂
40、趣,因此如果還有課程設(shè)計我還會積極參加,在實踐中鍛煉自己的能力水平。致謝對我來說這次課程設(shè)計的機會來之不易,首先我的父母辛苦工作,用他們賺到的血汗錢供我讀書,讓我有機會接受高等教育。其次,我的課程設(shè)計指導(dǎo)老師寇老師,冒著嚴寒每天早早地到機房為我指導(dǎo)、調(diào)試程序,從沒有一句怨言。再者,我的數(shù)據(jù)結(jié)構(gòu)授課教師周教授,從一開始接觸這門課就不辭辛勞的給我傳授知識,教我學的立足社會的資本。對你們,我想發(fā)自內(nèi)心的說一句:謝謝你們,辛苦了!參考文獻(1)數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC+語言描述)殷人昆 清華大學出版社(2)深入體驗C+項目開發(fā) 管西京 清華大學出版社(3)C+程序員教程(美)Deitel.P.J.
41、,(美)Deitel,H.M.著北京電子工業(yè)出版社附錄:程序源代碼:/mian()主函數(shù)中:#include "BinaryTree.h"#include <iostream>#include <fstream>#include <iomanip>using namespace std;void visit(BinTreeNode<int> *t)cout<<t->data<<" "void main()BinaryTree<int> binTree(0);cout
42、 << "從數(shù)組數(shù)據(jù)建立完全二叉樹:n"cout << "輸入二叉樹的元素總個數(shù): "long num;cin >> num;int *CBT = new intnum;cout << "n數(shù)組中數(shù)據(jù)為:n"for (int i = 0; i < num; i+)CBTi = i+1;cout << setw(4) << i+1;cout << endl;BinaryTree<int> binTree1;binTree1.Create
43、CompBinTree(CBT, num);cout << "n完全二叉樹前序遍歷結(jié)果:n"binTree1.PreOrder(visit);cout << "nn完全二叉樹中序遍歷結(jié)果:n"binTree1.InOrder(visit);cout << "nn完全二叉樹后序遍歷結(jié)果:n"binTree1.PostOrder(visit);cout << "n完全二叉樹非遞歸前序遍歷結(jié)果:n"binTree1.PreOrder1(visit);cout <<
44、; "nn完全二叉樹非遞歸中序遍歷結(jié)果:n"binTree1.InOrder1(visit);cout << "nn完全二叉樹非遞歸后序遍歷結(jié)果:n"binTree1.PostOrder1(visit);cout << "n完全二叉樹層次序遍歷結(jié)果:n"binTree1.levelOrder(visit);cout<<endl;delete CBT;/包含在頭文件BinaryTree.h中#include <string>#include <cassert>#include
45、<iostream>using namespace std;#include"LinkedStack.h"#include"LinkedQueue.h"template <typename T>struct BinTreeNode/樹結(jié)點T data;BinTreeNode<T> *leftChild;BinTreeNode<T> *rightChild;BinTreeNode():leftChild(NULL), rightChild(NULL)BinTreeNode(T x, BinTreeNode&l
46、t;T> *l = NULL, BinTreeNode<T> *r = NULL):leftChild(l), rightChild(r)data = x;template <typename T>class BinaryTree/二叉樹類定義public:BinaryTree():root(NULL)BinaryTree(T value):root(NULL)RefValue = value;BinaryTree(BinaryTree<T> &s)if (this != &s)root=Copy(s.root);BinaryTree(
47、)BinTreeNode<T> *Parent(BinTreeNode <T> *t)return (root = NULL | root = t)?NULL:Parent(root, t);BinTreeNode<T> *LeftChild(BinTreeNode<T> *t)return (t != NULL)?t->leftChild:NULL;BinTreeNode<T> *RightChild(BinTreeNode<T> *t)return (t != NULL)?t->rightChild:NUL
48、L;void PreOrder(void (*visit)(BinTreeNode<T> *t)PreOrder(root, visit);void InOrder(void (*visit)(BinTreeNode<T> *t)InOrder (root, visit);void PostOrder(void (*visit)(BinTreeNode<T> *t)PostOrder(root, visit);void CreateCompBinTree(T *CBT, int num)/建立完全二叉樹CreateCompBinTree(CBT, num,
49、0, root);void levelOrder(void (*visit)(BinTreeNode<T> *t);/層次序遍歷void PreOrder1(void (*visit) (BinTreeNode<T> *t);/非遞歸前序遍歷void InOrder1(void (*visit) (BinTreeNode<T> *t);/非遞歸中序遍歷void PostOrder1(void (*visit) (BinTreeNode<T> *t);/非遞歸后序遍歷friend istream& operator >> (is
50、tream &in, BinaryTree<T> &Tree)/輸入二叉樹Tree.CreateBinTree(in, Tree.root);return in;protected:BinTreeNode<T> *root;/二叉樹的根指針T RefValue;/數(shù)據(jù)輸入停止標志void CreateBinTree(istream &in, BinTreeNode<T> *& subTree);/遞歸建立二叉樹void CreateCompBinTree(T *CBT, int num, int rt, BinTreeNode
51、<T> *& subTree);/建立完全二叉樹BinTreeNode<T> *Copy(BinTreeNode<T> *r);/復(fù)制二叉樹rvoid Traverse(BinTreeNode<T> *subTree, ostream &out);/遍歷輸出void PreOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *t);/前序遍歷void InOrder(BinTreeNode<T> *subTree, void (
52、*visit)(BinTreeNode<T> *t);/中序遍歷void PostOrder(BinTreeNode<T> *subTree, void (*visit)(BinTreeNode<T> *t);/后序遍歷;template <typename T>void BinaryTree<T>:CreateBinTree(istream &in, BinTreeNode<T> *& subTree)/私有函數(shù): 以遞歸方式建立二叉樹。T item;if (in >> item)if (it
53、em != RefValue)subTree = new BinTreeNode<T>(item);/Create Rootassert(subTree);CreateBinTree(in, subTree->leftChild);/ Create left child treeCreateBinTree(in, subTree->rightChild);/ Create reght child treeelsesubTree = NULL;template<typename T>void BinaryTree<T>:CreateCompBinT
54、ree(T *CBT, int num, int rt, BinTreeNode<T> *& subTree)/建立完全二叉樹if (rt >= num)subTree = NULL;elsesubTree = new BinTreeNode<T>(CBTrt);CreateCompBinTree(CBT, num, 2*rt+1, subTree->leftChild);CreateCompBinTree(CBT, num, 2*rt+2, subTree->rightChild);template<typename T>BinT
55、reeNode<T> *BinaryTree<T>:Copy(BinTreeNode<T> *r) /遞歸復(fù)制二叉樹 if (!r)return NULL; BinTreeNode<T> *p=new BinTreeNode<T>(r->data); p->leftChild = Copy(r->leftChild); p->rightChild = Copy(r->rightChild); return p;template <typename T>void BinaryTree<T&
56、gt;:Traverse(BinTreeNode<T> *subTree, ostream &out)/前序遍歷輸出結(jié)點數(shù)據(jù)if (subTree)out << subTree->data << ' 'Traverse(subTree->leftChild, out);Traverse(subTree->rightChild, out);template <typename T>void BinaryTree<T>:PreOrder(BinTreeNode<T>* subTree, void (*visit)(BinTreeNode<T> *t)/遞歸前序遍歷if (subTree != NULL)visit(subTree);PreOrde
溫馨提示
- 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. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 燃氣公司服務(wù)管理辦法
- 牧場牛糞銷售管理辦法
- 物業(yè)付費管理暫行辦法
- 物業(yè)準入退出管理辦法
- 物業(yè)小區(qū)入住管理辦法
- 物業(yè)快遞代簽管理辦法
- (2025年)山西省忻州市輔警協(xié)警筆試筆試模擬考試試題含答案
- 物業(yè)用水收費管理辦法
- 物業(yè)租戶車輛管理辦法
- 物業(yè)管理裝修管理辦法
- 化學●甘肅卷丨2024年甘肅省普通高中學業(yè)水平等級性考試高考化學真題試卷及答案
- 2025年高考真題-英語(全國一卷) 含答案
- 2025年山東省普通高中學業(yè)水平合格考預(yù)測歷史試卷(含答案)
- 倉庫組長考試試題及答案
- 衣柜廠家合作協(xié)議書
- 2025年數(shù)字媒體藝術(shù)考試試卷及答案
- 新生兒高膽紅素血癥診治指南(2025)解讀
- 2025-2030年中國線纜設(shè)備行業(yè)市場現(xiàn)狀供需分析及投資評估規(guī)劃分析研究報告
- 兒童情商課件
- T∕CWEA 29-2024 水利水電工程砌石壩施工規(guī)范
- 2025年湖北荊門市交通旅游投資集團有限公司招聘筆試參考題庫含答案解析
評論
0/150
提交評論