java - 返回二叉树中节点的父节点

Question

我正在编写代码以返回任何节点的父节点，但我遇到了困难。我不想使用任何预定义的 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，则将其与子节点一起递归。

Answer 1

这可以改写为遍历二叉树以找到给定树的父节点。

假设你有一个

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

此输出结果为树中每个节点的(父，子)对。