实验报告课程名称数据结构课程设计题目名称二叉树的实现学生学院应用数学学院专业班级14信安1班学号3114008224学生姓名阮志敏指导教师刘志煌2016年12月9日二叉排序树的实现一、内容和要求。编程实现二叉排序树，包括生成、插入、删除；对二叉排序树进行先根、中根和后根非递归遍历；每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。分别用二叉排序树和数组去存储一个班（50人以上）的成员信息（至少包括学号、姓名、成绩3项），对比查找效率，并说明在什么情况下二叉排序树效率高，为什么？格式按照作业的要求，对数据测试，分析，总结和改进的工作要做详细一点。解决方案和关键代码1.二叉排序树的实现。首先定义二叉树的结构体，代码如下：structTreeNode;typedefstructTreeNode*TreePosition;typedefstructTreeNode*SearchTree;typedefstructTreeNode*Tree;typedefintTreeElementType;structTreeNode{//二叉树TreeElementTypeelement;//节点中的元素SearchTreeleft;//左儿子SearchTreeright;//右儿子intleght;//节点的深度，用于打印intposition;//节点的位置，用于打印};实现插入和生成二叉树节点的方法。在这里用到了递归插入的方法。SearchTreeinsertTreeNode(TreeElementTypex,SearchTreetree){if(tree==NULL){tree=makeTree(x,NULL,NULL);//插入在该处}elseif(x<tree->element){tree->left=insertTreeNode(x,tree->left);}elseif(x>tree->element){tree->right=insertTreeNode(x,tree->right);}//如果相等，什么也不做returntree;}当tree==NULL时，就是递归终止的条件，也是插入该节点的地方，在这里，用makeTree()方法创建一个节点，其代码如下：staticSearchTreemakeTree(TreeElementTypex,SearchTreeleft,SearchTreeright){SearchTreenode=(SearchTree)malloc(sizeof(structTreeNode));if(node==NULL){printf("makeTreeNodefail!\n");}else{node->element=x;node->left=left;node->right=right;}returnnode;}实现二叉树节点删除的方法。删除节点时有3种情况：情况一：被删除的节点同时含有左儿子和右儿子。在这种情况下，必须找出一个合适的节点来替代被删除的节点。由于二叉树的特性，被删除节点右子树中的节点都比左子树节点大，因此，可以替代原节点的节点必然在被删除节点的右子树中，并且是右子树的最小节点。所以，在这种情况下，应该把被删除节点的右子树中最小节点替代被删除节点。情况二：被删除节点只有一个子节点。显然，应该把它的子节点替代它。情况三：被删除节点没有子节点。此时，直接删除它。具体代码如下,同样使用递归删除的方法：SearchTreedeleteTreeNode(TreeElementTypex,SearchTreetree){TreePositiontmpNode;if(tree==NULL){//到叶节点了，还没找到可以删除的printf("notfound!\n");}elseif(x<tree->element){tree->left=deleteTreeNode(x,tree->left);}elseif(x>tree->element){tree->right=deleteTreeNode(x,tree->right);}elseif(x==tree->element){if(tree->left&&tree->right){tmpNode=findMin(tree->right);//找出右子树中最小的tree->element=tmpNode->element;//把右子树中最小的值给当前树>节点//把tree右子树中最小值的节点删除了,那个要删除的节点不可能有左>儿子tree->right=deleteTreeNode