Closed yangCoder96 closed 3 years ago
请详述
一般情况下二叉查找树中不存在相同节点;对二叉查找树的定义应该是递归的,是一个节点的所有左子树的节点都小于该节点,而不是一个节点的左子节点小于该节点,这两种定义是不同的
感谢回复 (1) 我没找到有什么资料定义BST不可以有相同节点,wikipedia也根据允许和不允许分别给了搜索算法 (2) 下个版本会更正
具体的可以看看网上的定义,我是觉得作者这样的定义是不够严谨,存在一定问题的。 百度百科定义如下: 二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
若左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若右子树不空,则右子树上所有节点的值均大于它的根节点的值; 左、右子树也分别为二叉排序树; 没有键值相等的节点。
关于是否有键值相等节点这一说法,我也拿不准,有的说有,有的说没有。但是呢,作者书中的定义跟递归式定义是明显不同的
特意瞅了一眼百度百科,并不像你说的那样拿不准,其定义二和定义三都有说明。 维基百科英文定义: the key in each node is greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree 本书将以上述定义为准
个人觉得14.3中对二叉查找树的文字定义存在错误