二叉树的遍历(先序.中序.后序)

实践三：树的应用

1.实验目的要求

通过本实验使学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法。认识哈夫曼树、哈夫曼编码的作用和意义。

实验要求：建一个二叉树并按照前序、中序、后序三种方法遍历此二叉树， 正确调试本程序。

能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。写出实验报告。

2.实验主要内容

2.1 对二叉树进行先序、中序、后序递归遍历，中序非递归遍历。

2.2 根据已知的字符及其权值，建立哈夫曼树，并输出哈夫曼编码。

3．实验步骤

2.1实验步骤

● 输入p127二叉链表的定义

● 录入调试p131算法6.4，实现二叉树的构造函数

● 编写二叉树打印函数，可以通过递归算法将二叉树输出为广义表的

形式，以方便观察树的结构。

● 参考算法6.1，实现二叉树的前序、中序和后序的递归遍历算法。

为简化编程，可以将visit函数直接使用printf函数输出结点内容来

代替。

#include

#include

#include

#define OK 1

#define ERROR 0

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef char TElemType;

typedef char Status;

// 构造书的结构体

typedef struct BiTNode{

TElemType data;

struct BiTNode *lchild, *rchild;

}BiTNode, *BiTree;

// 构造栈的结构体

typedef BiTree SElemType;

typedef struct{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

Status InitStack(SqStack &S){

//构造一个空栈

S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base)exit(-2);

S.top = S.base;

S.stacksize = STACK_INIT_SIZE;

return OK;

}

Status StackEmpty(SqStack S){

//若栈S为空栈，则返回TRUE,否则返回FALSE

if(S.top==S.base)

else

}

return 1; return 0;

Status Push(SqStack &S,SElemType e){

//插入元素e为新的栈顶元素

if(S.top - S.base >= S.stacksize){

S.base = (SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType));

if(!S.base)exit(-2); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; }

*S.top++ = e;

return OK;

}

Status Pop(SqStack &S,SElemType &e){

//若栈不空，则删除S的栈顶元素，用e返回其值并返回OK,否则返回ERROR

if(S.top == S.base) return ERROR;

e = * --S.top;

return OK;

}

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){

//非递归中序遍历二叉树

SqStack S;

BiTNode * p;

InitStack(S);

p = T;

while(p||!StackEmpty(S)){

} else { Pop(S,p); if(!Visit(p->data)) return 0; } p=p->rchild;

return 1;

}

//以下是递归遍历

Status CreateBiTree(BiTree &T){

//构造二叉树T

char ch;

scanf("%c",&ch);

if(ch == ' ') T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(-2);

}

return 1;

}

Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){

T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); //递归先序遍历 if(T){ if(Visit(T->data))

}

if(PreOrderTraverse(T->rchild,Visit)) return 1; return 0; }else return 1;

Status MinOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){

}

Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){

}

Status PrintElement(TElemType e){

//Visit函数，输出元素 //递归后续遍历 if(T){ if(PostOrderTraverse(T->lchild,Visit)) if(PostOrderTraverse(T->rchild,Visit)) if(Visit(T->data)) return 1; //递归中序遍历 if(T){ if(MinOrderTraverse(T->lchild,Visit)) if(Visit(T->data)) if(MinOrderTraverse(T->rchild,Visit)) return 1; return 0; }else return 1; return 0; }else return 1;

printf("%c ",e);

return 1;

}

//主函数

void main(){

BiTNode* p;

printf("Enter Node:\n");

CreateBiTree(p);

printf("递归先序遍历：");

PreOrderTraverse(p,PrintElement);

printf("\n递归中序遍历：");

MinOrderTraverse(p,PrintElement);

printf("\n递归后序遍历：");

PostOrderTraverse(p,PrintElement);

printf("\n");

printf("\n非递归中序遍历：");

InOrderTraverse(p,PrintElement);

printf("\n");

}

输入：ABCE000DF00G00HJ00K0L00 (“0”表示空格) 输出：

实践三：树的应用

1.实验目的要求

通过本实验使学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法。认识哈夫曼树、哈夫曼编码的作用和意义。

实验要求：建一个二叉树并按照前序、中序、后序三种方法遍历此二叉树， 正确调试本程序。

能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。写出实验报告。

2.实验主要内容

2.1 对二叉树进行先序、中序、后序递归遍历，中序非递归遍历。

2.2 根据已知的字符及其权值，建立哈夫曼树，并输出哈夫曼编码。

3．实验步骤

2.1实验步骤

● 输入p127二叉链表的定义

● 录入调试p131算法6.4，实现二叉树的构造函数

● 编写二叉树打印函数，可以通过递归算法将二叉树输出为广义表的

形式，以方便观察树的结构。

● 参考算法6.1，实现二叉树的前序、中序和后序的递归遍历算法。

为简化编程，可以将visit函数直接使用printf函数输出结点内容来

代替。

#include

#include

#include

#define OK 1

#define ERROR 0

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef char TElemType;

typedef char Status;

// 构造书的结构体

typedef struct BiTNode{

TElemType data;

struct BiTNode *lchild, *rchild;

}BiTNode, *BiTree;

// 构造栈的结构体

typedef BiTree SElemType;

typedef struct{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

Status InitStack(SqStack &S){

//构造一个空栈

S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base)exit(-2);

S.top = S.base;

S.stacksize = STACK_INIT_SIZE;

return OK;

}

Status StackEmpty(SqStack S){

//若栈S为空栈，则返回TRUE,否则返回FALSE

if(S.top==S.base)

else

}

