如何在Left Child Right兄弟树中找到节点的父节点？

Question

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

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

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

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

Answer 1

从根开始，搜索记住上一次拿左分支的时间。当您找到密钥时，您最后离开的节点是父节点。如果没有留下分支，那么就没有父母。

顺便说一句，在Wikipedia definition

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

没有附加信息短语不是一般的可逆意味着你正在尝试做的是不可能的。但我不同意，所以不this Wikipedia discussion page

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; 
     } 
    } 
}