二叉排序树的实现doc下载

数据结构课程设计二叉排序树的实现课程名称:数据结构设计题目:二叉排序树的实现院系:学生姓名:学号:班级:指导教师:年月日课程设计任务书设计题目二叉排序树的实现计算机科学与姓名罗浩院系、年级、班软件工程班信息工程系设计要求:a)以回车('n')为输入结束标志,输入数列L生成一棵二叉排序树Tb)对二叉排序树T作中序遍历输出结果c)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作)否则输出信息“无x”学生应完成的工作:、按设计要求完成各项任务。、测试数据及测试结果在上交的资料中写明必须上机调试通过。、按《数据结构课程设计大纲》中的要求完成课程设计报告格式。、设计结束后上交如下材料:)《课程设计报告》打印稿一份)课程设计的源代码电子文档一份参考文献阅读:李春葆尹为民李蓉蓉蒋晶鈺喻丹丹数据结构教程上机实验指导谭浩强C程序设计教程唐宁九游洪跃朱宏数据结构与算法(C版)工作计划:共计一周时间进度安排如下:(选题在上机实验之前看透设计要求翻阅资料完成程序设计大致提纲。(选好题上级编写程序(需求分析、概要设计)。(填写算法实现设计要求的各项功能(详细设计)。调试和分析最终完成较合理的程序设计。

}不难分析，上述算法的时间复杂度同样为 o(n) 7．6．3 二叉树的线索化算法对--x 树的线索化，就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程， 因此， 二叉树的线索化过程只能在对二叉树的遍历过程中进行。如果二叉树需要经常遍历或查找结点是需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。4 树：树和森林的概念及其表示，二叉树，二叉树性质，二叉树表示，二叉树遍历与树游标， lvr, lrv, vlr，中序游标，按层次遍历，满足性问题，线索二叉树，线索，中序遍历线索二叉树，将结点插入线索二叉树，选择树，胜者树，败者树，森林的二叉树表示及遍历，集合表示，并查集，在等价类问题中的应用。

该设计运用数据结构知识利用C编写来锻炼和提高我自己的编程及独立解决问题的能力故选较为基础但知识点广泛的题目。任务与分析任务是一个二叉排序树的实现问题根据任一数列生成一棵二叉排序树实现基本的遍历方法查询结点并删除结点且保证仍为二叉排序树。根据二叉排序树的概念查找当前插入的元素的位置删除结点如果不是叶子结点要注意考虑如何使树仍为二叉排序树。设计方案整体设计方案此课题研究二叉排序树的实现建立二叉排序树中序遍历并显示遍历结果输入元素x,查找x若存在删除之否则输出“无x”然后再进行中序遍历输出遍历结果。为方便起见画出流程图如图:主程序模块中序遍历二叉排中序遍历二叉排查找元素x初始化模块BSTSearch()CreateBST()序树inorder()序树inorder()图该程图描述了主要程序及函数。方案实施主程序模块设计方案#includetypedefintKeyTypetypedefcharElemTypetypedefstructtnode{KeyTypekeyElemTypedatastructtnode*lchild,*rchild}BSTNode定义全局变量、分配储存空间。初始化模块设计方案)实现二叉树的初始化BSTNode*CreatBST(KeyTypeA,intn)由数组中的关键字建立一棵二叉排序树{BSTNode*bt=初始时bt为空树inti=while(ikey==k)return()f=p*f指向*p结点的双亲结点*if(p>key>k)p=p>lchild*在左子树中查找*elsep=p>rchild*在右子树中查找*}p=newBSTNode*建立新结点*p>key=kp>lchild=p>rchild=if(bt==)*原树为空时,*p作为根结点插入*bt=pelseif(kkey)f>lchild=p*插入*p作为*f的左孩子*elsef>rchild=p*插入*p作为*f的右孩子*return()}voidCreateBST(BSTNode*bt,KeyTypestr,intn){bt=*初始时bt为空树*inti=while(ilchild)cout

用链式存储结构来表示二叉树，一个结点至少由3个域组成，即数据域、左子结点域和右子结点域（如图1所示）。 其中，结点的 lchild 域和 rchild 域已分别填有指向其左、右孩子结点的指针，而 parent域中的值为空指针(拟作为指向双亲结点的指针域)。假若s,p,q是连续三个结点的指针，若我们要在p前插入一个新结点r，则只需把s的右链域指针指向r数据结构二叉排序树，r的左链域指针指向s，r的右链域指针指向p，p的左链域指针指向r即可。

4．译码的思想是循环读入一串哈夫曼序列，读到“0”从根结点的左孩子继续读，读到“1”从右孩子继续，如果读到一个结点的左孩子和右孩子是否都为0，如果是说明已经读到了一个叶子（字符），翻译一个字符成功，把该叶子结点代表的字符存在一个存储翻译字符的数组中，然后继续从根结点开始读数据结构二叉排序树，直到读完这串哈夫曼序列，遇到结束符便退出翻译循环。 供选择的答案： a：①是特殊的树②不是树的特殊形式③是两棵树的总称④是只有二个根结点的树形结构 b：①左子结点②右子结点③左子结点或者没有右子结点 ④兄弟 c～d： ①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟e：①o(n)②o(n)③o(log2n)④o(log2n) 15、每一棵树都能唯一地转换为它所对应的二叉树，树的这种二叉树表示对树的运算带来很大的好处。二分查找法： 定义一个数组a，首先查找的数与数组a的中位数比较，若小，则取中位数左半部分，（若大，则取中位数右半部分），在去左半部分的中位数依次比较重复此步骤，直至找到，否则当左界low>右界high，则输出无。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-118313-1.html