return 1; return 0;

Status Push(SqStack &S,SElemType e){

//插入元素e为新的栈顶元素

if(S.top - S.base >= S.stacksize){

S.base = (SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType));

if(!S.base)exit(-2); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; }

*S.top++ = e;

return OK;

}

Status Pop(SqStack &S,SElemType &e){

//若栈不空，则删除S的栈顶元素，用e返回其值并返回OK,否则返回ERROR

if(S.top == S.base) return ERROR;

e = * --S.top;

return OK;

}

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){

//非递归中序遍历二叉树

SqStack S;

BiTNode * p;

InitStack(S);

p = T;

while(p||!StackEmpty(S)){

} else { Pop(S,p); if(!Visit(p->data)) return 0; } p=p->rchild;

return 1;

}

//以下是递归遍历

Status CreateBiTree(BiTree &T){

//构造二叉树T

char ch;

scanf("%c",&ch);

if(ch == ' ') T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(-2);

}

return 1;

}

Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){

T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); //递归先序遍历 if(T){ if(Visit(T->data))

}

if(PreOrderTraverse(T->rchild,Visit)) return 1; return 0; }else return 1;

Status MinOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){

}

Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){

}

Status PrintElement(TElemType e){

//Visit函数，输出元素 //递归后续遍历 if(T){ if(PostOrderTraverse(T->lchild,Visit)) if(PostOrderTraverse(T->rchild,Visit)) if(Visit(T->data)) return 1; //递归中序遍历 if(T){ if(MinOrderTraverse(T->lchild,Visit)) if(Visit(T->data)) if(MinOrderTraverse(T->rchild,Visit)) return 1; return 0; }else return 1; return 0; }else return 1;

printf("%c ",e);

return 1;

}

//主函数

void main(){

BiTNode* p;

printf("Enter Node:\n");

CreateBiTree(p);

printf("递归先序遍历：");

PreOrderTraverse(p,PrintElement);

printf("\n递归中序遍历：");

MinOrderTraverse(p,PrintElement);

printf("\n递归后序遍历：");

PostOrderTraverse(p,PrintElement);

printf("\n");

printf("\n非递归中序遍历：");

InOrderTraverse(p,PrintElement);

printf("\n");

}

输入：ABCE000DF00G00HJ00K0L00 (“0”表示空格) 输出：


相关文章

  • 二叉树深度优先遍历.广度优先遍历

    • 1. 简述树的深度优先遍历和广度优先遍历及其非递归实现的特点. 2011-09-19 10:49:34| 分类: | 标签: |字号大中小 订阅 二叉树的深度优先遍历.广度优先遍历和非递归遍历 二叉树的遍历: D:访问根结点,L:遍历根结点 ...查看


  • 二叉树的遍历算法

    • 二叉树的前序.后序的递归.非递归遍历算法 摘 要 本课程设计主要解决树的前序.后序的递归.非递归遍历算法,层次序的非递归遍历算法的实现.在课程设计中,系统开发平台为Windows 2000,程序设计设计语言采用Visual C++,程序运行 ...查看


  • 二叉树的遍历 1

    • 课 程 设 计 课程设计名称: 数据结构课程设计 专 业 班 级 : 学 生 姓 名 : 学 号 : 指 导 教 师 : 课程设计时间: 2015.6.29-2015.7.10 1.需求分析 题目:二叉树的前序.中序.后序的递归非递归的遍历 ...查看


  • 哈工大数据结构与算法2树型结构的建立与遍历

    • 哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称:数据结构与算法 科学与技术四班 1110310422 课程类型:必修 实验项目名称:树型结构的建立与遍历 实验题目: 二叉树的运用 班级:计算机 学号: 姓名:胡明 一.实验目的 (1 ...查看


  • 二叉树的遍历

    • 目 录 一.设计思想---------------------.01 二.算法流程图--------------------.01 三.源代码----------------------.04 四.运行结果----------------- ...查看


  • 二叉树实验报告

    • <数据结构> 课程设计报告 专 业 计算机科学与技术 班 级 3班 姓 名 学 号 指导教师 起止时间 2012.12~2013.1 课程设计:二叉树 一.任务描述 二叉树的中序.前序.后序的递归.非递归遍历算法,应包含建树的实 ...查看


  • 深度优先遍历与广度优先遍历

    • 深度优先遍历 1．深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过.在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过:然后依次从v出发搜索v的每个邻接点w.若w未曾访问 ...查看


  • 二叉树的中序的递归.非递归遍历算法

    • 信息工程学院<数据结构> 课程设计报告 设计题目 二叉树的中序的递归.非递归遍历算法 专 业 班 级 小 组 成 员 一． 题目:二叉树的中序的递归.非递归遍历算法 二． 小组任务分工 马凯:编写二叉树中序递归遍历.非递归遍历 ...查看


  • 二叉树的创建与遍历

    • 昆明理工大学信息工程与自动化学院学生实验报告(三) (2011-2012学年 第1学期) 课程名称:数据结构 开课实验室:计算中心204 2011年 11月 6日 一.上机内容和目的 内容:二叉树的建立,遍历. 目的:了解二叉树的基本性质, ...查看


  • 树和二叉树实验

    • 树和二叉树实验 实验题目:二叉树的实现 一. 实验目的 (1)掌握二叉树的逻辑结构: (2)掌握二叉树的二叉链表存储结构: (3)验证二叉树的二叉链表存储及遍历操作 二. 实验内容: (1)建立一颗含有 n 个节点的二叉树,采用二叉链表存储 ...查看


热门内容