算法与数据结构试验报告——树及其应用

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 :