数据结构学习第四弹 二叉排序树
2016-10-02 本文已影响84人
Richie_ll
二叉排序树又称为二叉搜索树或二叉查找树，这是一种插入、删除和检索记录效率都很高的树结构
二叉排序树概念
二叉排序树，由名字可以看出他也是一颗二叉树，所以描述时和二叉树很相似。
二叉排序树有如下性质：
- 若其左子树不为空，则左子树上所有结点的值均小于根结点的值
- 若其右子树不为空，则右子树上所有节点的值均大于根结点的值
- 左右子树也为二叉排序树
按照这样的性质描述来看，用中序遍历来遍历二叉排序树可以得到一个有序的序列。一般而言二叉排序树采用二叉链存储结构，描述如下：
typedef int KeyType;
typedef struct node
{
KeyType data;
struct node *leftChile;
struct node *rightChild;
}BSTNode, *BiTree;
二叉排序树的基本运算
- BSTSearch(bt,k)： 在二叉排序树bt中，查找值为k的结点
- BSTInsert(bt,k): 在二叉排序树bt中，插入值为k的结点
- CreatBST(bt,arr,n): 创建二叉排序树
- DispBST（bt）: 输出二叉排序树
- BSTDelete(bt,k): 删除结点
查找结点
查找方法：将给定的k值与根结点进行比较，若相等则查找成功，否则：
- 当k值小于根结点时，查找在左子树进行下去
- 当k值大于根结点时，查找在右子树进行下去
- 当查找成功则返回，否则一致查找到子树为空为止
BSTNode* BSTSearch(BSTNode *bt,KeyType k)
{
BSTNode* p = bt;
while(p!=NULL && p->data!=k)
{
if(k>p->data) //沿着右子树查找
p = p->rightChild;
else if(k<data) //沿着左子树查找
p = p->leftChile;
}
return p;
}
插入结点
每一个新加入的结点作为叶子结点加入到二叉排序树当中
void BSTInsert(BSTree &bt,KeyType k)
{
//为新结点申请空间
BSTree p = bt;
p = (BSTree)malloc(sizeof(BSTNode));
p->data = k;
p->leftChild = NULL;
p->rightChild = NULL;
//查找二叉排序树
//若原本的树为空，则设为根结点
if(bt==NULL)
bt=p;
else
{
//在已有的二叉排序树中查找找到合适的位置插入
if(bt->data >= k)
{
if(bt->leftChild == NULL)
bt->leftChild = p;
else
BSTInsert(bt->leftChild,k);
}
else
{
if(bt->rightChild == NULL)
bt->rightChild = p;
else
BSTInsert(bt->rightChild,k);
}
}
}
二叉排序树的建立
二叉排序树的建立其实就是把每一个元素插入到
void CreateBST(BSTree &bt,KeyType str[],int n)
{
bt = NULL;
for(int i=0;i<n;i++)
BSTInsert(bt,str[i]);
}
二叉排序树的输出
其实二叉排序树的输出就是对二叉树的遍历，根据二叉排序树的性质可以知道
中序遍历的结构就是一个有序的数列
void DispBST(BSTNode *bt)
{
if(bt==NULL)
return ;
DispBST(bt->leftChild);
printf("%d ",bt->data);
DispBST(bt->rightChild);
}
二叉排序树是一种动态的数据结构，它的运算大都是基于查找运算的，查找的次数与树的深度（层数）有关，这样，有n个结点的二叉排序树的平均查找长度就和树的形态有关。如果形态接近或为完全二叉树，则平均查找次数的数量级为log2n，如果给出的n个关键字是有序的，那么建立的二叉排序树就是一棵单枝树，这样的查找长度就为（n+1）/2，不过已知是有序的关键字的话，为什么不用二分查找呢......
