数据结构-动态查找表-二进制排序树

二进制排序树是具有以下属性的空树或二进制树:

（1）如果其左子树不为空，则左子树中所有节点的值小于其根节点的值;

（2）如果右子树不为空，则右子树中所有节点的值都大于其根节点的值；

（3）其左和右子树都是二进制排序树.

下图显示了两个二进制排序树:

二叉排序树也称为二叉搜索树，您可以看到二叉树的性质: 其搜索过程类似于次优二叉树，即当二叉排序树不为空时，给定值和根节点的关键字比较. 如果它们相等，则搜索成功. 否则，将根据给定值和根节点关键字之间的大小关系在左侧或右侧子树上继续搜索.

通过顺序输入数据元素并将其插入到二叉树的适当位置来实现二叉树的构建.

特定过程: 每次读取元素时，都会创建一个新节点. 如果二进制排序树不为空，则将新节点的根节点与该值进行比较. 如果小于根节点的值，则将其插入左子树中；否则，将其插入右子树中；否则，将其插入子树中. 如果二进制排序树为空，则将新节点视为二进制排序树的根节点.

由于二进制排序树是递归的，因此子树的插入过程与树中的插入过程相同，因此您可以编写一个递归过程.

二进制排序树的形式完全由输入序列确定. 通过构建二进制排序树，可以将无序序列转换为有序序列. 如果输入顺序为10/25/28/40/52/80，则对应的二进制排序树为单个分支树，如图所示:

从二进制排序树的构造过程中可以看出，插入的每个新节点都是二进制排序树的叶节点. 在插入过程中不需要移动其他元素，只需更改某个节点的指针即可. 空可以更改为非空，因此二进制排序树结构适合频繁插入元素.

删除树中的节点，您不能删除以更改后的节点为根的自述文件. 该函数将删除该节点，并仍然确保二进制排序树的特性二叉排序树 构造，即删除二进制树上的一个节点等效于删除序列中的一个一元素.

因为二进制排序树可以看作是一个有序列表二叉排序树 构造，所以二进制排序树的左子树中所有节点的关键字都小于根节点的关键字，而右子树中所有节点的关键字都小于大于或等于关键字等于根节点，二叉树中的所有搜索都类似于二分之一的搜索.

搜索过程: 如果二进制排序树不为空，则将给定值与根节点进行比较，如果相等，则搜索成功；如果不是，则当根节点大于给定值时，转到根目录的左侧子节点Look in the tree，否则转到根目录的右侧子树. 显然，这仍然是一个递归过程.

在二进制排序树中查找其键等于给定值的节点的过程将采用从根节点到该节点的路径. 与给定值相比较的关键字数量等于路径长度+ 1.

在最坏的情况下，二进制排序树变成单个分支树. 在最好的情况下，排序树是相对统一的.

二进制排序树的性能与二进制搜索没有太大区别，但是二进制排序树对于节点的插入和删除非常方便，并且经常被搜索和删除.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-184094-1.html