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检查它是否left在right. 如果是孩子，或者如果node被查询else，则与孩子一起递归。

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 回答