软设每日打卡——折半查找二叉判定树、平衡二叉树

对长度为n的有序顺序进行折半查找（即二分查找）的过程可用一颗判定树表该判定树的形态符合（ ）的特点。

A、最优二叉树（哈夫曼树）        B、平衡二叉树

C、完全二叉树                              D、最小生成树                                答案：B

解：        折半查找又称二分查找，要求表有序，即表中元素an关键字有序，而且必须顺序存储。

        折半查找可用一个称为判定树的二叉树描述（如题所述），判定树中的每一个结点对应表中的一个元素，但结点的值不是关键字的值，而是元素在表中的位置。

        题目只是在问折半查找的判定树的形态，那么这里我们主要需要记住的点是，折半查找判定树必为平衡树（平衡二叉树）。即由折半查找过程中所产生的树，首尾以二取整。

        那么为什么折半查找判定树一定是平衡二叉树？因为折半查找的过程是每次将查找区间折半，然后根据中间元素与查找值的大小关系确定下一步的查找区间，这个过程可以看作是在一颗二叉树上进行的。折半查找树是一种二叉搜索树，它的每个节点都满足左子树的所有节点的值都小于节点的值，右子树的所有节点的值都大于节点的值。（这句没太懂，我再研究一下）在折半查找树中，每个节点的左子树和右子树的高度差不超过1，因此它是一棵平衡二叉树。判定树是一种用于分析算法的数据结构，它用来表示算法在处理输入时所做的决策。对于折半查找算法，其判定树的每个节点表示一个比较操作，它的左子树和右子树分别比当前节点小和比当前节点大的元素。由于折半查找树是一颗平衡二叉树，因此它的判定树也一定是一颗平衡二叉树。

移到上方

        平衡二叉树是一种特殊的二叉树，它的左右子树高度差（简称平衡因子）的绝对值不超过1（即-1，0，1），这样可以保证树的高度不会太高，从而保证了树的查找效率。

平衡二叉树的两个条件：

        1、是二叉排序树

        2、任何一个节点的左子树或右子树都是平衡二叉树（左右高度差小于1）

横线复制

这里拓展一下这个判定树的画法，我看的这个博主的文：（这个电脑粘贴坏了，后续我补充）

满二叉树（Full Binary Tree）：

所有节点的度要么为0，要么为2，且所有的叶子节点都在最后一层。

不全的内容我后续补充