0

式の変換を求めているわけではありません

接頭辞から接頭辞への変換

入力がプレフィックス表記の形式で与えられている場合、つまり BST の preorder traversal の場合、BST についてそれを求めているだけです。次に、値のシーケンスを infix 表記、つまり BST の inorder traversal に変換するにはどうすればよいですか。

                 8
               /  \
              1    12
              \     /
               5   9
             /   \
            4     7
                 /
                6

たとえば、事前注文トラバーサルは 8 1 5 4 7 6 12 9 を与えます

これらの一連の値 (入力) を順不同のトラバーサル式に変換するにはどうすればよいですか 1 4 5 6 7 8 9 12.

AS 場合によっては inorder 式の方が扱いやすい...

4

2 に答える 2

0

BST の場合:
プレフィックス: 左サブツリー、ノード、右サブツリー。
Infix : ノード、左サブツリー、右サブツリー。
Postfix : 右サブツリー、左サブツリー、ノード。

変換は、ツリーをどのようにトラバースするかによって異なります。

于 2012-11-15T20:21:25.443 に答える
0

させて

V = 頂点

L = 左サブツリー

R = 右サブツリー

プレオーダー = VLR

インオーダー = LVR

Postorder = LRV

(修正する順番を入れ替えるだけで同じです)

それらを元に戻してプレフィックス値をインフィックス値にする 1 つの方法は、プレフィックス値を使用して二分探索木を再度作成し、インオーダー トラバーサルを実行することです。

また！

ソートするだけです...（BSTは、それらを1行に圧縮すると常にソートされます（上から下に圧縮します））

于 2013-03-05T14:16:58.527 に答える