《数据结构课程设计--二叉排序树的实现[最终版]》由会员分享，可在线阅读，更多相关《数据结构课程设计--二叉排序树的实现[最终版]（14页珍藏版）》请在金锄头文库上搜索。
1、 .wd.实 验 报 告课程名称数据构造课程设计题目名称 二叉树的实现 学生学院应用数学学院 专业班级 14信安1班 学 号3114008224学生姓名 阮志敏 指导教师 刘志煌2016年12月9日二叉排序树的实现一、内容和要求。1) 编程实现二叉排序树，包括生成、插入、删除；2) 对二叉排序树进展先根、中根和后根非递归遍历；3) 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4) 分别用二叉排序树和数组去存储一个班50人以上的成员信息至少包括学号、姓名、成绩3项，比照查找效率，并说明在什么情况下二叉排序树效率高，为什么5) 格式按照作业的要求，对数据测试，分析，总结
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;/左儿子 SearchTree right;/右儿子
3、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 = insertTree
4、Node(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!n); else
5、 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(x =
7、tree-element) if(tree-left & tree-right) tmpNode = findMin(tree-right);/找出右子树中最小的 tree-element = tmpNode-element;/把右子树中最小的值给当前树节点 /把tree右子树中最小值的节点删除了,那个要删除的节点不可能有左儿子 tree-right = deleteTreeNode(tree-element,tree-right); else /只有一个子节点，或者没有子节点 tmpNode = tree; if(tree-left = NULL) /0个子节点也包含在内 tree = tr
8、ee-right; else if(tree-right = NULL) tree = 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. 对二叉排序
9、树进展先根、中根和后根非递归遍历1) 先根遍历先根遍历先访问根，再访问左儿子，接着访问右儿子。上图中的树，如果用先根遍历，顺序则是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入栈
11、，再把E入栈。这时，访问顺序为A-B-E-F-C，因此，我们可以用栈来作为循环遍历时的储存数据构造。此时，每轮循环的步骤就很清晰了：如果栈非空，出栈一个元素作为当前节点，先访问或者打印当前节点，接着，如果当前节点有左儿子或者右儿子，则先把右儿子入栈，再把左儿子入栈然后进入下次循环。如果当前节点没有儿子，则直接进入下次循环。具体代码如下：void preorderTraversal(Tree tree) Stack stack = createStack(10); push(tree,stack); while(!isStackEmpty(stack) TreePosition node = p
12、op(stack); printf(%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(tree = NULL) printf(the tree is NULL,cant traversaln); else pushLeftToStack(tree,stack); while(!isStackEmpty(stack)
