如何在二叉树中找到节点的父节点？

问题描述：

这意味着以下内容：

B为根，其子A，d，我
D的孩子是C，E，G
我的孩子是H，L

等。

现在，我已经写了下面的方法：

public Position<E> parent(Position<E> v)

其中“V”代表在上面树的一个字母，而这种方法需要找到它的父。

我一直在努力与这个小时..任何想法？

这看起来并不像一个二叉树。 – 2014-10-16 19:16:54

这是因为它起初是一棵普通的树，并且它被转换为二叉树。这就是你如何表示一棵普通的树，它有一些有3个孩子的节点（在这种情况下），就像一棵二叉树。 – Gambit2007 2014-10-16 19:17:44

从二叉树的概念，一个节点只能有2个孩子，而不是3. – 2014-10-16 19:20:25

答

从你出了什么：

算法是：

start from root 

for every node v 

every left-child is node v's child so add this child to node v childs list 

every right-child is node v's parent's child(or parent of parent until it is a left-child of its parent, then the node you discovered is the child of left-child node's parent's child).

在实际的树寻找节点的父伪代码：

enter node. 

if node is left child 
    print its node->parent. 
else 
    while node->parent is right child 
     node = node->parent 
    print node->parent.

是的，你写的完全描述了节点，但是我怎样才能实现一个代码来找到给定节点的父节点？ – Gambit2007 2014-10-16 19:30:13

你想在二叉树或实际树中的父节点？ – Lrrr 2014-10-16 19:34:03

@ Gambit2007因为我喜欢你的问题我打算给你伪代码，但我不打算给你添加食物并给出全部答案 – Lrrr 2014-10-16 19:38:17

答

这是简单的;假设你的节点类没有访问父即

class Node{ 
Node left; 
Node right; 
int value; 
}

所有你需要做的是从根开始，遍历在树中pre-order时尚。如果你遇到你的目标节点，则其父是从堆栈（为什么？）杀出的最后两个元素

@see Depth First Search

答

在这种二叉树的是最简单的重新标记子指针为children之一（左孩子）和sibling（右孩子），因为这就是他们所代表的。由于您没有父指针，因此当您找到可能是父节点的节点时，您必须在搜索未来节点时将其传递。

我需要做出很多假设，因为您提供的信息太少。

如果Position是您的节点类型和您所需的功能是Tree的成员，那么那么它会是这个样子：

private Position<E> parentImpl(Position<E> v, Position<E> node, Position<E> parent) { 

    if (node.equals(v)) { 
    return parent; 
    } 

    for (Position<E> child = v.children; child != null; child = child.sibling) { 
    Position<E> rtn = parentImpl(v, child, node); // current node is parent 
    if (rtn != null) { 
     return rtn; 
    } 
    }   
    return null; 
}

现在，你想要的功能只是调用这一个。

public Position<E> parent(Position<E> v) { 
    return parentImpl(v, root, null); // Root has no parent. 
}

当v不在树中并且它是树的根时，这将返回null。

public position parent（Position v）throws IllegalArgumentException { return parentImpl（v，bTree。root（），null）; } 私人位置 parentImpl（位置 V，位置节点，位置父）{ 如果（节点== v）的{ 返回父; } 的（位置孩子= bTree.left（V）;！孩子= NULL;孩子= bTree.right（V））{ 位置 RTN = parentImpl（V，孩子，节点）;如果（rtn！= null）{ return rtn; } } return null; } 这就是我实现了它，它不工作.. bTree.left（V）是你如何进入孩子，bTree.right（五）同级 – Gambit2007 2014-10-16 20:54:13

人，你没有给任何地方接近足够的信息来提供完美的解决方案。我说“类似的东西”，而不是“这就是它”。找出我的代码正在做什么，并找到你的错误。我保证这种方法可行。 – Gene 2014-10-16 22:22:23

答

我和你一样做家庭作业...

解决方案：我们的一般树中的父节点将成为我们的二叉树中有一个左子节点的节点，并且此父节点的右子节点不等于我们的节点v（请参阅节点I）

你可以这样做：如果v的父亲是左孩子，那么v的父亲将是最后找到的具有左孩子的节点。但家长一定不能有正确的孩子，所以如果它有一个，你必须寻找这最后一个节点的上父母。（见节点I）

希望这有助于

如何在二叉树中找到节点的父节点？

相关推荐