二进制排序tree.ppt的典型示例

二进制排序树动态查找表结构-二进制排序树（也称为二进制搜索树），以键值为节点的二进制树如果任何节点的左子树都不为空，则左子树所有节点的键代码in小于根节点的键码；如果任意一个节点的右子树不为空，则该右子树中所有节点的键码都大于根节点的键码. 二进制排序树结构BinSearchNode的存储结构（链类型）； typedef struct BinSearchNode * PBinSearchNode; struct BinSearchNode {KeyType键； / *关键代码值* / PBinSearchNode llink，rlink; / *二叉树的左右指针* /}; typedef struct BinSearchNode * BinSearchTree / *二进制排序树* / typedef BinSearchTree * PBinSearchTree;二进制排序树搜索在二进制排序树中查找节点的过程与二进制搜索类似，这也是逐渐缩小搜索范围的过程. if（node.value == key）foundelseif（key> node.value）binSearch（key构造二叉排序树，node.rightChild）; elsebinSearch（key，node.leftChild）;如果二进制排序树为空，则插入和构造二进制排序树，将新节点用作根节点.

如果二进制排序树不为空，则将新节点的密钥代码与根节点的密钥代码进行比较. 如果它们相等，则表示该节点已经在二进制排序树中；如果小于根节点的密钥，则将新节点插入到根节点的左子树中；否则，它将插入到正确的子树中. 子树中的插入过程与树中的插入过程相同，因此继续进行直到找到该节点，或者直到左或右子树是一个空的二叉树为止，然后将新节点插入到叶节点中. 删除二进制排序树为了删除二进制树中的节点，必须首先找到该节点，然后选择下面给出的两种方法将其删除，以确保删除后仍然满足二进制排序树的定义. 第一种方法: （1）如果删除的节点p没有左子树，则用p的右子代替换p. （2）否则，在p的左子树中找到具有最大键的节点r（r在p的左子树的右下角，r必须没有右子节点），并设置r Point的右指针到p的右孩子构造二叉排序树，并用p的左孩子替换p节点. Delete Key = 1018删除二进制排序树（续）第二种方法: 如果删除的节点p没有左子树，则用p的右子代替换p（与第一种方法相同）. 与第一种方法相同，找到最大的r节点，然后使用r节点替换已删除的节点p. p的原始左右子元素保持不变. 并将原始r节点替换为原始r的左子节点. Delete Key = 10 18最佳二进制排序树-将n个节点以不同顺序插入二进制排序树，您可能会得到n！二进制排序树.

最佳二进制排序树（续）在扩展的二进制排序树中，检索关键字的平均比较数为: 检索期间的平均比较数最小，即，具有最小E的二进制排序树（ n）最佳二进制排序树. 最佳二进制排序树的构造（1）首先对字典元素的键进行排序. （2）通过二分法对排序键序列中的每个键码进行搜索，并将在搜索中遇到的，尚未在二进制排序树中的键码插入到二进制排序树中. -根据二进制搜索中遇到的节点，依次插入二进制排序树. 例如，对于K = {27,73,10,5,18,41,99,51,25}，构造最佳​​二进制排序树的过程如下: 首先将它们排序为: 5、10、18， 25、27、41、51、73、99，然后从空的二叉树开始，使用二分法在排序的键序列中搜索5，在搜索中遇到的节点是27、10、5，插入这三个节点分成两个Fork排序树. 检索第二个节点10，遇到的节点为27,10. 二进制排序树中已经有两个节点. 检索第三个节点18，...的插入顺序为27、10、5、18、25、51、41、73、99.

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