二叉树定义

Question

我在维基百科中看到了二叉树的定义

另一种定义二叉树的方法是对有向图进行递归定义。二叉树是： 一个顶点。 一种图，由两个二叉树，加一个顶点，加上一个从新的顶点指向每个二叉树的根的边。

那么，怎么可能有一个根和一个左子的二叉树，像这样：

         O
        /
       O

这是一棵二叉树对吧？我在这里错过了什么？

请不要只说“维基百科可能是错的”，我在其他地方也看到过这个定义。

Answer 1

对，是这样。树可以是空的(零)

假设您有两棵树:一棵有一个顶点，另一棵是空的(零)。它们看起来是这样的：

O   .

注意，我为(零)树使用了一个点。

然后，我添加一个新的顶点，从新的顶点到现有的两棵树的边(注意，我们不会从现有的树中取边并将它们连接到新的顶点--这是不可能的)。现在看起来是这样：

   O
  / \
 O   .

由于导致(零)的边不是画出来的，下面是结尾处的内容：

   O
  /
 O

我希望它能澄清。

Answer 2

这取决于二叉树的算法:至于冰淇淋，有很多口味:)

一个例子是，当节点上有节点指针和叶指针的混合，当您在一个完整的节点上插入新值时，一个平衡系统决定创建第二个节点(不管是根节点还是另一个节点)：与其创建根节点和2叶节点，不如通过拆分它，只创建另一个节点要经济得多。

Answer 3

维基百科可能是错的。二叉树是有限的数据结构，一个子树必须允许为空，否则二叉树将是无限的。二叉树递归定义的基本大小写必须允许单个节点或空树。

“类的触摸:良好使用对象和契约的编程入门”，Bertrand Meyer著，Springer Ver剂，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.