在二叉樹中返回節點的父節點

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上。如果是孩子，或者被詢問的nodeelse，則向孩子遞歸。

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

這個輸出結果作爲樹中的每個節點對（父母，子女）的。

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

}