UC知道二叉排序树的应用
来源：百度知道 编辑：UC知道 时间：2024/06/20 06:01:45
编写一个程序用来统计一个文本中各种字符出现的次数，再对各字符的ASCII码进行排序，建立一棵二叉排序树(注意：二叉排序树中无相同的数据元素)，然后按照字符大小依次输出字符信息(包括字符本身和出现次数)。 要求：(1) 输出该二叉排序树的先序、中序和后序遍历。
(2) 可以按照用户的要求查询某字符的出现次数。
(二)设计思想
首先从文件中一边读字符，一边按其大小将其插入到二叉排序树中，当所有字符插入完毕，二叉排序树即建立完成。然后对二叉排序树进行中序遍历，便可按字符大小输出及其出现次数，对于用户要求查询特定字符的出现次数，可在二叉排序树中进行查找，找到后输出。
(三)字符信息的存储结构定义：
typedef struct node
{char val; /*存储字符*/
int count; /*存储字符出现次数*/
struct node *lchild,*rchild; /*指向左、右孩子指针*/
}bitnode, *bittree;
(四)参考程序
#include "stdio.h"
#include "malloc.h"
typedef struct node
{char val; /*存储字符*/
int count; /*存储字符出现次数*/
struct node *lchild,*rchild; /*指向左、右孩子指针*/
}bitnode, *bintree;
bintree creatbintree(bintree t,char ch)
{ bitnode *ptr,*p;
p=NULL;
ptr=t;
while(ptr!=NULL)
if(ch==ptr->val)
{ptr->count++;
return t;
}
el
树的应用：二叉排序树
排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来，形成一个线性有序的序列。二叉排序树是利用二叉树的结构特点来实现对元素排序的。
一、二叉排序树的定义
二叉排序树或者是空树，或者是具有如下性质的二叉树：
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指向根结点的二叉排