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

如果所有元素都不同，它很容易在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

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

回答

相關問題