バイナリ検索ツリー内の最も低い共通祖先

Question

すべての要素が異なる場合、BSTで最も近い共通祖先を見つけるのはかなり簡単です。しかし、値のいくつかが同じであればどうでしょうか。これまではノードのデータを比較していましたが、それはそれでしたが、値の代わりにノードのアドレスをチェックする必要がありますか？

Answer 1

はい、代わりにkeyを使用する代わりに、比較のために(key, address of node)を使用してください。これにより、一意でないキーを扱うときにコードが単純化されます。

Answer 2

使用している構造体の種類を見ることなく、それは詳細を与えるのは難しいですが、あなたは、この擬似コードのような何かを試みることができる：ここ

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; 
    } 
} 

Answer 3

を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