87

以下のツリーの用語について混乱しています。ツリーについて調べてきましたが、これらのツリーを区別することができません。

a) 完全な二分木

b) 厳密な二分木

c) 完全二分木

これらの木を区別するのを手伝ってください。これらのツリーはいつ、どこでデータ構造で使用されますか?

4

12 に答える 12

91

完璧な木:

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ / \ / \ / \
x x x x x x x x

完全なツリー:

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ /
x x x

厳密/完全ツリー:

       x
     /   \
    /     \
   x       x
  / \ 
 x   x 
    / \
    x x
于 2012-09-10T21:35:27.770 に答える
74

ウィキペディア

完全な二分木 (適切な二分木または 2 ツリーまたは厳密な二分木である場合もあります) は、葉以外のすべてのノードが 2 つの子を持つツリーです。

したがって、子が 1 つしかないノードはありません。厳密な二分木と同じように見えます。

これは、Google からの完全な/厳密なバイナリ ツリーの画像です。

ここに画像の説明を入力

完全二分木とは、最後のレベルを除くすべてのレベルが完全に埋められ、すべてのノードが可能な限り左にある二分木です。

バランスの取れた木という意味だそうです。

これは完全なバイナリ ツリーの画像です。Google から入手した画像の完全なツリー部分はおまけです。

ここに画像の説明を入力

于 2012-09-10T21:28:47.653 に答える
53

STRICT と FULL BINARY TREE には違いがあります。

1) FULL BINARY TREE:高さ h のバイナリ ツリーで、正確に (2^h)-1 個の要素を含むものは、フルバイナリ ツリーと呼ばれます。(参照: Pg 427、C++ のデータ構造、アルゴリズム、およびアプリケーション[University Press]、Sartaj Sahni による第 2 版)。

または言い換えれば

FULL BINARY TREE では、各ノードに正確に 0 または 2 つの子があり、すべてのリーフ ノードが同じレベルにあります。

例:以下は FULL BINARY TREE です。

          18
       /      \   
     15       30    
    /  \     /   \   
  40    50  100  40

2) STRICT BINARY TREE:各ノードには正確に 0 個または 2 個の子があります。

例:以下は STRICT BINARY TREE です。

         18
       /     \   
     15       30    
    /  \          
  40    50

完全なバイナリ ツリーの定義に混乱はないと思いますが、投稿を完全なものにするために、完全なバイナリ ツリーとは何かを説明したいと思います。

3) COMPLETE BINARY TREE:最後のレベルを除いてすべてのレベルが完全に満たされ、最後のレベルにすべてのキーが可能な限り残っている場合、バイナリ ツリーは完全なバイナリ ツリーです。

例:以下は COMPLETE BINARY TREE です。

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
 /  \   /
8   7  9

注:以下も完全なバイナリ ツリーです。

         18
       /     \   
     15       30    
    /  \     /   \   
  40    50  100  40
于 2015-08-18T05:21:50.270 に答える
10

免責事項-いくつかの定義の主な情報源はウィキペディアです。私の回答を改善するための提案は大歓迎です。

この投稿には受け入れられた回答があり、良いものですが、私はまだ混乱していたので、これらの用語の違いについてさらに明確にしたいと思います.

(1)完全二分木 - 完全二分木は、葉以外のすべてのノードが 2 つの子を持つ二分木です。これは、厳密には二分木とも呼ばれます。

ここに画像の説明を入力 ここに画像の説明を入力

上記の 2 つは、完全または厳密な二分木の例です。

(2) COMPLETE BINARY TREE-現在、完全な二分木の定義は非常に曖昧であり、次のように述べています:できるだけ左に。最後のレベル h で、できるだけ左に 1 ～ 2h のノードを持つことができます。

斜体の行に注意してください。

あいまいさはイタリック体の行にあります。「最後のレベルを除く」は、最後のレベルも完全に満たされる可能性があることを意味します。つまり、この例外は常に満たされる必要はありません。例外が成立しない場合は、投稿した 2 番目の画像とまったく同じで、完全な二分木とも言えます。したがって、完全な二分木も完全で完全ですが、その逆ではありません。これは、もう 1 つの定義によって明確になります。

ALMOST COMPLETE BINARY TREE -完全な二分木の定義の例外が成立する場合、それはほぼ完全な二分木またはほぼ完全な二分木と呼ばれます。これは完全な二分木そのものの一種ですが、より明確にするために別の定義が必要です。

したがって、ほぼ完全な二分木は次のようになります。画像でノードが可能な限り左にあることがわかります。したがって、完全な二分木のサブセットのようになります。より厳密に言えば、ほぼ完全な二分木はすべて完全な二分木です。ツリーですが、その逆ではありません。:

ここに画像の説明を入力

于 2014-09-28T19:36:11.367 に答える
3

ノードがツリー形式で描かれているバイナリ ツリーを考えてみましょう。ここで、ノードに上から下、左から右に番号を付け始めます。完全なツリーには次のプロパティがあります。

n に子がある場合、n より小さい番号のすべてのノードには 2 つの子があります。

n に 1 つの子がある場合、それは左側の子でなければならず、n 未満のすべてのノードには 2 つの子があります。さらに、n より大きい番号のノードには子がありません。

n に子がない場合、n より大きい番号のノードには子がありません。

完全なバイナリ ツリーを使用して、ヒープを表すことができます。これは、ギャップのない連続したメモリで簡単に表すことができます (つまり、最後に存在する可能性のあるスペースを除いて、すべての配列要素が使用されます)。

于 2012-09-10T21:33:19.193 に答える
2

完全な二分木は完全な二分木ですが、その逆は不可能であり、二分木の深さが n の場合はノーです。完全二分木のノード数は ( 2^n-1 ) です。バイナリ ツリーでは 2 つの子を持つ必要はありませんが、フル バイナリでは、すべてのノードに子がないか 2 つ存在します。

于 2012-10-16T19:13:54.000 に答える
2

二分木に関する私の限られた経験では、次のように思います。

  1. 厳密なバイナリ ツリー: リーフ ノードを除くすべてのノードには 2 つの子があるか、ルート ノードのみがあります。
  2. Full Binary Tree : H の厳密に (または正確に) 2^(H+1) -1 ノードを含むバイナリ ツリー。どのレベルに最も多くのノードがあるかは明らかです。または要するに、すべてのリーフノードが同じレベルにある厳密な二分木です。
  3. 完全な二分木 : 最後のレベルを除くすべてのレベルが完全に埋められ、すべてのノードが可能な限り左にある二分木です。
于 2017-01-05T18:14:00.093 に答える