二叉排序树的实现(最终版).doc

1、实 验 报 告课程名称 数据结构课程设计 题目名称 二叉树的实现 学生学院 应用数学学院 专业班级 14 信安 1 班 学 号 3114008224 学生姓名 阮志敏 指导教师 刘志煌 2016 年 12 月 9 日二叉排序树的实现一、内容和要求。1) 编程实现二叉排序树，包括生成、插入、删除；2) 对二叉排序树进行先根、中根和后根非递归遍历；3) 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4) 分别用二叉排序树和数组去存储一个班（50 人以上）的成员信息（至少包括学号、姓名、成绩 3 项） ，对比查找效率，并说明在什么情况下二叉排序树效率高，为什么？5) 格式按

2、照作业的要求，对数据测试，分析，总结和改进的工作要做详细一点。2、解决方案和关键代码1.二叉排序树的实现。1) 首先定义二叉树的结构体，代码如下：struct TreeNode;typedef struct TreeNode *TreePosition;typedef struct TreeNode *SearchTree;typedef struct TreeNode *Tree;typedef int TreeElementType;struct TreeNode /二叉树TreeElementType element;/节点中的元素SearchTree left;/左儿子SearchTr

3、ee right;/右儿子int leght;/节点的深度，用于打印int position;/节点的位置，用于打印;2) 实现插入和生成二叉树节点的方法。在这里用到了递归插入的方法。SearchTree insertTreeNode(TreeElementType x,SearchTree tree)if(tree = NULL) tree = makeTree(x,NULL,NULL);/插入在该处else if(x element) tree-left = insertTreeNode(x,tree-left);else if(x tree-element) tree-right = i

4、nsertTreeNode(x,tree-right);/如果相等，什么也不做return tree;当 tree = NULL 时，就是递归终止的条件，也是插入该节点的地方，在这里，用 makeTree()方法创建一个节点，其代码如下：static SearchTree makeTree(TreeElementType x,SearchTree left,SearchTree right) SearchTree node = (SearchTree)malloc(sizeof(struct TreeNode);if(node = NULL)printf(“make TreeNode fail

5、!n“);else node-element = x;node-left = left;node-right = right;return node;3) 实现二叉树节点删除的方法。删除节点时有 3 种情况：情况一：被删除的节点同时含有左儿子和右儿子。在这种情况下，必须找出一个合适的节点来替代被删除的节点。由于二叉树的特性，被删除节点右子树中的节点都比左子树节点大，因此，可以替代原节点的节点必然在被删除节点的右子树中，并且是右子树的最小节点。所以，在这种情况下，应该把被删除节点的右子树中最小节点替代被删除节点。情况二：被删除节点只有一个子节点。显然，应该把它的子节点替代它。情况三：被删除节点没

6、有子节点。此时，直接删除它。具体代码如下,同样使用递归删除的方法：SearchTree deleteTreeNode(TreeElementType x,SearchTree tree) TreePosition tmpNode;if(tree = NULL)/到叶节点了，还没找到可以删除的printf(“not found!n“);else if(x element) tree-left = deleteTreeNode(x,tree-left);else if(x tree-element) tree-right = deleteTreeNode(x,tree-right);else if

7、(x = tree-element) if(tree-left /找出右子树中最小的tree-element = tmpNode-element;/把右子树中最小的值给当前树节点/把 tree 右子树中最小值的节点删除了,那个要删除的节点不可能有左儿子tree-right = deleteTreeNode(tree-element,tree-right);else /只有一个子节点，或者没有子节点tmpNode = tree;if(tree-left = NULL) /0 个子节点也包含在内tree = tree-right;else if(tree-right = NULL) tree =

8、tree-left;free(tmpNode);return tree;其中的 findMin()方法为找出以某个节点为根的树的最小节点，在这里可以用循环遍历tree-left 来实现，也可以用递归来实现，代码如下：TreePosition findMin(SearchTree tree) /递归实现if(tree = NULL)return NULL;if(tree-left != NULL) return findMin(tree-left);else return tree;2.对二叉排序树进行先根、中根和后根非递归遍历1) 先根遍历先根遍历先访问根，再访问左儿子，接着访问右儿子。上图中

