排序二叉树二叉排序树实现1） 编程实现二叉排序树，包括生成、插入，删除

二叉排序树（急啊）

当用线性表作为表的组织形式时，可以有三种查找法。

其中以二分查找效率最高。

但由于二分查找要求表中结点按关键字有序，且不能用链表作存储结构，因此，当表的插入或删除操作频繁时，为维护表的有序性，势必要移动表中很多结点。

这种由移动结点引起的额外时间开销，就会抵消二分查找的优点。

也就是说，二分查找只适用于静态查找表。

若要对动态查找表进行高效率的查找，可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。

不妨将它们统称为树表。

下面将分别讨论在这些树表上进行查找和修改操作的方法。

二叉排序树 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是二叉排序树的类型

C语言 排序二叉树

#include?<stdio.h> #include?<stdlib.h> struct?node{ int?data; struct?node?*lc,*rc; }*head,*s; //-----必须传递二维指针才能改变实参指针变量的值！！ void?find(struct?node?**p,struct?node?*x){ if((*p)==NULL)? *p=x; else?if(x->data<=?(*p)->data) find(?&((*p)->lc),x); else? find(?&((*p)->rc),x); } void?print(struct?node?*p){ if(p!=NULL){ print(p->lc); printf("%d?",p->data); print(p->rc); } } int?main?(){ FILE?*fin=fopen("排序二叉树.txt","r"); int?a; while(!feof(fin)){ fscanf(fin,"%d",&a); s=(struct?node?*)malloc(sizeof(struct?node));//-- s->data=a; s->lc=s->rc=NULL?;//-- find(?&head,s);//-- } print(head); fclose(fin); system("pause"); return?0; }

二叉排序树实现1） 编程实现二叉排序树，包括生成、插入，删除

#include <stdio.h> struct node { int data; struct node *lchild; struct node *rchild; }； typedef struct node NODE; （1）递归函数 NODE *search(t, x) NODE *t; char x; { if (t==NULL) return(NULL); else { if (t->data==x) return(t); if (x<t->data) return(search(t->lchild)); else return(search(t->rchild)); } } （2）非递归函数 用非递归实现查找，程序同样很简单，但效率比递归程序高的多。

NODE *search(NODE *t, char x) { NODE *p; p=t; while (p!=NULL) { if (p->data==x) return(p); /* 查找成功 */ if (x<p->data) p=p->lchild; else p=p->rchlid; } printf(“找不到值为%x的结点！”，x); return (NULL); /* 查找失败 */ void insert(t, s) NODE **t, *s { if (*t==NULL) *t=s; else { if (s->data<(*t)->data) insert(&((*t)->lchild),s); else if (s->data>(*t)->data) insert(&((*t)->rchild),s); else printf(" 数据%d已在二叉排序树中！", s->data); } } void creat(t) NODE **t { int x; NODE *s; printf(" 输入待排序的数据序列（以-1结束）："); scanf("%d",&x); while (x!=-1) /* 以-1结束输入 */ { s=(NODE *)malloc(sizeof(NODE)); s->data=x; s->lchild=NULL; s->rchild=NULL; insert(t,s); /* 插入到二叉排序树中 */ scanf("%d",&x); } } main( ) { NODE *root=NULL; printf(" 创建一棵二叉排序树！"); creat(&root); printf("二叉排序树中序序列为："); midorder(root); } } void delete(NODE **t,int x) { NODE *f,*p,*r; p=(*t); /* p指向数据域值为x的结点 */ f=NULL; /* f指向p所指的结点的父结点 */ while (p!=NULL&&p->data!=x) /* 查找数据域值为x的结点 */ if (x<p->data) { f=p; p=p->lchild; } else { f=p; p=p->rchild; } if (p==NULL) printf("找不到键值为 %d的结点 ",x); else if (p->lchild==NULL) /* 被删除结点无左子树 */ { if (f==NULL) (*t)=p->rchild; /* 被删除结点为根结点 */ else if (f->lchild==p) f->lchild=p->rchild; /* 被删除结点为其父结点的左子树*/ else f->rchild=p->rchild; /* 被删除结点为其父结点的右子树*/ } else /* 被删除结点有左子树 */ { r=p->lchild; while (r->rchild!=NULL) /* 找到最右e68a84e8a2ad62616964757a686964616f31333337623535边的结点 */ r=r->rchild; r->rchild=p->rchild; /* 把被删除结点的右子树作为r的右子树 */ if (f==NULL) (*t)=p->lchild; /* 被删除结点为根结点 */ else if (f->lchild==p) f->lchild=p->lchild; /* 被删除结点为其父结点的左子树*/ else f->rchild=p->lchild; /* 被删除结点为其父结点的右子树*/ } free(p)