1

任意のノードの親を返すコードを書いていますが、行き詰まっています。事前定義されたADTを使用したくありません。

//Assume that nodes are represented by numbers from 1...n where 1=root and even 
//nos.=left child and odd nos=right child.
public int parent(Node node){
    if (node % 2 == 0){
       if (root.left==node)
       return root;
    else
       return parent(root.left);
    }
    //same case for right
}

しかし、このプログラムは機能しておらず、間違った結果をもたらしています。私の基本的なアルゴリズムは、プログラムがオンかオンかをrootチェックすることから開始することです。それが子供である場合、またはそれが照会された場合は、子供と一緒にそれを繰り返します。leftrightnodeelse

4

2 に答える 2

2

これは、二分木をトラバースして、指定されたノードの親であるノードを見つけると言い換えることができます。

あなたが持っていると仮定します

class Node {
  int node;
  Node left;
  Node right;

  Node(int node, Node left, Node right) {
    this.node = node;
    this.left = left;
    this.right = right;
  }
  @Override
  public String toString (){
     return "("+node+")";
  }
}

簡単にするために、グローバル変数を定義します。

Node root;
int target;
boolean found;

それらは次のメソッドによってアクセスされます。まず、メソッド呼び出しを初期化します

public Node findParent(int target){
  found = false;
  this.target = target;
  return internalFindParent(root, null);
}

次に、実装を書きます

private Node internalFindParent(Node node, Node parent){
  if (found) return parent;
  if (node.node == target) {
    found = true;
    return parent;
  }
  if (node.left == null) return null;
  Node temp = internalFindParent(node.left, node);
  if(temp != null)
    return temp;
  if (node.right == null) return null;
  temp = internalFindParent(node.right, node);
  if(temp != null)
    return temp;
  return null;
}

このメソッドはツリーをトラバースし、指定されたノードが見つかった場合はすぐに結果を返します。それがどのように機能するかを示すために、サンプル ツリーを作成し、それをrootノードに割り当てます。ターゲットとして使用される一意の番号を使用して、各ノードに番号を付けます。

public void init() {
  root = new Node (0,
    new Node(1,
      new Node (2,
        new Node (3,
          new Node (4, null, null),
          new Node (5, null, null)
        ),
        new Node (6,
          new Node (7, null, null),
          new Node (8, null, null)
        )
      ),
      new Node (9,
        new Node (10,
          new Node (11, null, null),
          new Node (12, null, null)
        ),
        new Node (13,
          new Node (14, null, null),
          new Node (15, null, null)
        )
      )
     ),
    new Node(21,
      new Node (22,
        new Node (23,
          new Node (24, null, null),
          new Node (25, null, null)
        ),
        new Node (26,
          new Node (27, null, null),
          new Node (28, null, null)
        )
      ),
      new Node (29,
        new Node (30,
          new Node (31, null, null),
          new Node (32, null, null)
        ),
        new Node (33,
          new Node (34, null, null),
          new Node (35, null, null)
        )
      )
    )
  );
}

簡単にするために、コンストラクターですべてのテストを実行するだけです

FindingParent(){
  init();
  for (int i=0; i<=35; i++){
    Node parent = findParent(i);
    if (parent != null)
      System.out.println("("+parent.node+", "+i+")");
  }

}
/**
 * @param args
 */
public static void main(String[] args) {
  new FindingParent();
  System.exit(0);
}

この出力は、ツリー内の各ノードの (親、子) のペアとして生成されます。

于 2012-09-11T14:45:33.057 に答える
2

これを試してみてください。うまくいくかもしれません：

public BinaryTreeNode getParent(BinaryTreeNode root, BinaryTreeNode node) {

    BinaryTreeNode lh = null, rh = null;
    if (null == root)
        return null;

    if (root.getLeft() == node || root.getRight() == node)
        return root;

    lh = getParent(root.getLeft(), node);
    rh = getParent(root.getRight(), node);

    return lh != null ? lh : rh;

}
于 2014-01-22T07:54:39.293 に答える