二叉排序树的实现_二叉排序树实验报告_二叉排序树的构造过程

树的应用：二叉排序树排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来，形成一个线性有序的序列。二叉排序树的实现二叉排序树是利用二叉树的结构特点来实现对元素排序的。一、二叉排序树的定义二叉排序树或者是空树，或者是具有如下性质的二叉树： 1、左子树上所有结点的数据值均小于根结点的数据值； 2、右子树上所有结点的数据值均大于或等于根结点的数据值； 3、左子树、右子树本身又各是一棵二叉排序树。由此可见，二叉排序树是一种特殊结构的二叉树。（18（10（3，15（12，15）），21（20，21（，37））））就是一棵二叉排序树。思考题1：试将上述括号表示法表示的二叉排序树用图形表示法表示出来。图 思考题2：试用中序遍历二叉树的方法写出遍历二叉排序树的结果，并思考二叉排序树究竟有什么作用？。二、二叉排序树的构造二叉排序树的构造过程实质上就是排序的过程，它是二叉排序树作媒介，将一个任意的数据序列变成一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是： 1、以待排序的数据的第一个数据构成根结点； 2、对以后的各个数据，逐个插入结点，而且规定：在插入过程的每一步，原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。

思考题3：试根据上述构造二叉排序树的思路，画出待排序数据（50，54，71，23，48，55，79，32，21）的二叉排序树图。总结：构造二叉排序树的算法思想如下：设A={a1,a2,...,an}为一组元素的集合， 1、令a1为二叉排序树的根； 2、在保持二叉排序树性质的前提下，依次把a2,a3,...,an插入到该树中。二叉排序树的生成算法： Procedure createbst(Var t:pointer);{构造一棵以t指向根结点的二叉排序树，插入数据以‘#’结束}Begin t:=nil;{初始化} read(x); {输入元素值x} while (x'#') dobeginnew(s);s^.Lc:=nil;s^.Rc:=nil;s^.data:=x;insertnode(s,t);read(x)end;end.其中，插入一个结点的算法insertnode(s，t)如下： Procedure insertnode(s:pointer;Var t:pointer);{s指向待插入结点，t是bst的根}Begin if t=nil then t:=s else if s^.data

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