数据结构课程设计报告
2011201年度第一学期201220112012年度第一学期
课程名称：题院班姓学
数据结构课程设计
目：建立二叉树并求指定结点路径系：级：名：号：电信学院计算机科学系
指导教师：成绩：
2011年12月18
f成绩评定
一、指导教师评语
二、成绩
成绩
备注
指导教师：指导教师：日日期：年月
f题目建立二叉树并求指定结点路径题目问题描述问题描述能够按照要求按先序遍历的次序输入二叉树的各个结点，而且能够输出中序遍历的序列和指定结点的路径，并且可以求出二叉树的深度，二叉树的叶子节点个数，以及交换二叉树的左右子树。基本要求基本要求分别建立二叉树存储结构的输入函数、输出中序遍历的函数，以及输出指定结点路径的函数，输出二叉树的深度，输出二叉树的叶子节点个数，以及交换二叉树的左右子树。
课程设计的需求和规格说明
1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该在程序运行窗口的主控菜单后，先选择“1”并回1车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值”之后，输入二叉树的先序序列结点值输入二叉树的先序序列结点值采用以下字符序列：ABCDEGF（以替代空格）作为建立
二叉树T的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成二叉树的链式存储结构建立完成二叉树的链式存储结构建立完成
图1二叉树的图形结构
2、二叉树的遍历。本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。需要在程序运行窗口的主控菜单中选择“2”并回车，程序运行窗口会出现2
f以下中序遍历序列：该二叉树的中序遍历序列是CBEGDFA该二叉树的中序遍历序列是该二叉树的中序遍历序列是3、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“3”并3回车，在程序运行窗口中提示信息“输入要求路径的结点值”输入“G”并回车，会得到结果为：→A→B→D→E→G如果输入“I”并回车，会得到结果为：没有要求的结点！没有要求的结点！没有要求的结点
设计
设计思想：设计思想：我们知道，在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访r