从普通树转换的二叉树中找到节点的父亲

Question

我正在使用普通树的二叉树实现，其中一个节点的第一个子节点是“左”，其他任何兄弟节点都是“正确“的第一个儿子。

我想回答的是，给定一个节点p，如何找到节点p的父亲？

这里是一个节点（我使用的非递归的方式遍历，从而被访问和父属性）

下面是一个例子：

GeneralTree

A     
/|\  
B C D 

通用树的BinaryTree版本

A 
/
B 
\ 
    C 
    \ 
    D 

所以B，C，和d的父节点都是A.

Answer 1

只需按照父母的联系，直到找到一个空引用 - 出现这种情况，如果你开始p作为根节点 - 或一个包含您来自其左子节点的节点。

var current = p; 
var parent = current.parent; 

while ((parent != null) && (current != parent.left)) 
{ 
    current = parent; 
    parent = current.parent; 
} 

现在parent包含节点的在p或null父节点如果p包含根节点。