數(shù)據(jù)結(jié)構(gòu)課程設(shè)計二叉樹遍歷C++語言

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