二叉排序树的应用

树的应用，求代码，建立一个二叉排序树，具体要求如下，真心求解各位，时间紧迫。~

这个做起来可真要花的时间，二叉排序树其实我也研究了一段时间，感觉比较难，我在网上找了一段代码。你自己去研究一下吧，要学习，还是自己动手比较好：
#include
#include
#include
struct node {
int value;
struct node* left;
struct node* right;
};
typedef struct node NODE;
typedef struct node* PNODE;
PNODE creat( PNODE tree,PNODE r,int value)
{
if(!r)
{
r = (PNODE)malloc(sizeof(NODE));
if(!r)
{
printf("内存分配失败！");
exit(0);
}

r->left = NULL;
r->right = NULL;
r->value = value;
if(!tree)
return r;
if(valuevalue)
tree->left = r;
else
tree->right = r;
return r;
}

if(value value)
creat(r,r->left,value);
else
creat(r,r->right,value);
return tree;
}
void new_node (PNODE* n, int value)
{
*n = (PNODE)malloc (sizeof(NODE));
if (*n != NULL)
{
(*n)->value = value;
(*n)->left = NULL;
(*n)->right = NULL;
}
}
void free_node (PNODE* n)
{
if ((*n) != NULL)
{
free (*n);
*n = NULL;
}
} /* 查找结点 */


