1.2.1编程实现二叉排序树，包括生成、插入，删除； 1.2.2对二叉排序树进行先根、中根、和后根非递归遍历； 1.2.3每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 1.2.4分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?

课程设计里用到了二叉排序树相关知识，并且附带课程设计报告和心得体会（大约共5000字）

攀枝花学院本科学生课程设计任务书 题　目 二叉排序树与平衡二叉树的实现 1、课程设计的目的 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。 3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等） (1) (1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T； (2)对二叉排序树T作中序遍历，输出结果； (3)计算二叉排序树T查

二叉排序树查找插入建立.cpp

本人用JAVA写的二叉排序树，有二叉树插入节点、删除节点、修改节点等操作，其中还写了一个字符串比较（字母模式比较，数值模式比较）另外不附有源码

给定一棵无穷的满二叉排序树，结点的编号是 1，2，3，4，…，即该二叉排序树的中序遍历序 列是从 1 开始的递增有序序列。如下图所示。 对于树中一棵根结点的编号为 X 的子树来说，沿着 X 的左孩子结点，以及左孩子结点的左孩子 结点，一路向左直至到达最后一层，可以获得以 X 为根的树中编号最小的结点；若沿着 X 的右孩子 结点，以及右孩子结点的右孩子结点，一路向右直至到达最后一层，可以获得以 X 为根的树中编号 最大的结点。 现在的问题是，在一棵根为 X 的子树中，结点的最小编号和最大编号分别是什么？ 要求输入一个整数 X，表示一棵子树的根结点的编号，输出以 X 为根的树中结点的最小编号和 最大编号。 例如： 若输入： 8 则输出： 1 15 若输入： 12 则输出： 9 15

设二叉排序树的二叉链表存储结构的类型定义如下： typedef struct node{ int data; //用整数表示一个结点的名 struct node *LChild,*RChild; //左右指针域 }BSTNode,*BSTree; 设计算法并编写程序求解以下几个问题。 8 12 14 10 7 3 15 6 2 4 1 5 11 9 13 16 13 （1）键盘输入一个元素序列创建一棵二叉排序树，输出该二叉排序树的中序遍历序列； 例如，若输入 45,24,55,12,37,53,60,23,40,70 则创建的二叉排序树为： 输出结果为：12 23 24 37 40 45 53 55 60 70 （2）在（1）中所得的二叉排序树中插入一个值为 58 的结点，再输出它的中序遍历序列，输出 结果为：12 23 24 37 40 45 53 55 58 60 70 （3）在（1）中所得的二叉排序树中删除值为 45 的结点，再输出它的中序遍历序列，输出结果 为：12 23 24 37 40 53 55 58 60 70 （4）利用（1）中所得的二叉排序树的所有叶子结点构造一个带头结点的单链表 L。要求不能 破坏这棵二叉排序树。所得的单链表 L 如下。 输出该链表各结点的值，输出结果为：23 40 53 70 （5）设计算法将（1）中所得的二叉排序树的左右子树进行交换，由于二叉树是一种递归定义， 所以子树的左右两棵子树也要相交换，依此类推。最后输出所得到的二叉树的中序遍历序列。 例如，经过上述操作后，（1）中所得的二叉排序树变为如下形式。 输出该二叉树的中序序列，结果为：70 60 55 53 45 40 37 24 23 12 （6）设计算法统计并输出（1）中所得的二叉排序树中只有一个孩子结点的结点个数。输出结 果为：3（7）在（1）中所得的二叉排序树中，设计算法并编写程序输出结点 40 的所有祖先结点。输 出结果为：45 24 37

二叉排序树模板类c++

包括代码和课程设计报告。 摘要……………………………………………………………………………………………1 1 引言…………………………………………………………………………………………2 1.1 问题的提出………………………………………………………………………………2 1.2 C语言……………………………………………………………………………………2 1.3 C语言的发展过程………………………………………………………………………2 1.4 任务与分析………………………………………………………………………………2 2设计方案……………………………………………………………………………………3 2.1整体设计方案……………………………………………………………………………3 2.1.1主程序模块设计方案…………………………………………………………………3 2.1.2初始化模块设计方案…………………………………………………………………3 2.1.3中序遍历模块设计方案………………………………………………………………5 2.1.4先序遍历模块设计方案………………………………………………………………5 2.1.5查找并删除元素模块设计方案………………………………………………………6 2.1.6主函数模块设计方案…………………………………………………………………7 3程序演示……………………………………………………………………………………9 总结…………………………………………………………………………………………10 致谢…………………………………………………………………………………………11 参考文献……………………………………………………………………………………12 附录…………………………………………………………………………………………13

１本程序在vc++6.0编译通过并能正常运行。 ２主界面 程序已经尽量做到操作简便了，用户只需要根据提示一步步进行操作就行了。 六思考和总结： 这个课程设计的各个基本操作大部分都在我的综合性实验中实现了，所以做这个主要攻克插入和删除这两个算法！其中插入在书本上已经有了，其中的右平衡算法虽然没有给出，但通过给出的左平衡算法很容易就可以写出右平衡算法。所以最终的点就在于删除算法的实现！做的过程中对插入算法进行了非常非常多次的尝试！花了非常多的时间，这其中很多时候是在对程序进行单步调试，运用了ＶＣ６。０的众多良好工具，也学到了很多它的许多好的调试手段。 其中删除算法中最难想到的一点是：在用叶子结点代替要删除的非叶子结点后，应该递归的运用删除算法去删除叶子结点！这就是整个算法的核心，其中很强烈得体会到的递归的强大，递归的最高境界（我暂时能看到的境界）！ 其它的都没什么了。选做的那两个算法很容易实现的： １合并两棵平衡二叉排序树：只需遍历其中的一棵，将它的每一个元素插入到另一棵即可。 ２拆分两棵平衡二叉排序树：只需以根结点为中心，左子树独立为一棵，右子树独立为一棵，最后将根插入到左子树或右子树即可。 BSTreeEmpty(BSTree T) 初始条件：平衡二叉排序树存在。 操作结果：若T为空平衡二叉排序树，则返回TRUE,否则FALSE. BSTreeDepth(BSTree T) 初始条件：平衡二叉排序树存在。 操作结果：返回T的深度。 LeafNum(BSTree T) 求叶子结点数，非递归中序遍历 NodeNum(BSTree T) 求结点数，非递归中序遍历 DestoryBSTree(BSTree *T) 后序遍历销毁平衡二叉排序树T R_Rotate(BSTree *p) 对以*p为根的平衡二叉排序树作右旋处理，处理之后p指向新的树根结点 即旋转处理之前的左子树的根结点 L_Rotate(BSTree *p) 对以*p为根的平衡二叉排序树作左旋处理，处理之后p指向新的树根结点， 即旋转处理之前的右子树的根结点 LeftBalance(BSTree *T) 对以指针Ｔ所指结点为根的平衡二叉排序树作左平衡旋转处理， 本算法结束时，指针Ｔ指向新的根结点 RightBalance(BSTree *T) 对以指针Ｔ所指结点为根的平衡二叉排序树作右平衡旋转处理， 本算法结束时，指针Ｔ指向新的根结点 Insert_AVL(BSTree *T, TElemType e, int *taller) 若在平衡的二叉排序树Ｔ中不存在和e有相同的关键字的结点， 则插入一个数据元素为e的新结点，并返回OK,否则返回ERROR. 若因插入而使二叉排序树失去平衡，则作平衡旋转处理 布尔变量taller反映Ｔ长高与否 InOrderTraverse(BSTree T) 递归中序遍历输出平衡二叉排序树 SearchBST(BSTree T, TElemType e, BSTree *f, BSTree *p) 在根指针Ｔ所指的平衡二叉排序树中递归的查找其元素值等于e的数据元素， 若查找成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p 指向查找路径上访问的最后一个结点并返回FALSE，指针f指向Ｔ的双亲， 其初始调用值为NULL Delete_AVL(BSTree *T, TElemType e, int *shorter) 在平衡二叉排序树中删除元素值为e的结点,成功返回OK,失败返回ERROR PrintBSTree_GList(BSTree T) 以广义表形式打印出来 PrintBSTree_AoList(BSTree T, int length) 以凹入表形式打印,length初始值为0 Combine_Two_AVL(BSTree *T1, BSTree T2) 合并两棵平衡二叉排序树 Split_AVL(BSTree T, BSTree *T1, BSTree *T2) 拆分两棵平衡二叉树 } (2)存储结构的定义： typedef struct BSTNode { TElemType data; int bf; //结点的平衡因子 struct BSTNode *lchild, *rchild;//左.右孩子指针 }BSTNode, *BSTree;