如何在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; 
     } 
    } 
}