c++ - 如何在树结构中从子节点移动到父节点？

Question

struct node
{
    int data;
    node *child;
    node *sibling
};

我想要一个从 child 移动到 parent 的循环。如果一棵树的根有 5 个 child ，那么从最后一个 child 开始到根。这意味着循环应该以相反的方式移动。

事实上，如果我有一个 child 数组，这可能很容易，但是如果我只有一个 child parent 关系怎么办，在这种情况下，每个 child 都有一个 parent ，那么我是否有可能从 child 到 parent 直到我 Root 。

Answer 1

您需要一个父指针才能在循环中直接从子指针移动到父指针。 我发现这很有效。

struct node{
    int value;
    node * parent;
    node ** childArray;
    int NumberOfChildren;
}

您在根节点上将 parent 设置为 null，并在叶(最终)节点上将 childArray 指针设置为 null。

当你想在树中移动时，你可以使用一个节点*。

例如

node * PCurrentNode = &MyNode;
PCurrentNode = MyNode->Parent;//Move Up
PCurrentNode = MyNode->ChildNodes[5]//Move to the 5th child node

如果您从根节点开始并向下递归，则可以避免使用父指针，因为您只需向上递归以到达父节点。