Java 在二叉树中查找节点的父节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/23856618/
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
Finding the parent of a node in a Binary tree
提问by sam_rox
I am trying to write a method to find the parent of a given node. Here's my method.
I created a BinaryNodeobject r which initially refers to root.
我正在尝试编写一种方法来查找给定节点的父节点。这是我的方法。
我创建了一个BinaryNode对象 r，它最初是指根。
public BinaryNode r=root;
public BinaryNode parent(BinaryNode p){
BinaryNode findParent=p;
if (isRoot(findParent) || r==null){
return null;
}
else{
if(r.left==findParent || r.right==findParent)
return r;
else{
if (r.element<findParent.element)
return parent(r.right);
else
return parent(r.left);
}
}
}
THis code doesn't work properly .I think that's because r is a null object.Because when I do
这段代码不能正常工作。我认为那是因为 r 是一个空对象。因为当我这样做时
if (isRoot(findParent) || r==null){
System.out.println(r==null);
return null;}
r==nullevaluates to true.How come that happen because I have inserted nodes as
r==null评估为 .true为什么会发生这种情况，因为我已将节点插入为
public static void main (String args[]){
BinaryTree t=new BinaryTree();
t.insert(5);
t.insert(t.root,4);
t.insert(t.root,6);
t.insert(t.root,60);
t.insert(t.root,25);
t.insert(t.root,10);
and the root is not null.
Can some one please point out why that happens and if what I am trying to do in order to find the parent node is logically correct.
并且根不为空。
有人可以指出为什么会发生这种情况，以及我为了找到父节点而尝试做的事情在逻辑上是否正确。
采纳答案by wastl
The problem is that you MUST keep track of your current node, while keeping the node who's parent you want to find. And as far as I understand your code, you keep the variable, but never change it
I'd recommend using a helper function. This would look something like that:
问题是您必须跟踪当前节点，同时保留要查找的父节点。据我了解您的代码，您保留变量，但永远不要更改它，
我建议使用辅助函数。这看起来像这样：
public BinaryNode parent(BinaryNode p){
parentHelper(root,p)
}
private BinaryNode parentHelper(BinaryNode currentRoot, BinaryNode p) {
if (isRoot(p) || currentRoot==null){
return null;
}
else{
if(currentRoot.left==p || currentRoot.right==p)
return currentRoot;
else {
if (currentRoot.element<p.element) {
return parentHelper(currentRoot.right,p);
}
else {
return parentHelper(currentRoot.left,p);
}
}
}
}
回答by peq
Use two parameters: One for the current node and one for the node being searched.
使用两个参数：一个用于当前节点，一个用于正在搜索的节点。
回答by Puneeth Reddy V
Here is code to find out parent node using a stack Data Structures.
这是使用堆栈数据结构找出父节点的代码。
Stack<TreeNode> parentStack = new Stack<TreeNode>();
public static void inOrderTraversal(TreeNode root){
if(root != null){
if(parentStack.size()==0){
parentStack.push(root);
}
if(root.getLeftChild()!=null){
parentStack.push(root);
inOrderTraversal(root.getLeftChild());
}
parent = parentStack.pop();
System.out.println(root.getNodeValue()+"'s parent is "+parent.getNodeValue());
if(root.getRightChild()!=null){
parentStack.push(root);
inOrderTraversal(root.getRightChild());
}
}
else{
if(root==null){System.err.println("Can't process a empty root tree");}
}
}
回答by Aerin
I compared value to value because I didn't define the way to compare the nodes.
我将值与值进行了比较，因为我没有定义比较节点的方式。
public static Node FindParent(Node root, Node node)
{
if (root == null || node == null)
{
return null;
}
else if ( (root.Right != null && root.Right.Value == node.Value) || (root.Left != null && root.Left.Value == node.Value))
{
return root;
}
else
{
Node found = FindParent(root.Right, node);
if (found == null)
{
found = FindParent(root.Left, node);
}
return found;
}
}
回答by Kaal
I prefer to delegate as much work as I can to lower-level components, in this case the Node class. Re: finding a node's parent, this is how I do it ...
我更喜欢将尽可能多的工作委托给较低级别的组件，在这种情况下是 Node 类。回复：找到一个节点的父节点，这就是我的做法......
template <typename T>
Node<T>* Node<T>::parent (const Node<T>* node)
{
if (node)
{
if (*node < *this)
{
if (left && (*node < *left))
return left->parent (node);
return this;
}
if (*node > *this)
{
if (right && (*right > *node))
return right->parent (node);
return this;
}
}
return nullptr;
}
