0

ウィキペディアでこのバイナリ ツリーの定義を参照してください。

二分木を定義するもう 1 つの方法は、有向グラフでの再帰的な定義です。二分木は次のいずれかです。

単一の頂点。

2 つのバイナリ ツリーを取り、頂点を追加し、新しい頂点から各バイナリ ツリーのルートに向かうエッジを追加することによって形成されるグラフ。

では、次のように、1 つのルートと 1 つの左の息子を持つバイナリ ツリーをどのようにして持つことができるでしょうか。

         O
        /
       O

これは二分木ですよね？ここで何が欠けていますか？

そして、「ウィキペディアは間違っている可能性がある」とだけ言わないでください。私はこの定義を他のいくつかの場所でも見ました.

4

3 に答える 3

2

正しい。ツリーは空にすることができます（nil）

2つのツリーがあると仮定します。1つは1つの頂点を持ち、もう1つは空（nil）です。彼らはこのように見えます：

O   .

（nil）ツリーにドットを使用したことに注意してください。

次に、新しい頂点を追加し、新しい頂点から既存の2つのツリーにエッジを追加します（既存のツリーからエッジを取得して新しい頂点に接続しないことに注意してください。これは不可能です）。だから今はそのように見えます：

   O
  / \
 O   .

（nil）につながるエッジは描画されないため、ここで最後になります。

   O
  /
 O

それが明らかになることを願っています。

于 2012-08-30T03:54:02.277 に答える
0

ウィキペディアは間違っている可能性があります。二分木は有限のデータ構造であり、サブツリーは空にする必要があります。そうしないと、二分木は無限になります。バイナリツリーの再帰的定義の基本ケースでは、単一ノードまたは空のツリーのいずれかを許可する必要があります。

Touch of Classのセクション14.4 ：オブジェクトとコントラクトをうまく使用したプログラミングの概要、Bertrand Meyer、Springer Verlag、2009年。©Bertrand Meyer、2009年。バイナリツリーのより良い再帰的定義があります。

Definition: binary tree

A binary tree over G, for an arbitrary data type G, is a finite set of items called
nodes, each containing a value of type G, such that the nodes, if any, are
divided into three disjoint parts:
  • A single node, called the root of the binary tree.
  • (Recursively) two binary trees over G, called the  left subtree and right subtree.

The definition explicitly allows a binary tree to be empty (“the nodes, if any”).
Without this, of course, the recursive definition would lead to an infinite
structure, whereas our binary trees are, as the definition also prescribes, finite.
If not empty, a binary tree always has a root, and may have: no subtree; a
left subtree only; a right subtree only; or both.
于 2012-08-30T04:30:15.630 に答える
0

二分木に使用するアルゴリズムに依存します: アイスクリームに関しては、多くのフレーバーがあります :)

1 つの例は、ノードにノード ポインターとリーフ ポインターが混在していて、完全なノードに新しい値を挿入するときに 2 番目のノード (ルートであるか他のノードであるかに関係なく) を作成することを決定するバランシング システムがある場合です。代わりにルートと 2 つのリーフを作成するよりも、それを分割することで、別のノードだけを作成する方がはるかに経済的です。

于 2012-08-30T03:49:28.677 に答える