PNODE find_node (PNODE n, int value)
{
if (n == NULL)
{
return NULL;
}
else if (n->value == value)
{
return n;
}
else if (value value)
{
return find_node (n->left, value);
}
else
{
return find_node (n->right, value);
}
} /* 插入结点 */
void insert_node (PNODE* n, int value)
{
if (*n == NULL)
{
new_node (n, value);
}
else if (value == (*n)->value)
{
return;
}
else if (value value)
{
insert_node (&((*n)->left), value);
}
else
{
insert_node (&((*n)->right), value);
}
} /* 删除结点 */
void deletenode (PNODE *n)
{
PNODE tmp = NULL;

if (n == NULL)
return;

if ((*n)->right == NULL)
{
tmp = *n;
*n = (*n)->left;
free_node (n);
}
else if ((*n)->left == NULL)
{
tmp = *n;
*n = (*n)->right;
free_node (n);
}
else
{
for (tmp = (*n)->right; tmp->left != NULL; tmp = tmp->left);
tmp->left = (*n)->left;
mp = (*n);
*n = (*n)->right;
free_node (&tmp);
}
}
void delete_node (PNODE *n, int value)
{
PNODE node;
if (n == NULL)
return;

node = find_node (*n, value);

if ((*n)->value == value)
{
deletenode (n);
}
else if (value value)
{
delete_node (&((*n)->left), value);
}
else
{
delete_node(&((*n)->right), value);
}
}
void pre_order_traversal(PNODE n) /* 前序遍历 */
{
if (n != NULL)
{
printf ("%i ", n->value);
pre_order_traversal (n->left);
pre_order_traversal( n->right);
}
}
void in_order_traversal (PNODE n) /* 中序遍历 */
{
if (n != NULL)
{
in_order_traversal (n->left);
printf ("%i ", n->value);
in_order_traversal ( n->right);
}
}
void post_order_traversal (PNODE n) /* 后序遍历 */
{
if (n != NULL)
{
post_order_traversal (n->left);
post_order_traversal (n->right);
printf ("%i ", n->value);
}
}
int get_num_nodes (PNODE n) /* 计算树的节点数 */
{
int left = 0;
int right = 0;
if (n == NULL)
{
return 0;
}
if (n->left != NULL)
{
left = get_num_nodes (n->left);
}
if (n->right != NULL)
{
right = get_num_nodes (n->right);
}
return (left + 1 + right);
}
int main()
{
char buf[50];
int i,n,option,s[80];
PNODE tree = NULL;/*树的第一个结点*/
PNODE node = NULL;
while (1)
{
printf ("--------------------------
");
printf ("Options are:

");
printf (" 0 Creat tree
");
printf (" 1 Insert node
");
printf (" 2 Delete node
");
printf (" 3 Find node
");
printf (" 4 Pre order traversal
"); /* 前序遍历 */
printf (" 5 In order traversal
"); /* 中序遍历 */
printf (" 6 Post order traversal
");/* 后序遍历 */
printf (" 7 Node Count
");
printf (" 8 Exit

");
printf ("--------------------------
");
printf ("Select an option: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("--------------------------
");
if (option 12)
{
fprintf (stderr, "Invalid option");
continue;
}
switch (option)
{
case 0:
printf ("Enter number of elements of array: ");
scanf("%d",&n);
printf ("Enter %d elements of array:
",n);
for(i=0;i<n;i++)
{
scanf("%d",&s[i]);
tree = creat(tree,tree,s[i]);
}
fflush(stdin);
break;
case 1:
printf ("Enter number to insert: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("

");
insert_node (&tree, option);
break;
case 2:
printf ("Enter number to delete: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("

");
delete_node (&tree, option);
break;
case 3:
printf ("Enter number to find: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("

");
node = find_node (tree, option);
if (node != NULL)
{
printf ("Found node

");
}
else
{
printf ("There is no node which you input!

");
}
break;
case 4:
printf ("Pre order traversal: ");
pre_order_traversal (tree);
printf ("

");
break;
case 5:
printf ("In order traversal: ");
in_order_traversal (tree);
printf ("

");
break;
case 6:
printf ("Post order traversal: ");
post_order_traversal (tree);
printf ("

");
break;
case 7:
printf ("Node Count is %i

", get_num_nodes (tree));
break;
case 8:
exit (0);
}
}
return 0;
}

二叉树二叉树能够说是人们假想的一个模型，因此，允许有空的二叉树是无争议的。二叉树是有序的，左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定，是因为人们赋予了左孩子和右孩子不同的意义，在二叉树的各种应用中，您将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书，您会发现一个有趣的现象：在二叉树这里，基本操作有计算树高、各种遍历，就是没有插入、删除——那树是怎么建立起来的？其实这很好理解，对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应用中，才会有插入删除操作。节点结构 数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲，或是资源紧张，建议附加一个双亲指针，这将会给很多算法带来方便，尤其是在这个“空间换时间”的时代。

二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值

• 若右子树不空，则右字数上所有节点的值均大于它的根节点的值
  

• 它的左、右子树也分别为二叉排序数（递归定义）
  

从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree）


所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）

当用线性表作为表的组织形式时，可以有三种查找法。其中以二分查找效率最高。但由于二分查找要求表中结点按关键字有序，且不能用链表作存储结构，因此，当表的插入或删除操作频繁时，为维护表的有序性，势必要移动表中很多结点。这种由移动结点引起的额外时间开销，就会抵消二分查找的优点。也就是说，二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找，可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。不妨将它们统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方法。

二叉排序树

1、二叉排序树的定义
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。

2、二叉排序树的特点
由BST性质可得：
（1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。
（2） 二叉排序树中，各结点关键字是惟一的。
注意：
实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的"小于"改为"大于等于"，或将BST性质(2)里的"大于"改为"小于等于"，甚至可同时修改这两个性质。
（3） 按中序遍历该树所得到的中序序列是一个递增有序序列。
【例】下图所示的两棵树均是二叉排序树，它们的中序序列均为有序序列：2，3，4，5，7，8。

3、二叉排序树的存储结构
typedef int KeyType； //假定关键字类型为整数
typedef struct node { //结点类型
KeyType key； //关键字项
InfoType otherinfo； //其它数据域，InfoType视应用情况而定，下面不处理它
struct node *lchild，*rchild； //左右孩子指针
} BSTNode；
typedef BSTNode *BSTree； //BSTree是二叉排序树的类型

---

惠安县13213229969： 二叉树在计算机科学与技术中的应用有哪些 - ？
乔残小建： 霍夫曼编码:这是一种数据压缩方法,利用一棵霍夫曼树(本质为二叉树)来压缩一组数据.优先级队列:它使用一棵二叉树来记录集合中元素的优先级,并将其排序,为解决问题提供更好的方案.事件调度:主要使用二叉搜索树,这能够使得查找信息更加高效.数据库系统:主要使用B树,这能够使插入和删除操作更加高效.用户界面:在图形用户界面中,窗口按树形结构组织,如windows系统.文件系统:文件按树形结构组织,如windows系统.人工智能:比如棋类这种逻辑类的游戏,可以把步骤生成决策树.以上如果需要详细了解,可直接百度相关名词.

惠安县13213229969： 二叉判定树和二叉排序树有什么区别? - ？
乔残小建： 二叉判定树神判大是用来分析某个算法而设计的二叉树,如:可以用来分析折半查找的过程,分析几个游竖数字的比较过程等;而二叉排序树是用来对一组关冲物键字进行排序的方法.

惠安县13213229969： 谁能给我讲讲二叉树的应用?？
乔残小建： 线索: n 个结点的二叉链表中含有 n+1 个空指针域.利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针,这种附加的指针称为 ＂ 线索 ＂ . 线索链表: 加上了线索的二叉链表称为线索链表,相应的二叉树称...

惠安县13213229969： 利用二叉排序树对顺序表进行排序 (1)生成一个顺序表L;(2)对所生成的顺序表L构造二叉排序树(3)利用栈结构实现中序遍历二叉排序树;(4)中序遍历所构造的二叉排序树将记录由小到大输出. - ？
乔残小建： #include <stdio.h>#include <stdlib.h>#include <iostream.h> struct tree//声明树的结构 { struct tree *left,*right; int data; }; typedef struct tree treenode;//声明新类型树结构 typedef treenode *b_tree;//声明二叉树链表 //插入二叉树节点 b_tree insert_...

惠安县13213229969： 利用二叉排序树排序 - ？
乔残小建： 本二叉树创建规则, 小于当前节点的数插入当前节点的左子树,大于当前节点的插入右子树,依次类推直到找到对应的节点. 打印62616964757a686964616fe58685e5aeb931333238653862的时候,通过递归的方法调用遍历函数,按照先左子...

惠安县13213229969： 什么是二叉排序树? - ？
乔残小建： 二叉排序树(Binary Sort Tree)又称二叉查找树. 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树 http://baike.baidu.com/view/647462.htm

惠安县13213229969： C语言 二叉树的应用,跪求高手. - ？
乔残小建： 二叉树的前序、中序、后序遍历 #include<malloc.h> // malloc()等 #include<stdio.h> // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等 #include<stdlib.h> // atoi(),exit() #include<math.h> // 数学函数头文件,包括floor(),ceil(),abs()等#define ...

惠安县13213229969： 二叉树的遍历及应用 - ？
乔残小建： 你需要设个全局变量.当if(ch=='.') 时退出所有的CreateBiTree递归函数,而不仅仅是当前的函数.

惠安县13213229969： 二叉排序树的构造和查找方法 - ？
乔残小建： 二叉排序树的构造过程:按照给定序列,以此将结点插入二叉排序树中,在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义. 插入过程:若二叉排序树为空,则待插入结点*S作为根结点插入到空树中; 当非空时,...

惠安县13213229969： 二叉排序树的操作？
乔残小建：实验目的】 由读入数据构造二叉排序树,并进行插入,查找,删除操作. 【设计原理】 二叉排序树:或者是一棵空树,或者是具有下列性质的二叉树: 1. 若它的左子树不空,则右子树上所有结点的值均大于它的根结点的值 2. 若它的右子树不...