c++ - C++、バイナリツリーを作成して描画し、プレオーダーでトラバースする方法

Question

バイナリツリーを作成し、プレオーダートラバーサル戦略を使用して描画するにはどうすればよいですか? ルートは最初に入る数字になります。

私は数字のセットを持っています: 48 32 51 54 31 24 39. 48 がルートになります。プレオーダートラバーサルでは、子ノードはどのようにバイナリツリーにプッシュされますか?

score 2 · Accepted Answer

次のサブ問題を想像してください。あなたは一連の数字を持っています：

N A1...AX B1...BY

Nそれが対応するツリーのルートであることがわかります。知る必要があるのは、左側のサブツリーを形成する数字だけです。明らかに、残りの数値は右のサブツリーを形成します。

二分探索木の特性を覚えていれば、左側のサブツリーの要素の値はルートよりも小さい (右側の要素の値は大きい) ことがわかります。

したがって、左のサブツリーは、より小さい (または等しい可能性がある) 数値のシーケンスですN。残りの数値は右側のサブツリーにあります。

を再帰的に解く

A1...AX

と

B1...BY

たとえば、次のようになります。

10 1 5 2 9 3 1 6 4 11 15 12 19 20

あなたは得る：

score 2 · Accepted Answer

次のバイナリツリーがあるとします。

        A
      /    \  
    B        C   
   / \      / \
  D   E    F   G
     / \    
    H   I

予約注文トラバーサルは NODE、LEFT、RIGHT に進みます。

したがって、このバイナリツリーの予約注文は次のようになります。A B D E H I C F G

c++ - C++、バイナリ ツリーを作成して描画し、プレオーダーでトラバースする方法