二叉树的基本操作实现及其应用

目录

一、实验目的 ...................................................... 2 二、实验内容 ...................................................... 2 三、实验步骤 ...................................................... 2

㈠、数据结构与核心算法的设计描述 ............................... 2 ㈡、函数调用及主函数设计 ....................................... 3 ㈢ 程序调试及运行结果分析 ...................................... 4 ㈣ 实验总结 .................................................... 4 四、主要算法流程图及程序清单 ....................................... 5

1、主要算法流程图： ............................................ 5 2、程序清单 .................................................... 6

1

实验 三 二叉树的基本操作实现及其应用

一、实验目的

1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。

3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。

二、实验内容

题目一 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树 ，

2按（A:先序 B:中序 C:后序 ）遍历输出二叉树的所有结点 以上比做，以下选做

3求二叉树中所有结点数 4求二叉树的深度

三、实验步骤

㈠、数据结构与核心算法的设计描述

1) 二叉树结构类型定义： typedef struct BiTNode {

char data;

struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 2）队列节点定义： typedef struct QNode {

BiTree bt;

struct QNode *next;

2

}QNode,*QueuePtr; 3）队列类型定义：

struct LinkQueue队列类型定义 {

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 PostOrderTraverse ( BiTree T) // 后序遍历二叉树 9） void out(BiTree T) //从左到右，从上到下遍历二叉树 10）void nodesum(BiTree &T) //二叉树节点总数 11）int Depth (BiTree T )// 返回二叉树的深度

12）void InitQueue ( LinkQueue &Q )// 构造一个空队列 Q 13）EnQueue ( LinkQueue &Q,BiTree &e )// 进队 14）DeQueue ( LinkQueue &Q, BiTree &e )//出队

15）Status emptyQueue(LinkQueue &Q) //判断队列是否空

㈡、函数调用及主函数设计

3

先序建立二叉树 主 函 数 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 上下左右依次遍历 二叉树总结点数 二叉树深度 其他键退出 ㈢ 程序调试及运行结果分析

1.先序建立二叉树时，应用getchar（）函数，从流中读入字符； 2.上下左右依次遍历二叉树时，判断结束的条件是栈是否空； 3.队列节点的数据域应定义成二叉树型的； 4.求节点总数时，计数n应定义成全局变量。 5.求深度的k也应是全局变量。

㈣ 实验总结

以前只是学一些零碎的东西，通过做实验，让我们把这些零碎的东西拼接成一个小小的程序。让我们在做实验时对整体的把握得以提高。

这次实验既培养了自己的动手能力，又加深了对知识的认识，同时使自己有了解决问题的思路和方法。在这次实验的过程中，我知道了一些如何查找错误的方法，掌握了一些关于如何调试来解决自己的代码编译错的技巧。自己在以后的学习过程中加强锻炼，多写写，多练练，把书本上的知识应用到实际问

4

题中去，达到所学以用。

通过这次实验，我对二叉树更加了解，还有跟队列的结合，是我对知识有更深的应用。

四、主要算法流程图及程序清单

1、主要算法流程图：

开 始

构造空队列，T入

队，输出T->data

是

栈是否

空 否

队头元素

是 出队 是 T->lchild 否 是否空

T->lchild入队 否 输出T->rchild T->lchild->data 是否空

T->rchild入队

输出T->lchild->data 结 束 5

从上到下，从左到右遍历二叉树图

2、程序清单

#include #include #include #define Status int

#define OVERFLOW 1 #define OK 1 #define ERROR 0 int 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 LinkQueue //队列类型定义 { 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;

6

}

Status emptyQueue(LinkQueue &Q) //判断队列是否空 { if(Q.front == Q.rear) return 1; else return 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.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 );

7

T->data =ch; CreateBiTree ( T->lchild ); CreateBiTree ( T->rchild ); } }

Status Visit(char e) { cout<Status PreOrderTraverse ( BiTree T)//先序遍历二叉树 { if ( T ) { if ( Visit ( T->data ) ) 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; return ERROR; } else return OK; }

8

Status 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); cout<data<<\" \"; while(!emptyQueue(Q)) { DeQueue (Q,T); if(T->lchild) { EnQueue(Q,T->lchild); cout<lchild->data<<\" \"; } if(T->rchild) { EnQueue(Q,T->rchild); cout<rchild->data<<\" \"; } }

9

}

void nodesum(BiTree &T) //二叉树节点总数 { if(T) { n++; nodesum(T->lchild); 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() { cout<<\"1.先序建立一个二叉树\"<10

char b; BiTree T; do { cin>>a; 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);cout<>b; }while(b=='Y'); }

11