c++ - ツリーの平坦化

Question

データの平坦化: ノードのバイナリ ツリーが与えられたときに、ノードのリンク リストを返す再帰関数を作成する方法は? (ツリーは変更可能です)

この質問では、木を平らにすることは何を意味しますか? 二分木のすべての要素を左右のポインタを持つリストに維持する必要がありますか、それとも私が取得していない別のキャッチがありますか?

第二に（ツリーは変更できます）、楽しみはビルドとともにツリーの変更を処理できる必要があるということですか？

Answer 1

Suppose you have a binary tree like so:

    a
   / \
  b   c
 / \   \
0   0   d
       / \
      0   0

Where a, b, etc. are nodes and 0 is nil. There are several possible recursive traversals of the tree:

• Pre-order, visiting parents before children: a b c d

• In-order, visiting parents between children: b a c d

• Post-order, visiting parents after children: b d c a

A “flattening” of a tree is merely a list resulting from a traversal; your data structure is no longer nested, but flat instead. To flatten a tree, begin with an empty linked list. Then traverse the tree in the order of your choosing, appending each visited node to the linked list. I presume “the tree can be modified” means that your function may alter the tree as it builds the list, if you find it necessary to do so.

Answer 2

フラット化とは、ノードを線形の順序で並べたいということです。ツリーにはいくつかの一般的な順序付けがあります: preorder、inorder、または postorder で、親ノードがそれぞれ子の前、間、または後に表示されます。