2025年二叉树遍历算法实践与数据结构深度解析教程.docxVIP

数据构造之二叉树

实验报告

题目：二叉树的遍历和子树互换指导老师：杨政宇

班级：通信1202

姓名：徐江学号：

需求分析

1.演示程序分别用多种遍历算法遍历二叉树并把数据输出。2.输入字符序列，递归方式建立二叉树。

3.在演示过程序中，顾客敲击键盘，输入数据，即可看到数据的输出。4.实现链式存储的二叉树的多种遍历算法。

遍历算法包括：

a)中序递归遍历算法、前序递归遍历算法【选】b)中序遍历非递归算法

c)先序或后序遍历非递归算法

d)建立中序线索，并进行中序遍历和反中序遍历5.实现二叉树的按层遍历算法

6.设计一种测试用的二叉树并创立对应的内存二叉树，可以测试自己算法的边界(包括树节点数为0、1以及1的不一样情形)。

7.测试数据：输入数据：-+a*b-cd-ef

概要设计

阐明：本程序在递归调用中用到了链表，在非递归调用时用到了栈。

1.栈的抽象数据类型

ADTStack{

数据对象：D={a;|ai∈char,i=1,2,3….……}

数据关系：R={ai-1,ai|aj-1,a;∈D,i=2,3.……}基本操作：

InitStack(S)

操作成果：构造一种空栈

StackEmpty(S)

初始条件：栈S已存在。

操作成果：若S为空栈，则返回OK,否则返回ERROR。

Push(S,e)

初始条件：栈S已存在。

操作成果：插入元素e为新的栈顶元素。

Pop(S,e)

初始条件：栈S已存在且非空。

操作成果：删除S的栈顶元素，并用e返回其值。

GetTop(S,e)

初始条件：栈S已存在且非空。

操作成果：用e返回S的栈顶元素。

}

2.二叉树的抽象数据类型

ADTBinaryTree{

数据对象D:D是具有相似特性的数据元素的集合。

数据关系R:

若D=φ,则R=φ,称BinaryTree为空二叉树；若D≠φ,则R={H},H是如下二元关系；

(1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱；(2)若D-{root}≠φ,则存在D-{root}={D1,Dr},且DINDr=φ;

(3)若Dl≠φ,则D1中存在惟一的元素x1,root,x1∈H,且存在D1

上的关系H1SH;若Dr≠D,则Dr中存在惟一的元素xr,root,xr∈H,

且存在上的关系HrEH;H={root,x1,root,xr,H1,Hr};

(4)(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。

基本操作：

CreateBiTree(T)

初始条件：给出二叉树T的定义。

操作成果：按规定构造二叉树T。

PreOrderTraverse_re(T,print()

初始条件：二叉树T存在，print是二叉树所有结点输出的应用函数。

操作成果：先序递归遍历T,对每个结点调用函数print一次且仅一次。一旦print()失败，则操作失败。

InOrderTraverse(T,print()

初始条件：二叉树T存在，print是二叉树所有结点输出的应用函数。

操作成果：中序非递归遍历T,对每个结点调用函数print一次且仅一次。

旦printf()失败，则操作失败。

InOrderTraverse_re(T,print()

初始条件：二叉树T在在，print是二叉树所有结点输出的应用函数。

操作成果：中序递归遍历T,对每个结点调用函数print一次且仅一次。一旦printf()失败，则操作失败。

PreOrderTraverse(T,printO)

初始条件：二叉树T存在，print是二叉树所有结点输出的应用函数。

操作成果：先序非递归遍历T,对每个结点调用函数print一次且仅一次。旦print()失败，则操作失败。

Levelorder(T)

初始条件：二叉树T在在。

操作成果：分层遍历二叉树T,并输出。

InOrderThreading(Thrt,T);

初始条件：二叉树T在在。

操作成果：中序遍历二叉树，并将其中序线索化。

InOrderTraverse_Thr(T,print);

初始条件：二叉树T在在。

操作成果：中序非递归遍历二叉线索树T

InThreading(p);

初