二叉排序树_wx619474981d7fe的技术博客_51CTO博客

1 二叉排序树的定义

果查找的数据集是有序线性表，并且是顺序存储的，查找可以用折半查找算法来实现，因为有序，在插入和删除操作上，就需要耗费大量的时间。

假设现在我们的数据只有一个数{62,88,58,47,35,73,51,99,37,93}做查找，建立好的二叉排序树如图所示，62、88、58创建好后，下一个数47因比58小，是它的左子树，35是47的左子树，73比62大，但比88小，是88的左子树，51比62小，比58小，比47大，是47的右子树；99比62、88都大，是88的右子树，37比62、58、47小，但却比35大，是35的右子树，93比62、88大是99的左子树。

二叉排序树，又称为二叉查找树。它或是一棵空树，或者是具有下列性质的二叉树。

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
它的左右子树也分别为二叉排序树。

构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在—个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

二叉排序树的结点结构定义：

/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode /* 结点结构 */
{
int data; /* 结点数据 */
struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
} BiTNode, *BiTree;

2 二叉排序树的插入

二叉排序树插入操作源码：

/* 当二叉排序树T中不存在关键字等于key的数据元素时， */
/* 插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key)
{
BiTree p,s;
if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
if (!p)
*T = s; /* 插入s为新的根结点 */
else if (key<p->data)
p->lchild = s; /* 插入s为左孩子 */
else
p->rchild = s; /* 插入s为右孩子 */
return TRUE;
}
else
return FALSE; /* 树中已有关键字相同的结点，不再插入 */
}

二叉排序树的构建：

int i;
int a[10]={62,88,58,47,35,73,51,99,37,93};
BiTree T=NULL;

for(i=0;i<10;i++)
{
InsertBST(&T, a[i]);
}

二叉排序树的查询操作：

/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
if (!T) /* 查找不成功 */
{
*p = f;
return FALSE;
}
else if (key==T->data) /* 查找成功 */
{
*p = T;
return TRUE;
}
else if (key<T->data)
return SearchBST(T->lchild, key, T, p); /* 在左子树中继续查找 */
else
return SearchBST(T->rchild, key, T, p); /* 在右子树中继续查找 */
}

查询算法执行流程：

第7-11行，是用来判断当前二叉树是否到叶子结点，当前为根结点，T不为空，第9-10行不执行。
第12-16行是查找到相匹配关键字时执行的语句，显然，第14行和第15行不执行。
第17行、18行是当要查找的关键字大于当前结点值时执行的语句，所以递归调用。此时T指向了62的右孩子88。
此时是第二层的，因93比88大，所以执行第20行，再次递归调用，此时T指向了88的右孩子99，如图所示。

5.第三层的，因93比99小，执行第18行，递归调用。此时T指向99的左孩子93，如图所示。

第四层的，因key等于，执行第14行和第15行，此时指针p指向93所在的结点，并返回True到第三层、第二层、第一层，最终函数返回True。

3 二叉排序树总结

二叉排序树以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树中的层数。二叉排序树的结构是不确定的，有可能会出现右下图的情况。

1 二叉排序树的定义

2 二叉排序树的插入

3 二叉排序树总结

Recommend

二叉排序树的建立

BP神经网络_wx619474981d7fe的技术博客_51CTO博客

数据结构01绪论_wx619474981d7fe的技术博客_51CTO博客

数据结构02算法_wx619474981d7fe的技术博客_51CTO博客

数据结构03顺序表_wx619474981d7fe的技术博客_51CTO博客

数据结构04链表_wx619474981d7fe的技术博客_51CTO博客

二叉树练习题_萌新的日常的技术博客_51CTO博客

有序查找及顺序查找_wx619474981d7fe的技术博客_51CTO博客

数据结构重点知识汇总_wx619474981d7fe的技术博客_51CTO博客

堆排序+TOPK问题_萌新的日常的技术博客_51CTO博客

About Joyk