《程序设计实践》实验报告二叉树

编辑:阿文时间:2020-06-17 13:31:04
《程序设计实践》实验报告二叉树,学院实践课程设计,综合应用所学的知识分析问题解决问题,二叉树的非递归遍历是用显示栈来储存二叉树的节点指针,并将结点指针入栈。

学院实践课程设计

一、实验目的

掌握二叉树的定义、基本操作,综合应用所学的知识分析问题、解决问题,学会用建立二叉树并对其进行遍历,提高实际编程能力及程序调试能力。

二、实验要求

建立并遍历二叉树(pre-order遍历、middle-order遍历、post-order遍历、hierarchy遍历)。

三、实验方法内容

1. 算法设计思路

二叉树的非递归遍历是用显示栈来储存二叉树的节点指针,先序遍历时,按二叉树的前序遍历的顺序访问接点,并将结点指针入栈,直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针,访问刚取出的指针指向的结点的右指针指向结点并将其指针入栈,如此反复执行则为非递归操作。

二叉树递归遍历:如果二叉树为空,则为空操作

先序遍历:

(a)访问根结点;

(b) 首先,遍历左子树;

(c) 首先,遍历右子树。

中序遍历:

(a) 中间级遍历左子树

(b) 访问根结点;

(c) 中间顺序遍历右子树。

后序遍历:

(a) 左子树的后序遍历

(b) 后序遍历右子树

(c)访问根结点;

层次遍历:

它从二叉树的第一层(根节点)开始,从上到下逐层遍历。在同一层中,从左到右依次访问节点。

2。算法中使用的数据结构

(1)void createbitree 以二叉链表表示二叉树,建立一棵二叉树;

(2) void预序遍历输出二叉树的预序遍历结果;

(3) void inordertraverse输出二叉树的中间级遍历结果;

(4) void postordertraverse输出二叉树的后序遍历结果;

(5) int leafnodecount统计二叉树中的叶结点数;

(6) int node count统计二叉树中的结点数;

(7) int depth计算二叉树的深度。

(8) int swap交换二叉树中每个结点的左右子结点;

3. 主要的常量变量

void createbitree

void preordertraverse

void inordertraverse

void postordertraverse

int leafnodecount

int nodecount

int depth

int swap

四、实验**

#include

#include

#define max 100

//二叉树结构定义

typedef struct node

binnode;

typedef binnode*bintree;

typedef struct qnode *queue;

//队列结构定义

struct qnode;

//判断队列是否为空

int isqueue(queue q)

//定义队列并初始化

queue createemptyqueue()

//入队

void enqueue(queue *ptrq,bintree t)

else

}//出队

bintree dequeue(queue *ptrq)

else

} //一阶递归创建二叉树

void creatbintree(bintree *t)

}//二叉树的前序递归遍历

void preorder(bintree t)

}//中阶递归遍历二叉树

void midorder(bintree t)

}//二叉树的后序递归遍历

void postorder(bintree t) }

//带队列的二叉树层次遍历

void btqueue(bintree t)

{ queue q;

bintree t;

t=(bintree)malloc(sizeof(binnode));

if(t)

{q=createemptyqueue();

enqueue(&q,t);