数据结构作业：唯一确定一棵二叉树.doc

.
二、唯一的确定一棵二叉树
需求分析
该程序的主要功能是根据给定的遍历二叉树的前序序列和中序序列，唯一构造出一棵二叉树，并输出该二叉树的后序序列，同时用凹入法打印该二叉树。

设计
1. 设计思想
程序中的值采用二叉树的存储结构。
（1）设计两个字符数组Pre和In存放前序序列和中序序列；
（2）根据定义，前序序列中第一个元素一定是树根，在中序序列中该元素之前的所有元素一定在左子树中，其余元素则在右子树中。所以，首先从数组Pre中取出第一个元素Pre[0]作根结点，然后在数组In中找到In[0]，以它为界，在其前面的是左子树中序序列，在其后面的是右子树中序序列；
（3）若左子树不为空，沿前序序列向后移动，找到左子树根结点，转（2）；
（4）左子树构造完毕后，若右子树不为空，沿前序序列向后移动，找到右子树根结点，转（2）；
（5）前序序列中各元素取完则二叉树构造完毕。
在二叉树构建的过程中使用了函数递归的方式。

2. 概要设计
程序中最主要的函数即为二叉树的构建函数BuildBiTree()
函数声明方式
void BuildBiTree(BiTreeNode* root,DataType Pre[],DataType In[],int flag[],int m,int n); 其中BiTreeNode* root为将要构建树的根节点；DataType Pre[]和DataType In[]为存储前序序列和中序序列的数组；int flag[]为标记数组，它用来区分In数组中的元素是否已经被加入二叉树中，标记为0时为未加入二叉树，标记为1时表示以加入二叉树；int m为即将加入二叉树的元素区间的下界；int m为即将加入二叉树的元素区间的上界。
结点操作函数 Visit()
函数声明方式：void visit(DataType item);
在进行二叉树的遍历时用来对结点进行一系列的操作。
打印二叉树函数 PrintBiTree()
函数声明方式：void PrintBiTree(BiTreeNode* root,int n);
打印二叉树函数同样采用递归的形式，用凹入法对二叉树进行打印输出。

3. 详细设计
算法开始阶段先是输入二叉树的前序序列和中序序列，然后调用构建二叉树函数BuildBitree()，并在函数内部进行递归调用进行二叉树的构建。构建完毕后，分别调用二叉树的前序、中序、后序遍历函数遍历二叉树并输出遍历结果，最后调用PrintBiTree()函数用凹入法打印输出二叉树。
我个人觉得比较巧妙的一个地方是设立了一个全局变量P来存储Pre数组的下标，即即将构建的子树的结点，在使用递归构建二叉树的时候不会因函数的结束而销毁变量。

4. 调试分析
这个程序应该算是我耗时最久的一个了，最初的问题是在碰到了构建二叉树函数的递归的栈溢出，调试的时候出现递归函数无法进入的情况从而以我目前的调试水平无法调试，后来又从头分析了一边函数才发现是某个循环的错误。解决这个问题后又出现了输出结果不正确的问题，经过调试后才发现是之前对算法的理解出了很大偏差，原因是只考虑了构造元素区间的上界而未考虑下界。所以对函数的结构做了一系列的改变，最终取得成功。
经分析，该程序的时间复杂度为O(lbn)，空间复杂度为O(lbn)。
虽然这个程序花费了我比较长的时间，但是它让我明白了调试的重要性，同时也重新熟悉了调试的方法，对我的编程技能有比较大的促进作用。在完成了这次实习之后，内心的喜悦之情无法言表。

5. 用户手册
接下来介绍一下该程序的使用方法：
（1） 编译运行程序；
（2） 按提示输入要构建的二叉树的结点（以PPT上测试数据为例）；
（3） 按提示输入该二叉树的前序序列；
（4） 按提示输入该二叉树的中序序列；
（5） 回车以后即可得出结果。

6. 测试结果
以题目中的数据为例，所测得结果如下：
同时测试了其他几组数据，结果均正确，在这不再上图。
精品文本