Question

数据结构里，什么是二叉判定树？

看书上提到了，但是不知道是什么意思。

Answer 1

二叉判定树也叫二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树。

扩展资料：

查找

步骤：

二叉树

若根结点的关键字值等于查找的关键字，成功。

否则，若小于根结点的关键字值，递归查左子树。

若大于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

平均情况分析（在成功查找两种的情况下）：

在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6

注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数。

参考资料来源：百度百科-二叉排序树

Answer 2

树中每个节点表示表中的一个记录，节点里的值为该记录在表中的位置，通常称这个查找过程的二叉树为二叉判定树。

二叉判定树的节点是各个元素的下标或在表中的位置。比如有一个文件【11,22,33,44,55,66】，我想查找44是否在该文件中，利用折半查找的思想，可以将此文件构造成一个二叉判定树。

根节点是3，注意二叉判定树的节点是下标或位置，这里不能写33。

Answer 3

描述查找过程的一种二叉排序树

Answer 4

什么叫二叉树的度？带你了解它的特点

Answer 5