c++ - 如何在左子右兄弟树中找到节点的父节点？

Question

我想在左子右兄弟树中找到节点 N 的父节点。树已经订购了孩子，孩子的数量没有限制。

Node getParent(Node n)
{
   ....
   return parent;
}

我真的需要帮助，因为没有直接的方法可以找到它。

答案可以是伪代码或编程语言。

Answer 1

从根开始，搜索记住你上次选择左分支的时间。当您找到密钥时，您从中取出最后一个左侧的节点就是父节点。如果没有采取左分支，则没有父级。

顺便说一句，在维基百科的定义中

左子右兄弟二叉树是 k 叉树的二叉树表示。1在没有附加信息的情况下，从 k-ary 树转换为 LC-RS 二叉树（有时称为 Knuth 变换2）的过程通常是不可逆的。

如果没有其他信息，该短语通常是不可逆的，这意味着您尝试做的事情是不可能的。但我不同意，这个维基百科讨论页面也是如此

Answer 2

这是我的答案，虽然没有经过很多案例的测试，但你可以明白

struct node{
    node* left;
    node* right;
    int i;

    node(int _i,node* _left,node* _right){
        i=_i;
        left = _left;
        right = _right;
    }
};

node* traverse(node* root,node* parent, int y){
    if(root == NULL) return NULL;
    if(root->i == y) return parent;

    node* result  = traverse(root->left,root,y);
    if(result) return result;

    result = traverse(root->right, parent , y);
    if(result) return result;

    return NULL;

}

遍历函数被称为

 traverse(rootofthistree, NULL, integerWearlookingfor);

Answer 3

以下是我对您的数据结构的理解：

• node.left是其中之一：
  • 上一个兄弟姐妹（如果node不是第一个兄弟姐妹）
  • 父母（如果node是第一个兄弟姐妹）
  • null（如果node是树根）
• node.right是其中之一：
  • 下一个兄弟姐妹（如果node不是最后一个兄弟姐妹）
  • null（如果node是最后一个兄弟姐妹）
• node.child是其中之一：
  • 第一个孩子（如果node有孩子）
  • null（如果node是树叶）

N然后，您可以通过以下算法获取节点的父节点：

node* get_parent(node* N)
{
    //define parent of nullptr to be nullptr
    if (!N)
        return nullptr;
    while (true)
    {
        if (N->left)
        {
            //N->left is either the previous sibling or the parent
            if (N->left->child == N) //N->left is the parent
                return N->left;
            else //N->left is the previous sibling
                N = N->left;
        }
        else //a node with left==nullptr is the root, so its parent is nullptr
        {
            return nullptr;
        }
    }
}