《二叉树的基本操作实现及其应用》由会员分享，可在线阅读，更多相关《二叉树的基本操作实现及其应用（11页珍藏版）》请在金锄头文库上搜索。
1、1目录一、实验目的 .1二、实验内容 .1三、实验步骤 .1、数据结构与核心算法的设计描述 .1、函数调用及主函数设计 .2 程序调试及运行结果分析 .3 实验总结 .3四、主要算法流程图及程序清单 .31、主要算法流程图： .32、程序清单 .42实验 三 二叉树的基本操作实现及其应用一、实验目的1熟悉二叉树结点的结构和对二叉树的基本操作。2掌握对二叉树每一种操作的具体实现。3学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4.会用二叉树解决简单的实际问题。二、实验内容 题目一 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函
2、数定义和主函数。1 按先序次序建立一个二叉树 ，2 按（A:先序 B:中序 C:后序 ）遍历输出二叉树的所有结点 以上比做，以下选做3 求二叉树中所有结点数 4 求二叉树的深度 三、实验步骤、数据结构与核心算法的设计描述1) 二叉树结构类型定义：typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;2）队列节点定义：typedef struct QNode BiTree bt;struct QNode *next;3QNode,*QueuePtr; 3）队列类型定义：struct LinkQ
3、ueue 队列类型定义QueuePtr front; /队头指针QueuePtr rear; /队尾指针;4） 初始化二叉树，即把二叉树置空：void BiTreeInit (BiTree &T)5） 按先序建立一个二叉树：Status CreateBiTree ( BiTree &T ) 按先序次序输入二叉树中结点值（一个字符） ，空格字符表示空树。构造二叉链表表示的二叉树 T。6） Status PreOrderTraverse ( BiTree T)/先序遍历二叉树7） Status InOrderTraverse ( BiTree T) / 中序遍历二叉树8） Status PostO
4、rderTraverse ( BiTree T) / 后序遍历二叉树9） void out(BiTree T) /从左到右，从上到下遍历二叉树10）void nodesum(BiTree &T) /二叉树节点总数11）int Depth (BiTree T )/ 返回二叉树的深度12）void InitQueue ( LinkQueue &Q )/ 构造一个空队列 Q13）EnQueue ( LinkQueue &Q,BiTree &e )/ 进队14）DeQueue ( LinkQueue &Q, BiTree &e )/出队15）Status emptyQueue(LinkQueue &Q
5、) /判断队列是否空、函数调用及主函数设计4 程序调试及运行结果分析1.先序建立二叉树时，应用 getchar（）函数，从流中读入字符；2.上下左右依次遍历二叉树时，判断结束的条件是栈是否空；3.队列节点的数据域应定义成二叉树型的；4.求节点总数时，计数 n 应定义成全局变量。5.求深度的 k 也应是全局变量。 实验总结以前只是学一些零碎的东西，通过做实验，让我们把这些零碎的东西拼接成一个小小的程序。让我们在做实验时对整体的把握得以提高。这次实验既培养了自己的动手能力，又加深了对知识的认识，同时使自己有了解决问题的思路和方法。在这次实验的过程中，我知道了一些如何查找错误的方法，掌握了一些关于如
6、何调试来解决自己的代码编译错的技巧。自己在以后的学习过程中加强锻炼，多写写，多练练，把书本上的知识应用到主 函 数先序建立二叉树先序遍历二叉树中序遍历二叉树后序遍历二叉树上下左右依次遍历二叉树总结点数其他键退出二叉树深度5实际问题中去，达到所学以用。通过这次实验，我对二叉树更加了解，还有跟队列的结合，是我对知识有更深的应用。四、主要算法流程图及程序清单1、主要算法流程图：否否否结 束队头元素出队T-lchild是否空T-lchild 入队输出 T-lchild-dataT-rchild是否空是T-rchild 入队输出 T-lchild-data是开 始构造空队列，T 入队，输出 T-data
7、栈是否空是6从上到下，从左到右遍历二叉树图2、程序清单#include#include#include#define Status int#define OVERFLOW 1#define OK 1#define ERROR 0int n=0,k;typedef struct BiTNode /二叉树节点定义char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct QNode /队列节点定义BiTree bt;struct QNode *next;QNode,*QueuePtr; struct LinkQue
8、ue /队列类型定义QueuePtr front; /队头指针QueuePtr rear; /队尾指针;void InitQueue ( LinkQueue &Q )/ 构造一个空队列 Q Q.front = Q.rear = ( QueuePtr ) malloc ( sizeof ( QNode ) );if ( ! Q.front ) exit ( OVERFLOW ); / 存储空间分配失败Q.front-next = NULL; 7 Status emptyQueue(LinkQueue &Q) /判断队列是否空if(Q.front = Q.rear)return 1;elseret
9、urn 0;void EnQueue ( LinkQueue &Q,BiTree &e )/ 进队QueuePtr p = ( QueuePtr ) malloc ( sizeof ( QNode ) );if ( ! p ) exit ( OVERFLOW ); p-bt = e; p-next = NULL;Q.rear-next = p; Q.rear = p; void DeQueue ( LinkQueue &Q, BiTree &e )/出队if ( Q.front = Q.rear ) return ; QueuePtr p = Q.front-next; e = p-bt; Q
10、.front-next = p-next; if ( Q.rear = p ) Q.rear = Q.front; free ( p ); void CreateBiTree (BiTree &T) /先序建立二叉树char ch;ch=getchar();if (ch= ) T = NULL; else if ( ! ( T = ( BiTNode * ) malloc ( sizeof ( BiTNode ) ) ) ) exit ( OVERFLOW );8T-data =ch;CreateBiTree ( T-lchild ); CreateBiTree ( T-rchild ); S
11、tatus Visit(char e)coutdata ) )if ( PreOrderTraverse ( T-lchild) ) if ( PreOrderTraverse ( T-rchild) )return OK; return ERROR; else return OK;Status InOrderTraverse ( BiTree T) / 中序遍历二叉树 if ( T ) if ( InOrderTraverse ( T-lchild) ) if ( Visit ( T-data ) ) if ( InOrderTraverse ( T-rchild) )return OK;
12、return ERROR; else return OK; 9Status PostOrderTraverse ( BiTree T) / 后序遍历二叉树if ( T ) if ( PostOrderTraverse ( T-lchild) ) if ( PostOrderTraverse ( T-rchild) ) if ( Visit ( T-data ) )return OK; return ERROR; else return OK;void out(BiTree T) /从左到右，从上到下遍历二叉树LinkQueue Q;InitQueue (Q);EnQueue (Q,T);cou
13、tdatalchild)EnQueue(Q,T-lchild);coutlchild-datarchild)EnQueue(Q,T-rchild);coutrchild-datalchild);nodesum(T-rchild);int Depth (BiTree T )/ 返回二叉树的深度 if (T )int depthLeft = Depth( T-lchild );int depthRight= Depth( T-rchild );k = 1 +(depthLeft depthRight ? depthLeft : depthRight); else k = 0;return k;void main()couta;switch(a)case 1:CreateBiTree (T);break;case 2:PreOrderTraverse (T);break;case 3:InOrderTraverse (T);break;case 4:PostOrderTraverse (T);break;case 5:out(T);break;case 6:nodesum(T);coutb;while(b=Y);
