c++ - 在从通用树转换的二叉树中找到节点的父亲

Question

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

我要回答的是，给定一个节点 p，我怎样才能找到节点 p 的父亲？

这是一个节点（我使用非递归方式遍历，因此访问和父属性）

struct node {
  std::string name;
  int sons;
  bool visited;
  node * first;
  node * next;
  node * parent;    
};

这是一个例子：

通用树

  A                   
 /|\       
B C D

GeneralTree 的 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包含根节点。