9、的树，如果用先根遍历，顺序则是 A-B-E-F-C要实现非递归遍历，必须使用循环来进行遍历。这就需要使每次循环时，都有一致的操作。为了一致性，先定义每次循环中的一致性操作：每次循环只处理一个节点，也就是打印当前节点，其左节点要等到下次循环再打印，这时，如果当前节点有左右节点，则需要储存当前节点的左节点和右节点，以便下次循环时取出打印，如果没有左右节点，则直接进入下次循环。在这里，有两种数据结构可用于储存待打印节点，一个是队列，一个是栈。先尝试队列，队列的特性是先进先出，我们希望在访问完当前节点后，储存当前节点的左节点和右节点，以便下次循环进取出进行打印，因此，节点储存的顺序必须为先储存左节点，

10、再储存右节点。以上图的树为例：当用队列时，会先访问 A 节点，然后储存 B 到队列，再储存 C 到队列，此时，队列中的元素为 BC。下次循环时，会把 B 出列，访问完 B后，再储存 E 和 F，此时，队列中的元素为 CEF。下次循环时，会把 C 出列进行访问。显然，这种访问顺序 A-B-C 不是正确的访问顺序，正确的应该是 A-B-E，因此队列并不能满足要求。接下来用栈进行储存尝试。当使用栈时，由于栈的特性为后进先出，故在第一次循环时，先访问 A，然后把 C 入栈，再把 B 入栈，这时栈中的元素为 CB。下次循环时，把 B 出栈进行访问，然后把 F 入栈，再把 E 入栈。这时，访问顺序为 A-

11、B-E-F-C，因此，我们可以用栈来作为循环遍历时的储存数据结构。此时，每轮循环的步骤就很清晰了：如果栈非空，出栈一个元素作为当前节点，先访问或者打印当前节点，接着，如果当前节点有左儿子或者右儿子，则先把右儿子入栈，再把左儿子入栈然后进入下次循环。如果当前节点没有儿子，则直接进入下次循环。具体代码如下：void preorderTraversal(Tree tree) Stack stack = createStack(10);push(tree,stack);while(!isStackEmpty(stack) TreePosition node = pop(stack);printf(“%

12、d “,node-element);if(node-right != NULL) push(node-right,stack);if(node-left != NULL) push(node-left,stack);2) 中根遍历中根遍历中，先访问当前节点的左儿子，再访问当前节点，最后访问右儿子。上图的树中，中根遍历的顺序为 D-B-F-E-A-C。在中根遍历过程中，要访问当前节点，首先要访问当前节点的左节点，而如果左节点又有左节点，则会一直向左下去。比如要访问 A，则首先要访问 B，要访问 B 则要先访问 E。因此，在循环遍历开始前，可以先将 A 以及其左边的节点全部压入栈中，此时，栈中的元

13、素为 ABD，然后开始循环遍历。在循环中，先从栈中弹出一个节点，访问该节点，然后判断该节点是否有右节点，如果有右节点，则把其右子树中右节点开始的所有左节点压入栈中，这样，下一次循环就能访问到右节点所在子树的最左边节点了。因为要访问右节点，必须先访问右节点的左子树中的最左边的元素。比如上图的树中，在弹出 B 的时候，访问 B，然后 B 有右节点 E，因此，把 EF 都入栈，然后开始下一次循环。下一次循环开始时，就能取出 F 进行访问了。具体代码如下：/*中序遍历*/void inorderTraversal(Tree tree) Stack stack = createStack(30);if(

14、tree = NULL) printf(“the tree is NULL,cant traversaln“);else pushLeftToStack(tree,stack);while(!isStackEmpty(stack) TreePosition node = pop(stack);printf(“%d “,node-element);if(node-right)pushLeftToStack(node-right,stack); printf(“n“); 其中的 pushLeftToStack()方法从该节点开始，一直向左，把左节点全部压入栈中，代码如下：static void pushLeftToStack(Tree tree,Stack stack) while(tree) push(tree,stack);tree = tree-left; 3) 后根非递归遍历