c++ - Left Child Right Sibling Treeでノードの親を見つける方法は?

Question

Left Child Right Sibling Tree でノード N の親を見つけたいと考えています。ツリーは子を注文しており、子の数に制限はありません。

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

直接見つける方法がないので、本当に助けが必要です。

答えは、疑似コードまたはプログラミング言語である可能性があります。

Answer 1

データ構造を理解する方法は次のとおりです。

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

Answer 2

ルートから始めて、最後に左の分岐を行ったときのことを思い出して検索します。キーを見つけたら、最後に左に取ったノードが親ノードでした。左の枝が取られなかった場合、親はありません。

ところで、ウィキペディアの定義では

左の子、右の兄弟のバイナリ ツリーは、k 分木のバイナリ ツリー表現です。1 k 分木から LC-RS 二分木への変換プロセス (Knuth 変換と呼ばれることもあります2 ) は、通常、追加情報なしでは元に戻せません。

一般に、追加情報がなければ元に戻せないというフレーズは、あなたがやろうとしていることは不可能であることを意味します。しかし、私は同意しません。このウィキペディアの議論ページもそうです。

Answer 3

これが私の答えですが、多くのケースでテストされていませんが、アイデアを得ることができます

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