バイナリツリーのすべての可能な順列を生成するためのアルゴリズムを見つけ出す必要があります。リストを使わずにそれを行う必要があります(これは、ツリー自体が持つことができないセマンティクスとリストに変換されます)。私は木の高さが3以下のアルゴリズムには適していますが、高さが高くなるたびに高さごとに1組の可能な並べ替えが緩和されます。リストを使わないバイナリツリーのパーミッション
各ノードは元の状態に関する情報を保持しているため、あるノードがそのノードに対して可能なすべての順列が試行されたかどうかを判断できます。また、ノードは天気に関する情報を運ぶか、「スワップ」されていない、すなわち、それが可能なすべてのパーツの部分木を見た場合には、情報を運ぶ。ツリーは左にセンタリングされています。つまり、右のノードは常に(このアルゴリズムをカバーする必要がない場合を除いて)リーフノードでなければならず、左のノードは常にリーフまたはブランチです。
私は、現時点で使用しているアルゴリズムは、ソートのこのように記述することができますように
branch
/ |
branch 3
/ |
branch 2
/ |
0 1
branch
/ |
branch 3
/ |
branch 2
/ |
1 0 <-- first swap
branch
/ |
branch 3
/ |
branch 1 <-- second swap
/ |
2 0
branch
/ |
branch 3
/ |
branch 1
/ |
0 2 <-- third swap
branch
/ |
branch 3
/ |
branch 0 <-- fourth swap
/ |
1 2
と:そのアルゴリズムの所望の動作はこのようなものになるだろう
if the left child node has been swapped
swap my right node with the left child nodes right node
set the left child node as 'unswapped'
if the current node is back to its original state
swap my right node with the lowest left nodes' right node
swap the lowest left nodes two childnodes
set my left node as 'unswapped'
set my left chilnode to use this as it's original state
set this node as swapped
return null
return this;
else if the left child has not been swapped
if the result of trying to permute left child is null
return the permutation of this node
else
return the permutation of the left child node
if this node has a left node and a right node that are both leaves
swap them
set this node to be 'swapped'
...
宿題のようなにおいはしますが、あなたは本当の努力を入れているように見えます。だから、普通の宿題様式の質問よりもはるかに優れています。それでも、そのデータ構造は、宿題であっても、置換のために非常に貧弱です。 – Welbog
私はそれが宿題ではないことを恐れている(私はそれが欲しかった)、私は実際にこの仕事のためにラインを持っている...;) –
ああ、うわー。それは本当にうんざりです、これは狂った問題のようです。私は何が出てくるのか見てみましょう。 – Welbog