二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:
①若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
②若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质(BST性质),故二叉排序树实际上是满足BST性质的二叉树。
下面就是二叉排序树的插入、删除、查找算法。
#include <iostream>
using namespace std;
typedef struct {
unsigned int key1;
unsigned int key2;
}KeyType;
typedef struct
{
// somethings user define ;
}BSTNode;
typedef struct
{
KeyType key;
BSTNode node;
}BSTree;
int compkey(KeyType x,KeyType y)
{
int ret ;
if((x.key1 == y.key1) && (x.ke2 == y.key2))
ret = 0;
else
if((x.key1 > y.key1) || (x.key1 == y.key1) && (x.key2 > y.key2) )
ret = 1;
else
ret =-1;
}
void InsertBST(BSTree *Tptr,KeyType key)
{
//若二叉排序树 *Tptr中没有关键字为key,则插入,否则直接返回
BSTNode *f,*p=*TPtr; //p的初值指向根结点
while(p)
{
//查找插入位置
//树中已有key,无须插入
if(compkey(p->key,key) == 0)return;
f=p; //f保存当前查找的结点
p=(compkey(key,p->key)<0 ? p->lchild:p->rchild; //若key<p->key,则在左子树中查找,否则在右子树中查找
} //endwhile
//生成新结点
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key.key1 = key.key1;
p->key.key2 = key.key2;
p->lchild = p->rchild=NULL;
//原树为空
if(*TPtr==NULL)
*Tptr=p;
else
if(compkey(key,f->key)<0)
f->lchild=p;
else f->rchild=p;
} //InsertBST
/**************************************************************************
②删除*p结点的三种情况
(1)*p是叶子(即它的孩子数为0)
无须连接*p的子树,只需将*p的双亲*parent中指向*p的指针域置空即可。
(2)*p只有一个孩子*child
只需将*child和*p的双亲直接连接后,即可删去*p。
注意:
*p既可能是*parent的左孩子也可能是其右孩子,而*child可能是*p的左孩子或
右孩子,故共有4种状态。
(3)*p有两个孩子
先令q=p,将被删结点的地址保存在q中;然后找*q的中序后继*p,并在查找过程
中仍用parent记住*p的双亲位置。*q的中序后继*p一定是 *q的右子树中最左下的结
点,它无左子树。因此,可以将删去*q的操作转换为删去的*p的操作,即在释放结
点*p之前将其数据复制到*q中,就相当于删去了*q.
***************************************************************************/
void DelBSTNode(BSTree *Tptr,KeyType key)
{
//在二叉排序树*Tptr中删去关键字为key的结点
BSTNode *parent=NULL,*p=*Tptr,*q,*child;
while(p)
{
//从根开始查找关键字为key的待删结点
if(compkey(p->key,key) == 0) break;//已找到,跳出查找循环
parent=p; //parent指向*p的双亲
p=(compkey(key , p->key)<0)? p->lchild:p->rchild;
//在关p的左或右子树中继续找
}
if(!p) return; //找不到被删结点则返回
q=p; //q记住被删结点*p
//*q的两个孩子均非空,故找*q的中序后继*p
if(q->lchild && q->rchild)
for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);
//现在情况(3)已被转换为情况(2),而情况(1)相当于是情况(2)中rchild=NULL的状况
child=(p->lchild)? p->lchild:p->rchild;
//若是情况(2),则child非空;否则child为空
if(!parent) //*p的双亲为空,说明*p为根,删*p后应修改根指针
*Tptr=child;
else //若是情况(1),则删去*p后,树为空;否则child变为根
{ //*p不是根,将*p的孩子和*p的双亲进行连接,*p从树上被摘下
if(p==parent->lchild) //*p是双亲的左孩子
parent->lchild=child;
else parent->rchild=child; //*child作为*parent的左孩子
//*child作为 parent的右孩子
if(p!=q) //是情况(3),需将*p的数据复制到*q
{
q->key.key1=p->key.key1;
q->key.key2=p->key.key2;
}
//若还有其它数据域亦需复制
} //endif
free(p); //释放*p占用的空间
} //DelBSTNode
BSTNode *SearchBST(BSTree T,KeyType key)
{ //在二叉排序树T上查找关键字为key的结点,成功时返回该结点位置,否则返回NUll
if(T==NULL || (compkey(key,T->key)==0)) //递归的终结条件
return T;//T为空,查找失败;否则成功,返回找到的结点位置
if(compkey(key,T->key)<0)
return SearchBST(T->lchild,key);
else
return SearchBST(T->rchild,key);//继续在右子树中查找
} //SearchBST
此处有非递归版本
http://www.cnblogs.com/ljphhj/archive/2012/02/25/2367821.html
相关推荐
/*用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
掌握二叉排序树的存储方法,实现二叉排序树的创建、查找、插入、删除、平均查找长度等基本操作。 三、实验内容及要求 1、构造二叉排序树的存储结构。 2、实现创建、查找、插入、删除、平均查找长度等操作。
用函数实现如下二叉排序树算法:(1) 插入新结点(2) 前序、中序、后序遍历二叉树(3) 中序遍历的非递归算法(4) 层次遍历二叉树(5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) Input 第一行:准备...
写一算法,判断一棵二叉树是否是一棵二叉排序树。
二叉排序树的实现 二叉排序补充概念(也可以参考书上第九章第二节) 左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,简单一点,二叉排序树左边的数据小于右边. 1)编程实现二叉排序树, 包括生成、...
二叉树的构造,插入,排序,我们对数据进行存储时候的构造。
数据结构中的二叉排序树实现算法,C语言~~~~~~~~~~~~
代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树,二叉排序树查找递归算法,二叉排序树查找非递归算法
二叉排序树插入
第一个程序:实现将两个二叉排序树合并为一个二叉排序树的算法; 第二个程序:N个人围成一圈,从第一个人开始计数,凡是数到1,2,4,8,也就是2的N次方的退出圈子。编写程序,把这些人退出的顺序输出,要求用链表。
用二叉链表作存储结构,编写程序实现二叉排序树上的基本操作:以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T......
SCAU数据结构的综合实验报告 实现二叉排序树的各种算法 因为里面有源程序和报告文档,所以压缩成一个rar文件,只需要解压后即可使用。 包括: 实验的源代码 根据代码写出来的实验报告
一、实验目的 (1)理解动态查找表的动态生成过程; (2)任意给出一组数(不少于10个),建立对应二叉排序树;...(2)实现二叉排序树的插入算法与查找算法,并建立二叉排序树; (3)进行数据查找和建树过程的比较。
用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
C++编写的查找算法,用二叉排序树查找,是在VC++6.0上实现的
二叉排序树算法在闪存数据管理中的应用,刘德伟,,本文给出了一种在嵌入式设备的闪存中实现用户数据管理的方法,不但使每次修改都擦除较少的扇区,而且保证了在修改闪存中数据时突
二叉排序树的创建、删除、插入等操作
(5)设计算法将(1)中所得的二叉排序树的左右子树进行交换,由于二叉树是一种递归定义, 所以子树的左右两棵子树也要相交换,依此类推。最后输出所得到的二叉树的中序遍历序列。 例如,经过上述操作后,(1)中...
输入:待排序数据序列 功能要求:输出平衡的二叉排序树的形态或输出二叉树的三种遍历序列
平衡二叉排序树的算法实现