首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


WPL 最小的二叉树称为最优二叉树或赫夫曼树。

第二节 二叉树的基本运算实验

【问题描述】 二叉树采用二叉链表作存储结构,试编程实现二叉树的如下基本操作: 1. 按先序序列构造一棵二叉链表表示的二叉树 T; 2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历序列,分别输出结点的遍历序列; 3. 求二叉树的深度/结点数目/叶结点数目; 4. 将二叉树每个结点的左右子树交换位置。 【数据描述】

//- -

- -

- - 二叉树的二叉链表存储表示

-

-

- -

- -

-

typedef struct BiTNode{ TElemType Struct }BiTNode, * 【算法描述】 1. 建立一棵二叉树 Status CreateBiTree(BiTree &T) BiTNode BiTree; data; * lchild, * rchild; //左右孩子指针

//按先序次序输入二叉树中结点的值(一个字符),#字符表示空树, //构造二叉链表表示的二叉树 T。 scanf(&ch); if else (ch=='#') { if (!(T=(BiTNode ch; //生成左子树 //生成右子树 *) malloc(sizeof(BiTNode)))) exit (OVERFLOW); T=NULL;

T->data =

//生成根结点

CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK;

}//CreateBiTree 2. 先序遍历二叉树递归算法 Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){

//采用二叉链表存储结构,Visit 是对数据元素操作的应用函数, //先序遍历二叉树 T,对每个结点调用函数 Visit 一次且仅一次。 //一旦 visit()失败,则操作失败。 if (T){ if if (Visit(T->data)) return OK;

(PreOrderTraverse(T->rchild,Visit)) ERROR; return OK;

return }else

}// PreOrderTraverse 3. 中序遍历的递归算法 Status if (T){ if if (Visit(T->data)) return OK; InOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){

(InOrderTraverse(T->rchild,Visit)) ERROR; return OK;

return }else

}// InOrderTraverse 4. 后序遍历递归算法 Status if (T){ if if (Visit(T->data)) return OK; PostOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){

(PreOrderTraverse(T->rchild,Visit)) ERROR; return OK;

return }else

}// PreOrderTraverse 5. 中序遍历非递归算法之一 Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)) {

InitStack(S); Push(S,T); While (!StackEmpty(S)) { //向左走到尽头 //根指针进栈

While (GetTop(S,p) && p) Push(S,p->lchild); Pop(S,p); If (!StackEmpty(S)) Pop(S,p); If (!Visit(p->data)) return ERROR; {

//空指针退栈 //访问结点,向右一步

Push(S,p->rchild); }//if }//while

return

OK; }//InOrderTraverse

6.

中序遍历非递归算法之二 InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)) {

Status

//采用二叉链表存储结构,Visit 是对数据元素操作的应用函数。 //中序遍历二叉树 T 的非递归算法,对每个数据元素调用函数 Visit。 InitStack(S); p=T; While (p‖!StackEmpty(S)) if else (p) {Push(S,p); { { //根指针进栈,遍历左子树 //根指针退栈,访问根结点,遍历右子树

p=p->lchild;}

Pop(S,p); if (!Visit(p->data)) p=p->rchild); }//else }//while return OK; }//InOrderTraverse 7. 层次遍历二叉树的非递归算法 Status LevelOrder(BiTree T){ return ERROR;

//按层次遍历二叉树 T, Q 为队列 InitQueue(Q); If (T!=NULL){// 若树非空

EnQueue(Q,T);//根结点入队列 While (!QueueEmpty(Q)){ DeQueue(Q,b); Visit(b->data); If If }//while //队首元素出队列 //访问结点 EnQueue(Q,b->lchild);//左子树非空,则入队列 EnQueue(Q,b->rchild);//右子树非空,则入队列

(b->lchild!=NULL) (b->rchold!=Null)

}//if }LevelOrder 8. 求二叉树的深度 int depth(BiTree T){ //若 T 为空树,则深度为 0,否则其深度等于左子树或右子树的最大深度加 1 if else (T==NULL) return 0; {dep1=depth(T->lchild); dep2=depth(T->rchild); return } } 【C 源程序】 #include #include <stdio.h> <stdlib.h> 20 dep1>dep2?dep1+1:dep2+1;

