java 返回二叉树中节点的父节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12342131/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Return parent of node in Binary Tree
提问by user188995
I'm writing a code to return the parent of any node, but I'm getting stuck. I don't want to use any predefined ADTs.
我正在编写一个代码来返回任何节点的父节点，但我被卡住了。我不想使用任何预定义的 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
}
But this program is not working and giving wrong results. My basic algorithm is that the program starts from the rootchecks if it is on leftor on the right. If it's the child or if the nodethat was queried else, recurses it with the child.
但是这个程序不起作用并且给出了错误的结果。我的基本算法是，该方案从开始root检查，如果它是在left上或right。如果是孩子或者node是被查询的else，则与孩子一起递归。
回答by Roman C
This could be rephrased as traverse a binary tree to find a node that is parent to the given one.
这可以重新表述为遍历二叉树以找到给定节点的父节点。
Suppose you have a
假设你有一个
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+")";
}
}
For simplicity we will just define global variables.
为简单起见，我们将只定义全局变量。
Node root;
int target;
boolean found;
They will be accessed by the next methods. First, we initialize a method call
它们将被下一个方法访问。首先，我们初始化一个方法调用
public Node findParent(int target){
found = false;
this.target = target;
return internalFindParent(root, null);
}
Second, we write an implementation
其次，我们写一个实现
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;
}
This method traverses a tree and returns results immediately if the given node is found. To demonstrate how it's worked we should create a sample tree and assign it to rootnode. We numerate each node with the unique number used as a target.
如果找到给定节点，则此方法遍历一棵树并立即返回结果。为了演示它是如何工作的，我们应该创建一个示例树并将其分配给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)
)
)
)
);
}
Just do all tests in the constructor for simplicity
为简单起见，只需在构造函数中进行所有测试
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);
}
This output results as pairs of (parent, child) for each node in the tree.
此输出结果为树中每个节点的（父、子）对。
回答by user3159447
Try this .It may work :
试试这个。它可能有效：
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;
}
