数据结构实验报告-二叉树的7种遍历算法及应用
- 格式：pdf
- 大小：160.50 KB
- 文档页数：11
printf("#先根序列：\n");
PreOrder2(BT);
printf(&#("#中根序列：\n");
InOrder2(BT);
printf("\n");
printf("#后根序列：\n");
PostOrder2(BT);
printf("\n");
printf("####层次遍历如下####\n");
if(top>0) p=stack[--top];
else break;
} p=p->rchild; }
} } //中根遍历，非递归的方法 void InOrder2(BiTree BT) {
BiTree stack[MAXSIZE]; int top=0; BiTree p=BT; while(!(p==NULL&&top==0)) {
Destroy(&((*BT)->lchild)); if((*BT)->rchild)
Destroy(&((*BT)->rchild)); free(*BT); *BT=NULL; } } //先根遍历，递归的方法 void PreOrder1(BiTree BT) { if(BT) { printf("%c\t",BT->data); PreOrder1(BT->lchild); PreOrder1(BT->rchild); } } //中根遍历，递归的方法 void InOrder1(BiTree BT) { if(BT) { InOrder1(BT->lchild); printf("%c\t",BT->data); InOrder1(BT->rchild); } } //后根遍历，递归的方法 void PostOrder1(BiTree BT) { if(BT) { PostOrder1(BT->lchild); PostOrder1(BT->rchild); printf("%c\t",BT->data); } } //先根遍历，非递归的方法 void PreOrder2(BiTree BT) { // 定义并且初始化栈 BiTree stack[MAXSIZE]; int top=0; BiTree p=BT;
// printf("请以广义表的形式输入二叉树:\n");
//建立二叉树并且默认初始化
BiTree BT;
Create(&BT,"(A(B(D,E(H,I)),C(F,G)))");
printf("二叉树建立完毕.\n");
// 以下为递归遍历
printf("####递归遍历如下####\n");
printf("#先根序列：\n");
PreOrder1(BT);
printf("\n");
printf("#中根序列：\n");
InOrder1(BT);
printf("\n");
printf("#后根序列：\n");
PostOrder1(BT);
printf("\n");
printf("####非递归遍历如下####\n");
int top=0;
BiTree p=BT;
BiTree q=NULL;
while(!(p==NULL&&top==0))
{
//入栈左孩子，直到结点没有左孩子；
while(p!=NULL)
{
stack[top++]=p;
p=p->lchild;
}
//
如果栈顶元素没有右孩子或者右孩子访问过，则出栈并访问；
DataType data; BiTree lchild; BiTree rchild; } BiNode; void Create(BiTree *,char str[]); void Destroy(BiTree *); void PreOrder1(BiTree); void PreOrder2(BiTree); void InOrder1(BiTree); void InOrder2(BiTree); void PostOrder1(BiTree); void PostOrder2(BiTree); void Level(BiTree); int main() {
四、测试结果
测试用例：二叉树 (A(B(D,E(H,I)),C(F,G)))
五、系统不足与经验体会
系统不足：算法效率不是非常高，有待改善
经验体会： 1 栈的用法非常灵活，有的时候不需要定义栈的数据类型。只需要用到栈的思想； 2 递归算法都可以用栈和循环来代替
六、附录：源代码（带注释）
/* 数据结构实验二：二叉树的各种遍历算法 计算机学院<6>班 杨瑞 学号：H090311001 2010-12-13 20:04:37 */ #include <stdio.h> #include <stdlib.h> #include <malloc.h> /*malloc 容错函数的宏定义*/ #define MALLOC(p,s) p=malloc(sizeof(s));\ if(p==NULL){\ fprintf(stderr,"Wrong Memory!\n");\ exit(-1);\ } //栈或者队列的默认容量 #define MAXSIZE 100 //定义数据类型 typedef char DataType; //定义二叉树的结构 typedef struct BiNode* BiTree; typedef struct BiNode {
数据类型定义及宏定义： /*malloc 容错函数的宏定义*/ #define MALLOC(p,s) p=malloc(sizeof(s));\ if(p==NULL){\ fprintf(stderr,"Wrong Memory!\n");\ exit(-1);\ }
//栈或者队列的默认容量 #define MAXSIZE 100 //定义数据类型 typedef char DataType; //定义二叉树的结构 typedef struct BiNode* BiTree; typedef struct BiNode {
Level(BT);
printf("\n");
// 销毁二叉树
printf("二叉树删除完毕.\n");
Destroy(&BT);
return 0;
}
//用广义表的形式输入二叉树，并且建立二叉树
void Create(BiTree *BT,char str[])
{
char ch;
BiTree stack[MAXSIZE];
算法思想： 用队列实现； 将根节点入队。 1 出队并输出节点的值。 2 若 存 在 左 右 孩 子 ，则 将 其 入 队 。 循 环 以 上 两 个 步 骤 ，直 到 队 列 为 空 。
删除二叉树
算法思想： 根据二叉树的定义。 （ 二叉树包含左右子树和根节点） 先 删 除 左 子 树 ，再 删 除 右 子 树 。最 后 释 放 根 节 点 。 仍然是递归实现。
while(!(p==NULL&&top==0)) {
//访问并入栈左孩子，重复直到不存在左孩子； while(p!=NULL) {
printf("%c\t",p->data); stack[top++]=p; p=p->lchild; } //出栈直到结点有右孩子，并把当前指针指向其右孩子。重复以上； if(top>0) { p=stack[--top]; while(p->rchild==NULL) {
递归遍历二叉树
非递归遍历二叉 树
层次遍历二叉树
算法思想： 根据二叉树的定义和遍历算法的定义 ，很 容 器 实 现 递 归 遍历的算法。
算法思想： 都是用栈实现； 先根： 1 访 问 并 入 栈 左 孩 子 ，重 复 直 到 不 存 在 左 孩 子 ； 2 出 栈 直 到 结 点 有 右 孩 子 ，并 把 当 前 指 针 指 向 其 右 孩 子 。重 复 以 上 两 个 步 骤 ； 中根： 1 入 栈 左 孩 子 ，直 到 结 点 没 有 左 孩 子 ； 2 出 栈 并 访 问 结 点 ，如 果 右 孩 子 存 在 ，则 把 当 前 指 针 指 向 右 孩 子 。重 复 以 上 两 步 ； 后根： 1 入 栈 左 孩 子 ，直 到 结 点 没 有 左 孩 子 ； 2 如果栈顶元素没有右孩子或者右孩子访问过，则 出 栈 并 访 问 ；如果栈顶元素右孩子存在且没被访问 过。则当前指针指向其右孩子 。重 复 以 上 两 个 步 骤；
哈尔滨工业大学计算机科学与技术学院
实验报告
课程名称：数据结构与算法 课程类型：必修 实验项目名称：二叉树的应用 实验题目：二叉树的建立、遍历
班级：计算机学院<6>班 学号：H090311001 姓名：杨瑞
设计成绩 报告成绩 指导老师
一、实验目的
掌握二叉树的建立方法，递归和非递归的遍历方法
二、实验要求及实验环境
DataType data; BiTree lchild; BiTree rchild; } BiNode; 函数集： void Create(BiTree *,char str[]); void Destroy(BiTree *); void PreOrder1(BiTree); void PreOrder2(BiTree); void InOrder1(BiTree); void InOrder2(BiTree); void PostOrder1(BiTree); void PostOrder2(BiTree); void Level(BiTree);
