数据结构之二叉树实 验 报 告 题目：二叉树得遍历与子树交换 指导老师：杨政宇 班级：通信１ 2 ０２ 姓名:徐江 学号:０ 9091 ２ 1 １２７需求分析1.演示程序分别用多种遍历算法遍历二叉树并把数据输出.2.输入字符序列,递归方式建立二叉树.3、在演示过程序中，用户敲击键盘，输入数据，即可瞧到数据得输出.4、实现链式存储得二叉树得多种遍历算法。遍历算法包括：a)中序递归遍历算法、前序递归遍历算法【选】b)中序遍历非递归算法c)先序或后序遍历非递归算法d)建立中序线索,并进行中序遍历与反中序遍历５、实现二叉树得按层遍历算法6、设计一个测试用得二叉树并创建对应得内存二叉树,能够测试自己算法得边界(包括树节点数为０、1以及>１ 得不同情形）。7、测试数据：输入数据:－＋a ＊b —ｃ d －ｅ f 概要设计说明:本程序在递归调用中用到了链表,在非递归调用时用到了栈。1.栈得抽象数据类型ADT S ｔ ack{数据对象：D=｛ａ i|ai∈cha ｒ，i=１，2,３……、、}数据关系:R=｛〈 ａ i －１,ai ＞｜ ai -1,ai ∈D,i＝２，3…、、｝基本操作:InitSt ａｃ k(＆Ｓ） 操作结果：构造一个空栈S ｔ ack Ｅ m ｐ t ｙ（ S ） ﻩ初始条件:栈 S 已存在. 操作结果:若 S 为空栈,则返回Ｏ K，否则返回 ERROR。 Pu ｓ h（ ＆S， e ）ﻫ 初始条件:栈 S 已存在。 操作结果:插入元素 e 为新得栈顶元素。 Pop（ &Ｓ， &e ） ﻩ初始条件:栈 S 已存在且非空. ﻫﻩ操作结果:删除 S 得栈顶元素，并用 e 返回其值。 GetT ｏｐ（ S, ＆ｅ ) ﻫ ﻩ初始条件:栈 S 已存在且非空. ﻩ操作结果:用 e 返回 S 得栈顶元素. }２、二叉树得抽象数据类型Ａ DT Bi ｎ ary Ｔｒ ee｛ 数据对象 D:D 就是具有相同特性得数据元素得集合。 ﻫﻩ数 据 关 系Ｒ： ﻩﻩ若 D=Φ，则 R=Φ,称 Bin ａ r ｙＴ r ｅ e 为空二叉树; ﻫﻩﻩ若 D≠Φ,则Ｒ={H}，H 就是如下二元关系； （1）在 D 中存在惟一得称为根得数据元素ｒｏ ot,它在关系 H 下无前驱; （2)若Ｄ-｛ｒ oot｝≠Φ，则存在Ｄ—{ｒ oo ｔ｝＝｛Ｄ 1,Ｄ r｝，且D1∩Dr =Φ； ﻩﻩ(３）若 D1≠Φ，则Ｄ 1 中存在惟一得元素ｘ１,〈ｒｏ ot,x １〉∈H，且存在Ｄ 1 上得ﻩﻩ 关系Ｈ 1 H⊆ ；若 D ｒ≠Φ,则 Dr 中存在惟一得元素ｘ r，＜ｒ oot，xr〉∈H，且ﻩﻩ 存在上得关系 Hr ⊆Ｈ...
