题目来源于王道论坛下列二叉树中，可能成为折半查找判定_

推荐

zsw3

解析：

折半查找判定树实际上是一棵二叉排序树，它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素，符合折半查找规则的树即是所求。

B选项4、5相加除二向上取整，7、8相加除二向下取整，矛盾。C选项，3、4相加除二向上取整，6、7相加除二向下取整，矛盾。D选项，1、10相加除二向下取整，6、7相加除二向上取整，矛盾。A符合折半查找规则，正确。

发表于 2018-06-16 10:55:34 回复(19)

亮宇

折半查找树的特点就在于其中序遍历是一个升序序列，因此相比于在以往的序列中进行二分查找，折半查找二叉树的优点在于不用自己去找中点，而是直接将要查找的关键字与根节点相比，小的话再和根节点的左子节点（又是相应的左子树中点，很方便吧！！）比较，大的话则是和根节点的右子节点比较。

而对于这道题的解题思路就在于向上或向下取整的问题，也就是说如果升序序列是偶数个，那么中点应该偏左多右少还是左少右多。但是很显然应该进行一个统一，像B和C选项中间的对称部分明显就是选择了不同的策略。D则由根节点左子树4个节点而点右子树5个节点可以确定用的是向下取整策略，但是我们再看它的左子节点在左子树中对应的中点左边2个数，右边一个数，明显是向上取整策略，策略没有统一，所以是错的。我一般个人喜欢在升序序列中出现偶数个的情况下选左少右多的策略。奇数的话当然就没有这种烦恼啦

发表于 2018-09-07 17:42:52 回复(0)

Ephemeral_

抛砖引玉，恳请斧正。

一般的折半查找是向下取整。

在这里，我们不妨设折半查找是向上取整的，所以存在：

情况一：当剩余查找个数为偶数的时候，在树中表现为对应节点左边的子节点总数比右边子节点总数多一个。

情况二：当需要判断的节点还剩两个的时候，剩下的一个节点必须是用于比较的节点的左孩子。

图D根节点的左边有4个节点，右边却有5个节点，与情况一矛盾，排除。

图B和图C的第二层节点中存在只有右孩子的节点，与情况二矛盾，排除。

所以答案选A

编辑于 2018-07-23 09:48:28 回复(6)

表彰先进

看每个节点的左右子树个数，所有节点一致则正确，B的5左子树节点数大于右子树节点数，7却正好相反，矛盾，C中的4和6也一样矛盾，D中5的左子树4个节点，右子树5个，而任意一个其他的分支节点都是左子树节点数大于右子树，矛盾，只有A中所有分支节点的子树节点个数都是左边大于右边

发表于 2021-11-26 15:24:11 回复(0)

Fcq11

有谁和我一样没看懂题目的嘛

发表于 2020-02-27 14:41:28 回复(0)

北方华创微电子内推码IZBJ0J

折半查找树：统一策略，即要么所有结点的左子树结点个数都比右子树结点个数多（少），凡是出现不统一的现象统统为错。

发表于 2022-07-03 16:26:28 回复(0)

小木子201811092138657

就是看，mid =(left＋right）/2，向上取整，还是想下取整。

发表于 2020-03-27 19:14:40 回复(0)

haichuangxia

折半查找判定树,实质是一颗二叉排序树,构造判定树的过程是构造二叉排序树的过程,关键是根节点的选择要统一.

A:总共10个节点,根节点是6号,说明是是向上取整定根节点,其左子树根节点是3号,右子树根节点是3号,都是向上取整,同理可得,其余子树也都是向上取整确定根节点

B:共11个节点,根节点6号,左右子树根节点也是3号,居中,再往下看,发现3层和4层之间,左边两颗子树是向上取整,确定根节点,右边两颗子树是向下取整确定根节点,矛盾,故不为判定树

C:同理,根节点的左子树,共4个节点,根节点是2,向下取整,右子树根节点是3,向上取整,矛盾,非判定树

D:共10个节点,根节点是5,向下取整,左子树4个节点,根节点是3号节点,表明向上取整,矛盾,非判定树

发表于 2021-11-25 10:27:51 回复(0)

煩透了

新人发帖，如有错误还请斧正。首先，折半查找判定树的特性是：其左右子树结点数之差只能为0或1（查找元素个数为奇数时是0，为偶数时是1）。若采用除2后向下取整则右子树比左子树结点数多1（或相等），若向上取整则结果相反。要注意的是，在整棵判定树，其中任意一层中，两颗对称的左右子树都要满足上述条件，且整棵判定树只能采用其中一种策略（向上取整或向下取整）。了解特性后，再来看题目。在图B中以第三层结点为根的子树，左边子树的左子树比右子树多一个结点，但右边子树的左子树比右子树少一个结点，与上述所说特性矛盾。图C情况类似。图D中以第二层为根结点的两颗子树，左边比右边少一个结点，但这两颗树的子树都是左边子树结点比右边子树多，所以矛盾。综上，只有图A完全满足特性，其采用的是向上取整的策略。叙述如有错误，请多多包涵指教。

发表于 2022-04-11 21:54:39 回复(0)

TIL

不能死背某些结论。这题就代表了折半查找判定书可以向上也可以向下取整（不然A就直接错了不是吗）。根据根节点判断是向上还是向下取整，画出折半查找判定树就是了，一下就画出来了。

发表于 2019-11-18 21:42:23 回复(0)

哇咔咔咔咔嗷嗷

# 二叉树判断是否为折半查找树

## 题目

<img src="https://gitee.com/BearBrick0/images/raw/master/img/image-20220226125027883.png" alt="image-20220226125027883" style="zoom:50%;" />

网上有好多教程，看的我很头大。经过朋友的讲解，豁然顿悟。废话不说。

要做对这道题，首先就是先要搞懂折半查找树是怎样的构建的过程，折半查找，顾名思义，就是通过一次次的折半，来构建树，小的放左边，大的放右边。

构建树，肯定要先有根节点。没有问题吧。所以说先要折半。折半的还有问题，要么正好是中点，要么需要向上取整或者向下取整。

这时候，你就会发现了，只能存在两种情况，要么**取中点和向上取整**，**要么取中点和向下取整**，这是为什么呢？因为我们数据有偶数和奇数之分的吧。明白了吧。

看图，很懵，所以来点数据，没有问题吧。那数据要谁？要多少呢？接下来，我们看选项，A选项，不要真看，你要数。是不1个根节点，左边有5个节点，右边有四个。总共10个节点。其他的自己数！B总共11，C总共9，D总共10。要多少我们解决了，给谁呢？

对就1，2，3，4，5，6，7，8，9，10，11。

来看A：

- 1，2，3，4，5，6，7，8，9，10

- 先找根节点，折半，就会发现中点有两个，5和6，那选哪一种，我先胡说一下，大多数都选6，叫向下取整。为什么呢？因为我一直都是这样做。没有毛病吧。
- 接下来，把6当作根节点，是不左边就剩 [1，2，3，4，5] 右边 [7,8,9,10]。没有问题吧。脑子里边要有树！没有的话栽个树。
- 接下来你就重复折半，不要忘记大小顺序！

![](https://img2022.cnblogs.com/blog/2260953/202202/2260953-20220226143833984-1194439078.png)

然后你在看选项，是不答案就出来了。这个办法有点慢，你可以看左右子树。
- A 左5 右4
- B 左5 右5
- C 左4 右4
- D 左4 右5
一般有个规律，左子树节点多于右子树的，就是符合折半搜索树的。

发表于 2022-02-26 14:46:02 回复(2)