#define MAX

#define NULL 0 typedef typedef char TElemType; int Status;

typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree; Status char CreateBiTree(BiTree ch; *T){

ch=getchar(); if else (ch=='#') (*T)=NULL; { */ /*生成根结点 ; /*构造左子树 */ */ /* #代表空指针*/

(*T)=(BiTree) malloc(sizeof(BiTNode));/*申请结点 (*T)->data=ch; CreateBiTree(&(*T)->lchild)

CreateBiTree(&(*T)->rchild) } return } void PreOrder(BiTree T){ if (T) { 1;

;

/*构造右子树

*/

printf("%2c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } void LevleOrder(BiTree T){

/*访问根结点,此处简化为输出根结点的数据值*/ /*先序遍历左子树*/ /*先序遍历右子树*/

/*层次遍历二叉树 T,从第一层开始,每层从左到右*/ BiTree Queue[MAX],b; /*用一维数组表示队列,front 和 rear 分别表示队首和队尾指针*/

int front,rear; front=rear=0; if (T) /*若树非空*/ {Queue[rear++]=T; /*根结点入队列*/ /*当队列非空*/

while (front!=rear){ b=Queue[front++];

/*队首元素出队列,并访问这个结点*/

printf("%2c",b->data); if if (b->lchild!=NULL) Queue[rear++]=b->lchild; /*左子树非空,则入队列*/

(b->rchild!=NULL) } }

Queue[rear++]=b->rchild; /*右子树非空,则入队列*/

}//LevelOrder int depth(BiTree T){ int dep1,dep2; if (T==NULL) return 0; {dep1=depth(T->lchild); /*求二叉树的深度*/

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 

数据结构实验指导书 - 数据结构 实验指导书 院别 专业 班级 姓名 计算机学院编 实验一 线性表的顺序存储实验 一、实验目的及要求 1、掌握在TC环境下调试顺序表...

数据结构与算法实验指导书90969 - 数据结构与算法实验指导书 计算机与信息学院 实验一 【实验目的】 顺序表 熟练掌握线性表在顺序存储结构上的基本操作。 【实验...

数据结构实验指导书02 很好!很好!隐藏&gt;&gt; 实验二 2.1 实验目的: 线性表 (1)掌握线性表的顺序存储结构的定义及 C 语言实现。 (2)掌握线性表在顺序存储结构即...

数据结构实验说明书新版 - the principl e of simplified E IA of constr uction pr oject s in the regi on. In te...

数据结构实验指导书 - 数据结构实验指导(C语言版)... 数据结构实验指导书_IT/计算机_专业资料。数据结构实验指导(C语言版) 数据结构实验指导书 江西农业大学计算机与...

数据结构试验指导书V2[1].0 - V 2.0 数据结构与算法 实验指导书 编写: 编写:陆绍飞 校核: 校核:___ 湖南大学软件学院 2011 年 9 月 湖南大学软件学...

数据结构实验指导书(2012.9) - 1.2 实验报告(文档)书写规范 实验报告(文档)应包括以下 7 个方面的内容: 1、问题分析 根据对实验任务的理解, 以无歧义的陈述...

09级《数据结构》实验指导书 - 《数据结构实验指导书》 潘向辉/吴学毅编写 印包学院数字媒体技术专业 2011 年 3 月 实验说明 实验说明 【实验环境】 操作系统:...

空间数据结构基础实验指导书 隐藏&gt;&gt; 《空间数据结构基础》 课程实习指导书实习周数:2 周 学分数:2 一、实习目的 数据结构是一门重要的专业基础课,其特点是理论...

《数据结构(C 语言版) 》实验指导书(非计算机专业适用) 广州大学 2013.1 目 录 实验一 线性表的顺序存储及其操作... 1 实验二 线性表的链式存储及其操作......


 

热点推荐