二叉搜索树中的最低公共祖先

如果所有元素都不同，它很容易在BST中找到最接近的共同祖先。但是如果某些值相同呢。到目前为止，我们只是比较节点的数据，就是这样，但现在我们需要检查节点的地址而不是数值吗？二叉搜索树中的最低公共祖先

2011-08-06 arvind.mohan

是的，而不是只使用您的key进行比较，请使用(key, address of node)进行比较。这在处理非唯一键时简化了代码。

2011-08-06 10:31:50 ybungalobill

没有看到你使用的是什么样的结构，就很难给具体，但你可以尝试这样的东西伪代码：

struct BST { 
    struct BST* parent; 
    struct BST* left; 
    struct BST* right; 
    void* value; 
} 

find_common_ancestor(struct BST* x, struct BST* y) 
{ 
    set<struct BST*> ancestors; 

    // Add all of x's ancestors to set. 
    while (true) { 
     ancestors.insert(x); 

     if (x == NULL) 
      break; 

     x = x=>parent; 
    } 

    // Check y's ancestors against x's until a match is found. 
    while (true) { 
     if (ancestors.count(y) > 0) 
      return y; 

     y = y->parent; 
    } 
}

来源

2011-08-06 10:41:08 Swiss

@ swiss：你没有给任何节点的父字段。如果父节点被赋予，那么BST的使用会是什么。：P –

@arvind mohan：没有什么能阻止BST实现从指向其父节点的指针。诚然，这在技术上并不需要，但它确实使某些事情更容易 - 就像你正在做的事情一样。即使你没有给出父指针，你也可以走树来创建一个包含x和y祖先的集合;你可以在while循环中使用它而不是父指针。 – Swiss

这里是psudocode。只是将它们转换成语法。

GETLeastCommonAn(BINARYTREE BT, NODE A, NODE B) 
IF Root==NIL 
    return NIL 
ENDIF 

IF Root==A OR root==B 
    return Root 
ENDIF 

Left = GETLCA (Root.Left, A, B) 
Right = GETLCA (Root.Right, A, B) 

IF Left! = NIL AND Right! = NIL 
    return root 
ELSEIF Left! = NIL 
    Return Left 
ELSE 
    Return Right 
ENDIF

来源

2014-09-05 06:17:27

二叉搜索树中的最低公共祖先

回答

相关问题