如果BST被翻转,我对inorder继承人/前任有轻微的困惑 . 当BST被翻转/反转时,我的意思是当右子树中的所有元素都较小并且左子树中的所有元素都较大时 . 通常,正确的子树具有更大的 Value . 如果它是相反的,那么inorder继承人/前任的定义是否仍然保持不变?
对于普通树,顺序继承者将是右子树的最左边的子项不是吗?
对于翻转的BST,如下例所示:
8
/\
15 4
/\ /\
20 10 6 2
8的继承人是10?或者,如果我们遵循顺序继承者的“通常”定义,那么它是6吗?
谢谢!
1 回答
如果您执行逆向BST的有序遍历,您将获得以 descending 顺序排序的数字 . 因此,在这种情况下,您的值的顺序将是:20,15,10,5,6,4,2 . So the successor of 8 will be 6 .