二叉排序树的实现

精品文档---下载后可任意编辑实 验 报 告课程名称数据结构课程设计题目名称二叉树的实现学生学院应用数学学院 专业班级 14 信安 1 班 学 号 3114008224学生姓名 阮志敏 指导老师刘志煌2024 年 12 月 9 日精品文档---下载后可任意编辑二叉排序树的实现一、内容和要求。1)编程实现二叉排序树，包括生成、插入、删除；2)对二叉排序树进行先根、中根和后根非递归遍历；3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4)分别用二叉排序树和数组去存储一个班（50 人以上）的成员信息（至少包括学号、姓名、成绩 3 项），对比查找效率，并说明在什么情况下二叉排序树效率高，为什么？5)格式根据作业的要求，对数据测试，分析，总结和改进的工作要做详细一点。二、解决方案和关键代码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;//右儿子 int leght;//节点的深度，用于打印 int position;//节点的位置，用于打印};2)实现插入和生成二叉树节点的方法。在这里用到了递归插入的方法。SearchTree insertTreeNode(TreeElementType x,SearchTree tree){ if(tree == NULL) { tree = makeTree(x,NULL,NULL);//插入在该处 }else if(x < tree->element) { tree->left = insertTreeNode(x,tree->left); }else if(x > tree->element) { tree->right = insertTreeNode(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 { node->element = x; node->left = left; node->right = right; } return node;}3)实现二叉树节点删除的方法。删除节点时有 3 种情况：情况一：被删除的节点同时含有...