algorithm - BST：-给定每个节点的中序后继，在O(h)中找到每个节点的父节点

Question

标题总结了它，我有一个包含节点的数组，它的顺序继承者我需要实现一个子程序来在 O(h) 中找到任何给定节点的父节点

不给左右指针

Answer 1

我不确定我是否正确理解了您的问题，BST 中的有序继任者仅仅意味着下一个更高的元素。现在提供此信息，可以创建多个 BST。例如 [{1,4},{2,1},{3,2},{5,3}] 这里 {a,b} 表示 a 是节点，b 是有序后继。所以树的一种可能实现是 4 IPO（读取是父级）1 和 NULL，1 IPO 2 和 NULL，2 IPO 3 和 NULL，最后是 3 IPO 5 和 NULL。由于您只需要遍历数组一次，因此可以在 O(n) 复杂度中找到此信息。