3

データ構造の中間試験に備えて、教授は昨年のテストを出しました。これは、サンプル ツリーを完全な二分探索ツリーに再配置する問題です。ツリーを書き出すいくつかの異なるバージョンを試しましたが、Wolfram Mathematica からのこの完全なバイナリ ツリーの例は、フルの定義にも適合するため、まったく役に立ちませんでした。教科書では、完全なバイナリ ツリーを、レベル n-1 までのツリーが完全であり、レベル n にいくつかの余分なリーフ ノードがあり、すべて左揃えであると定義しています。

ノードはA E I L N O P R S T U、n=11 ノードです。これが私が思いついた最良の答えです：

           R
         /    \
        L      T
       / \    / \
     I    N   S   U
    / \  / \
   A  E O   P

しかし、これは WM のツリーの例には当てはまりますが、本の例には当てはまりません。それで、正しい答えはどれですか？

4

3 に答える 3

11

あなたの混乱がどこにあるのか完全にはわかりませんが、私は答えるために最善を尽くします...

すべてのノードに正確に0または2の子がある場合、バイナリツリーは完全であると見なされます。

最後を除いてすべてのレベルがいっぱいで、すべてのノードが可能な限り左にプッシュされている場合、バイナリツリーは完全であると見なされます。

したがって、これらの説明の両方に当てはまる場合は、可能ですが、同時に完全で完全なものにすることができます。

また、二分木がいっぱいで、すべての葉が同じレベルにある場合、二分木は完全であると見なされます。

したがって、上で描いた例では、そのツリーは完全で完全ですが、完全ではありません。

これがお役に立てば幸いです。

于 2010-10-19T14:06:02.307 に答える
4

うまくいけば役立ついくつかの例：

完了、完全ではない:

        R
      /    \
     L      T
    / \    / \
  I    N   S   U
 / \  /
A  E O

完全、未完了:

        R
      /    \
     L      T
    / \    / \
  I    N   S   U
      / \
     O   P


        R
      /    \
     L      T
    / \    
  I    N   
 / \  / \
A  E O   P
于 2010-10-21T02:38:34.600 に答える