1、北京郵電大學軟件學院2019-2020學年第1學期實驗報告課程名稱：算法與數據結構課程設計實驗名稱：樹及其應用實驗完成人：日 期：2019 年 11 月10 日實驗目的樹是一種應用極為廣泛的數據結構，也是這門課程的重點。它們的特點在于非線性。 廣義表本質上是樹結構。本章實驗繼續突出了數據結構加操作的程序設計觀點，但 根據這兩種結構的非線性特點，將操作進一步集中在遍歷操作上，因為遍歷操作是其他眾多操作的基礎。 遍歷邏輯的（或符號形式的）結構，訪問動作可是任何操作。本次實驗希望幫助學生熟悉各種存儲結構的特征，以及如何應用樹結構解決具體問題（即原理與應用的結合）。實驗內容必做內容1） 二叉樹的建立與

2、遍歷問題描述建立一棵二叉樹，并對其進行遍歷（先序、中序、后序），打印輸出遍歷結果。基本要求從鍵盤接受輸入（先序），以二叉鏈表作為存儲結構，建立二叉樹（以先序來建立），并采用遞歸算法對其進行遍歷（先序、中序、后序），將遍歷結果打印輸出。測試數據ABOi） 6 DE6 G6 6氏或申66表示空格字符）則輸出結果為先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA2）打印二叉樹結構問題描述按凹入表形式橫向打印二叉樹結構，即二叉樹的根在屏幕的最左邊，二叉樹的左子樹在測試數據由學生依據軟件工程的測試技術自己確定。注意測試邊界數據，如空二叉樹。實現提示(1)利用RDL遍歷方法；(2)利用結點的深

3、度控制橫向位置。選做內容采用非遞歸算法實現二叉樹遍歷。三、實驗環境Windows下利用vs 2019完成，語言C+四、實驗過程描述首先構造Tree類，內含樹的結構體BiTree ,以及本實驗所要用到的一 些操作typedef struct BiTNodeTElemType data;int degree, depth, level;/ 度，高度，高度差struct BiTNode * lchild, * rchild;/* 左右孩子指針 */ BiTNode , * BiTree ;實現相應功能：1、二叉樹的建立與遍歷構造二叉樹： 前序構造，先賦值，然后遞歸構造左子樹，遞歸構造右函數BiTNo

4、de * Tree :CreatBiTree( BiTree T) TElemType ch;/不跳過空格/輸入空格表示空子樹/分配空間/分配失敗就退出 bad_alloc ;/記錄度/度增加T->lchild);T->rchild);/遞歸創建左子樹/遞歸創建右子樹cin >> noskipws >> ch; if (ch ='')T = NULL;else T = new BiTNode ;if (! T) throw new std:T->degree = 0;(T)->data = ch;T->depth+;T-&g

5、t;lchild=CreatBiTree(T->rchild=CreatBiTree( if ( T->lchild != NULL)/有一個孩子度就加一if ( T->rchild != NULL)T->degree+;)return T;)銷毀二叉樹：后序遞歸銷毀左右子樹(需要先查找到子樹，銷毀再銷毀父親樹)void Tree:Release(BiTree T) if (T != NULL) Release(T->lchild);Release(T->rchild); delete T;)/前序遍歷void Tree :PreOrderTraverse(

6、/遞歸銷毀左子樹/遞歸銷毀右子樹BiTree T, void ( Tree :* Visit )( BiTree ) if ( T) /* T 不空 */(this ->* Visit )( T); /* 先訪問根結點 */PreOrderTraverse(T->lchild,PreOrderTraverse(T->rchild,) ) /中序遍歷 void Tree :InOrderTraverse( BiTreeVisit ); /*再先序遍歷左子樹*/Visit ); /*最后先序遍歷右子樹 */T, void (Tree :* Visit )( BiTree )if

