数据结构_课程设计__二叉树遍历.doc

1 《数据结构》课程设计报告题目: 二叉树的遍历日期: 2009-12-22 年级: 班级: 姓名: 学号: 、前序、后序的递归、非递归遍历算法, 层次序的非递归遍历算法的实现流程及操作步骤。加深理论知识,提高实践能力。、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,建树的实现。 1. 创建二叉树 2. 二叉树的递归遍历算法(前、中、后) 3. 二叉树的层次遍历算法 4. 二叉树的非递归遍历算法(前、中、后) 5. 退出以选择面板开始, 显得更为清晰。其中 3,4,5,6,8 为添加内容, 有助于更好的了解二叉树。 1. 创建二叉树(1) 定义二叉树结点值的类型为字符型。(2) 结点个数不超过 10 个。(3) 按先序次序输入,构造二叉链表表示的二叉树 T ,空格表示空树。 2. 二叉树的递归遍历算法(前、中、后) DLR (1) 访问根结点。(2) 先序遍历根结点的左子数。(3) 先序遍历根结点的右子数。 LDR (1) 先序遍历根结点的左子数。(2) 访问根结点。(3) 先序遍历根结点的右子数。 2 LRD (1) 先序遍历根结点的左子数。(2) 先序遍历根结点的右子数。(3) 访问根结点。 3. 二叉树的层次遍历算法(1) 访问该元素所指结点。(2) 若该元素所指结点的左右孩子结点非空, 则该元素所指结点的左孩子指针和右孩子指针顺序入队。 4. 二叉树的非递归遍历算法(前、中、后) (1 )非递归的先序遍历算法 a. 访问结点的数据域。 b. 指针指向 p 的左孩子结点。 c. 从栈中弹出栈顶元素。 d. 指针指向 p 的右孩子结点。(2 )非递归的中序遍历算法 a. 指针指向 p 的左孩子结点。 b. 从栈中弹出栈顶元素。 c. 访问结点的数据域。 d. 指针指向 p 的右孩子结点。(3 )非递归的后序遍历算法 bt 是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法,结点入栈时,配一个标志 tag 一同入栈(1 :遍历左子树前的现场保护, 2 :遍历右子树前的现场保护)。首先将 bt和 tag( 为 1) 入栈,遍历左子树; 返回后,修改栈顶 tag 为2 ,遍历右子树;最后访问根结点。 5. ab c def g34 #include "" #include "" #include "" typedef char ElemType;// 定义二叉树结点值的类型为字符型 const int MaxLength=10;// 结点个数不超过 10个 typedef struct BTNode{ ElemType data; struct BTNode *lchild,*rchild; }BTNode,* BiTree; void CreateBiTree(BiTree &T){// 按先序次序输入,构造二叉链表表示的二叉树 T ,空格表示空树// if(T) return; char ch; ch=getchar(); // 不能用 cin 来输入,在 cin 中不能识别空格。 if(ch==' ')