c - 現在のノードの上にノードを取得することは可能ですか?

Question

二分木をトラバースするときに、現在のノードの上にあるノードを取得することは可能ですか?という質問を受けました。二重連結リストとして。

Answer 1

二重リンクとしてビルドする場合は、はい、「親」プロパティに移動します。抽象的な例:

struct node {
    struct node *parent; // << this is the parent, just access it
    struct node *rchild;
    struct node *lchild;
    int val;
}

それ以外の場合は、子ノードにアクセスするたびに前のノードをキャッシュする必要があります。

二重リンクリストは、バイナリツリーと同じではないことに注意してください(リストでは、各項目に 1 つの子があります)。