7、( T)InOrderTraverse(T->lchild,Visit);/*先中序遍歷左子樹*/(this ->* Visit )( T); /* 再訪問根結點*/InOrderTraverse(T->rchild,Visit);/*最后中序遍歷右子樹 */后序遍歷void Tree :PostOrderTraverse( BiTreeT, void ( Tree :* Visit )( BiTree )if ( T)PostOrderTraverse(T->lchild,Visit);PostOrderTraverse(T->rchild,Visit);(th

8、is ->* Visit )( T); /* 再訪問根結點 */*先中序遍歷左子樹 */*最后中序遍歷右子樹 */查找深度int Tree :TreeDepth( int i, j;if (! T)return 0; /* if ( T->lchild)i = TreeDepth( elsei = 0;if ( T->rchild)j = TreeDepth(BiTree T) 空樹深度為0 */T->lchild);/* iT->rchild);/* j為左子樹的深度*/為右子樹的深度*/elsej = 0;T->depth = i > j ? i

9、+ 1 : j + 1; return T->depth;)/得到層數void Tree :getLevel(BiTree T, int level )if ( T) T->level = level ;getLevel(T->lchild,level+ 1);/得到左子樹的層數，左子樹根節點的層數比此節點多一getLevel(T->rchild,level+ 1);/得到右子樹的層數，右子樹根節點的層數比此節點多一)/非遞歸中序遍歷void Tree :NoRecInOrderTraverse(BiTreeT, void (Tree :* Visit )( BiTre

10、e ) LinkedStack <BiTree > S;BiTree p = T;while (p | !S.isEmpty() if (p) S.Push(p);p = p->lchild;)else p=S.Pop();( this ->* Visit )(p);/當節點不為空時就壓棧，然后判斷左孩子/返回到父節點/訪問p = p->rchild;/然后指向右節點)實驗二：2、打印二叉樹結構/中序遍歷RDLvoid Tree :InOrderTraverseRDL( BiTree T, void (Tree :* Visit )( BiTree ) (if (

11、 T) (InOrderTraverseRDL(T->rchild,Visit);/*先中序遍歷左子樹 */(this ->* Visit )( T); /* 再訪問根結點 */ InOrderTraverseRDL(T->lchild,Visit);/*最后中序遍歷右子樹*/) ) /打印二叉樹圖形 打印圖形時，需要中序遍歷 RDL (先遍歷右節點，再遍歷右節點)。每一個字符占一行， 所在的列根據此節點的層數來確定。( void printT( BiTree T) / 打印二叉樹圖形for ( int i = 0; i < T->level; i+) cout

12、<< "") cout << T->data << endl; )實驗3:采用非遞歸算法實現二叉樹遍歷 利用棧來模擬操作系統調用函數 判斷該節點是否為空，如果不為空就壓棧，否則彈出棧中最上層元素/非遞歸前序遍歷 void Tree :NoRecPreOrderTraverse( BiTree T, void (Tree :* Visit )( BiTree ) LinkedStack <BiTree > S;BiTree p = T;while (p | !S.isEmpty() if (p) (this ->*

13、Visit )(p);/ 先訪問S.Push(p);p = p->lchild;/當節點不為空時就壓棧，然后判斷左孩子) else /節點為空時p = S.Pop();/返回到父節點然后指向右節點p = p->rchild;/非遞歸后序遍歷后序遍歷時如果當前結點左右子樹均為空，則可以訪問當前結點，或者左右子 樹不均為空，但是前一個訪問的結點是當前結點的左孩子或者右孩子，則也可 以訪問當前結點否則則壓入棧中。壓棧時先壓右節點再壓左節點。void Tree :NoRecPostOrderTraverse( BiTree T, void (Tree :* Visit )( BiTree

14、) (LinkedStack <BiTree > S;S.Push( T);BiTree pre = NULL;BiTree cur;while (!S.isEmpty() (cur = S.Peek();if ( cur->lchild=為空/將根節點壓棧/前一個節點/現在的節點/如果棧不為空就一直進行/觀測現在的節點，不彈出NULL && cur->rchild= NULL )| ( pre!= NULL &&( pre= cur->rchild|pre=cur->lchild)一個訪問的結點是當前結點的左孩子或者右孩子，

15、則可以訪問/左右子樹不均/或前()(cur);/彈出此節點/改變現在的pre(this ->* Visit cur = S.Pop(); pre = cur;)else if (cur->rchild != NULL ) S.Push(cur->rchild);/如果右孩子不為空就壓入棧) if ( cur->lchild != NULL ) S.Push(cur->lchild);/如果左孩子不為空就壓入棧) ) ) )void visitT(BiTree T) /輸出節點上的字符數據cout << T->data;五、實驗結果：輸入兩組樹，分

16、別進行相關運算，得到如下結果:的 Ucrc5ctt V:;ual StLcl o 討羥司金1輸入一個樹：Swc DE G F工前序遍歷：.VBCDEGF中序遍歷:CBEGDFA后序遍歷:CGEFDBA打印圖形:AFDG花BC非遞歸前序遍歷:ABCDEGF非遞歸中序遍歷;CBEGDFA非遞歸后序遍歷;("GEFDBAD: 'Homework'算法與數據結構'chapG'tree'xMMJebugVtma exe (進程 14020J已退出，運何代科為：0六、源代碼:LinkedStack.h 棧的模板類 #pragma once #include

17、 <exception> template < typename T> struct Node T data;Node <T>* next;template < typename T> class LinkedStack private :Node <T>* top;public :LinkedStack();LinkedStack();void Push( T);T Pop();T Peek(); bool isEmpty();template < typename T> LinkedStack <T>:Li

18、nkedStack() top = nullptr ;template < typename T> LinkedStack <T>:LinkedStack() Node <T>* p = nullptr ; while (top) p = top; top = top->next; delete p; template < typename T> void LinkedStack <T>:Push( T e) Node<T>* p = new Node<T> p->data = e ;p->n

19、ext = top;top = p;template < typename T> T LinkedStack <T>:Pop() if (!top)throw - 1;/如果為空則失敗Node <T>* p = top;T e = p->data; top = top->next; delete p; p = NULL; return e; template < typename T> T LinkedStack <T>:Peek() if (!top)throw - 1;/如果為空則失敗T e = top->dat

20、a;return e;template < typename T>bool LinkedStack <T>二isEmpty() return top = nullptr ;Tree.h#pragma once#include <iostream>#include <string>#include "LinkedStack.h" using namespace std; typedef char TElemType ;typedef int Status ; /* Status 是函數的類型，其值是函數結果狀態代碼，如O符*/t

21、ypedef int Boolean ; /* Boolean 是布爾類型，其值是 TRU或 FALSE */ typedef struct BiTNode TElemType data;int degree, depth, level;/ 度，高度，高度差struct BiTNode * lchild, * rchild;/* 左右孩子指針 */ BiTNode , * BiTree ;class Treeprivate :BiTree root; int rootDepth;BiTNode * CreatBiTree( BiTree T);/ 構造二叉樹void Release( BiTr

22、ee T);/ 銷毀二叉樹void InOrderTraverse( BiTree , void (Tree :* Visit )( BiTree );/ 中序遍歷void InOrderTraverseRDL( BiTree , void (Tree :* Visit )( BiTree ); /RDL中序遍歷void PostOrderTraverse( BiTree , void (Tree :* Visit )( BiTree ); / 后序遍歷 void PreOrderTraverse( BiTree , void (Tree :* Visit )( BiTree ); / 前序遍

23、歷 int TreeDepth( BiTree T);/ 測量樹的深度void NoRecPreOrderTraverse( 遞歸前序遍歷void NoRecInOrderTraverse( 歸中序遍歷void NoRecPostOrderTraverse( 遞歸后序遍歷void getLevel( BiTree , int );/測量樹的層數(節點所在層數)BiTree , void (Tree :* Visit )( BiTree );/ 非BiTree , void (Tree :* Visit )( BiTree ); / 非遞BiTree , void (Tree :* Visit

24、)( BiTree ); / 非public :Tree() / 構造函數，調用 CreatBiTree()root = NULL;root = CreatBiTree(root);rootDepth = TreeDepth(root);getLevel(root, 1);Tree()/析構函數Release(root); void visitT( BiTree T) cout << T->data;void printT( BiTree T) for ( int i = 0; i <cout << " "/輸出節點上的字符數據/打印二叉

25、樹圖形T->level; i+) cout << T->data << endl;/下面的幾個函數是為了給外部調用而設計的void PreOrderTraverse( void (Tree :* Visit )( BiTree ) PreOrderTraverse(root, Visit );void InOrderTraverse( void ( Tree :* Visit )( BiTree ) InOrderTraverse(root, Visit );InOrderTraverseRDL(root, void PostOrderTraverse( v

26、oidPostOrderTraverse(root, void NoRecPreOrderTraverse(NoRecPreOrderTraverse(root, void NoRecInOrderTraverse(NoRecInOrderTraverse(root, void NoRecPostOrderTraverse(void InOrderTraverseRDL( void (Tree :* Visit )( BiTree ) Visit );(Tree :* Visit )( BiTree ) Visit );void ( Tree :* Visit )( BiTree ) Visi

27、t );void (Tree :* Visit )( BiTree ) Visit );void (Tree :* Visit )( BiTree ) NoRecPostOrderTraverse(root, Visit );Tree.cpp#include "Tree.h"/構造二叉樹BiTNode * Tree :CreatBiTree( BiTree T) TElemType ch;/不跳過空格/輸入空格表示空子樹/分配空間/分配失敗就退出 bad_alloc ;/記錄度/度增加T->lchild);T->rchild);/遞歸創建左子樹/遞歸創建右子樹c

28、in >> noskipws >> ch if (ch ='')T = NULL;else T = new BiTNode ;if (! T) throw new std:T->degree = 0;(T)->data = ch;T->depth+;T->lchild=CreatBiTree(T->rchild=CreatBiTree(if ( T->lchild !=NULL)T->degree+;/有一個孩子度就加一if ( T->rchild !=NULL)T->degree+;return T

29、;/銷毀二叉樹void Tree :Release( BiTree T) if ( T != NULL) /遞歸銷毀左子樹/遞歸銷毀右子樹Release( T->lchild);Release( T->rchild);delete T;/前序遍歷BiTree T, void (Tree :* Visit )( BiTree ) void Tree :PreOrderTraverse( if ( T) /* T 不空 */(this ->* Visit )( T); /* 先訪問根結點 */再先序遍歷左子樹*/最后先序遍歷右子樹 */PreOrderTraverse(T->

30、;lchild,Visit );/*PreOrderTraverse(T->rchild,Visit );/* BiTree T, void (Tree :* Visit )( BiTree )/中序遍歷void Tree :InOrderTraverse( if ( T)InOrderTraverse( T->lchild, Visit ); /* 先中序遍歷左子樹 */ (this ->* Visit )( T); /* 再訪問根結點*/InOrderTraverse( T->rchild, Visit ); /* 最后中序遍歷右子樹*/中序遍歷RDL void T

31、ree :InOrderTraverseRDL( BiTree T, void (Tree :* Visit )( BiTree ) if ( T) InOrderTraverseRDL(T->rchild,Visit);/*先中序遍歷左子樹*/(this ->* Visit )( T); /* 再訪問根結點 */ InOrderTraverseRDL(T->lchild,Visit);/*最后中序遍歷右子樹 */ /后序遍歷 void Tree :PostOrderTraverse( BiTree T, void (Tree :* Visit )( BiTree ) if

32、( T)PostOrderTraverse(T->lchild,Visit);/*先中序遍歷左子樹 */PostOrderTraverse(T->rchild,Visit);/*最后中序遍歷右子樹*/(this ->* Visit )( T); /* 再訪問根結點 */ /查找深度int Tree 二TreeDepth( int i, j;if (! T)return 0; /* if ( T->lchild)i = TreeDepth( elsei = 0;if ( T->rchild)j = TreeDepth(BiTree T) 空樹深度為0 */T->

33、;lchild);/* iT->rchild);/* j為左子樹的深度*/為右子樹的深度*/elsej = 0;T->depth = i > j ? i + 1 : j + 1; return T->depth;/得到層數void Tree :getLevel( BiTree if ( T) T->level = level ;getLevel( T->lchild,點的層數比此節點多一getLevel( T->rchild, 點的層數比此節點多一 T, int level )level+ 1);level+ 1);/得到左子樹的層數，左子樹根節/得到

34、右子樹的層數，右子樹根節/非遞歸前序遍歷void Tree :NoRecPreOrderTraverse( LinkedStack <BiTree > S;BiTree p = T;while (p | !S.isEmpty() if (p) ( this ->* Visit )(p);BiTree T, void ( Tree :* Visit )( BiTree )/先訪問S.Push(p);p = p->lchild;/當節點不為空時就壓棧，然后判斷左孩子) else p = S.Pop();/返回到父節點然后指向右節點p = p->rchild;)/非遞歸

35、中序遍歷void Tree :NoRecInOrderTraverse( BiTree T, void (Tree :* Visit )( BiTree ) LinkedStack <BiTree > S;BiTree p = T;while (p | !S.isEmpty() if (p) S.Push(p);p = p->lchild;)else p=S.Pop();(this ->* Visit )(p); p = p->rchild;) /非遞歸后序遍歷/當節點不為空時就壓棧，然后判斷左孩子/返回到父節點/訪問/然后指向右節點BiTree T, void (Tree :* Visit )( BiTree )LinkedStack <BiTree > S;S.Push( T);BiTree pre = NULL;BiTree cur;while (!S.isEmpty() cur = S.Peek();if ( cur->lchild=為空/將根節點壓棧/前一個節點/現在的節點/如果棧不為空就一直進行/觀測現在的節點，不彈出NULL && cur->rchild= NULL )/左右子樹不均void Tree :