7

（ルートノードではなく）特定のリーフノードから開始してツリーをトラバースし、親ポインターを使用してルートに到達するツリーを作成することは概念的に可能ですか？

誰かがツリーを実装し、配列を使用してすべてのリーフノード/外部ノードを保持し、各リーフ/外部ノードが親ノードのみを指し、それらの親が親ノードを指すなどの理由で、これを尋ねます。親を持たないルートノードに到達します。したがって、それらの実装では、ツリー内の任意の場所に到達するためにリーフの1つから開始する必要があり、ツリーノードには子ポインターがなく、親ポインターのみがあるため、ツリーを「下に」移動することはできません。

このような実装は見たことがないので面白いと思いましたが、それでも「ツリー」と見なすことができるかどうか興味がありました。私はあなたが根の代わりに葉で横断を始める木を見たことがありません。また、ツリーノードに親ポインターのみがあり、子ポインターがないツリーを見たことがありません。

4

2 に答える 2

4

はい、この構造は存在します。これは、スパゲッティスタックと呼ばれることがよくあります。

スパゲッティスタックは、「の一部」の関係を表すのに役立ちます。たとえば、アップキャストを効率的にする方法でクラス階層を表現する場合は、クラス階層を、各タイプのノードがその親タイプへのポインターを格納するスパゲッティスタックとして表現できます。そうすれば、ノードから上に歩くだけで、アップキャストが有効かどうかを簡単に見つけることができます。

また、コンパイラでスコーピング情報を追跡するためによく使用されます。各ノードはプログラム内の1つのスコープを表し、各ノードには、その1レベル上のスコープを表すノードへのポインターがあります。

お役に立てれば！

于 2013-03-11T18:02:33.003 に答える
0

リーフノードの配列Aが指定されている場合、トラバーサルが可能です。リーフノードが1つしかない場合、ツリーをトラバースする方法がわかりません。擬似コード：

// initial step 
add all nodes in A to a queue Q  

//removeNode(Q) returns pointer to node at front of Q 
while((node = removeNode(Q)) != NULL) 
    /* do your operation on node */ 
    add node->parent to Q
于 2013-03-11T18:02:35.383 に答える