二叉樹的定義

Question

我看到Wikipedia二叉樹的定義是：

定義二叉樹的另一種方式是在向圖遞歸定義。二叉樹可以是：

單個頂點。

通過取兩棵二叉樹，添加一個頂點，並將從新頂點指向的邊添加到每棵二叉樹的根形成的圖形。

怎麼那麼是有可能有一個二叉樹一個根和一個左兒子，就像這樣：

  O 
     /
     O 

這是一個二叉樹，對不對？我在這裏錯過了什麼？

請不要只說「維基百科可能是錯的」，我在其他幾個地方也看到了這個定義。

Answer 1

這取決於你使用二叉樹算法：作爲冰淇淋，有很多味道:)

一個例子是，當你有節點指針和葉指針的節點上的混合，以及當你在一個完整的節點上插入新的值時，決定創建第二個節點（不管是根還是其他節點）的平衡系統：不是創建一個根節點和2個葉節點，通過分割創建另一個節點，創建另一個節點更加經濟節點。

Answer 2

正確。樹可以是空的（無）

假設你有兩棵樹：一棵樹有一個頂點，另一棵是空的（無）。他們看起來像這樣：

O . 

請注意，我爲（無）樹使用了一個點。

然後我添加一個新的頂點，並從新頂點到現有兩棵樹的邊緣（注意，我們不從現有樹中取出邊並將它們連接到新頂點 - 這是不可能的）。所以，現在看起來它：

O 
/\ 
O . 

由於邊緣導致（無）中沒有畫出，這裏是什麼是底：

O 
/
O 

我希望澄清。

Answer 3

維基百科可能是錯誤的。二叉樹是有限的數據結構，必須允許子樹爲空，否則二叉樹將是無限的。遞歸定義二叉樹的基本情況必須允許單個節點或空樹。的Touch of Class: An Introduction to Programming Well Using Objects and Contracts, by Bertrand Meyer, Springer Verlag, 2009. © Bertrand Meyer, 2009. 14.4

部分有二叉樹更好的遞歸定義

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.