空のバイナリ検索ツリーは有効ですか？

StackOverflow https://stackoverflow.com/questions/810881

  •  03-07-2019
  •  | 
  •  

質問

バイナリ検索ツリーに関して、空のツリーに関する質問が2つあります。

  1. 空のツリー（null）は有効ですか？
  2. 子のないルートノードは有効ですか？
役に立ちましたか？

解決

はい、はい。

他のヒント

空のツリーとは、「有効」という言葉の意味と同様に、もちろん実装によって異なりますが、一般的には「はい」と言います。両方の質問に。空のツリーは、対象のエンティティセットが空の場合を表し、単一ノードは、セットに1つのエンティティが含まれる場合を表します。

子のない単一のノードは確かに有効であり、バイナリツリー構造によると：

  

（可変）バイナリツリー、BiTree、できます   空の状態または空ではない   状態：

     
      
  • 空の場合、データは含まれません。
    •   
  • 空でない場合、ルート要素と呼ばれるデータオブジェクトと、左サブツリーと右サブツリーと呼ばれる2つの異なるBiTreeオブジェクトが含まれます。
    •   

完全を期すため、このウィキペディアエントリは、用語などの非常に有用な要約です。

  

空のツリー（null）は有効ですか？

空の場合、ツリーはありません。したがって、妥当性の問題は発生しません。

  

子のないルートノードは有効ですか？

はい。それは、その中に1つの要素のみを持つティーです。

リンゴとオレンジを混ぜていると思います：

  1. null はいくつかのプログラミング言語の値であり、データ構造の実装の具体的な表現に関連しています
  2. ＆quot;空＆quot;は、「バイナリ検索ツリー」と呼ぶ抽象データ構造のプロパティです

現在、ツリーは順序付きセットです。これ以上でもそれ以下でもありません。もちろん、セットは空にすることができます！つまり、実装では、次のようなものになります。

MyTree tree = null

空のツリーを表しますか？まあ、それはあなたのモデルに依存します。 たとえば、空のサブツリーは、値のないノードによって表され、リーフへの参照が無効化されていると考えることができます。そのモデルでは、 null ポインターは論理的な観点からは意味がありません。しかし、これは 1つのアプローチにすぎません！センチネルベースのアプローチはプログラミングの喜びですが、メモリが非常に大きくなります。空のノードをヌルだけでモデル化できます。その場合、 null ポインターは空のツリーにすることができます。

バイナリツリーは、次のように再帰的に定義できます。

A single node with either no children, or with two children - 
each of which is a binary tree.

はい、両方の条件が真です。 二分木の場合、各ノードは0、1、または2つの子を持つことができます。 ツリーにルートノードのみがあり、他のノードがない場合は、NULLツリーと呼ばれます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top