binary-tree - 二叉树定义

Question

我在Wikipedia中看到了二叉树的这个定义：

定义二叉树的另一种方法是在有向图上递归定义。二叉树是：

单个顶点。

由两棵二叉树组成的图，添加一个顶点，然后添加一条从新顶点指向每个二叉树根的边。

那么如何才能拥有一个具有一个根和一个左子的二叉树，如下所示：

         O
        /
       O

这是二叉树吧？我在这里想念什么？

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

Answer 1

正确的。一棵树可以是空的（nil）

假设你有两棵树：一棵有一个顶点，另一棵是空的（nil）。它们看起来像这样：

O   .

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

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

   O
  / \
 O   .

由于没有绘制通向 (nil) 的边，因此这里是最后的内容：

   O
  /
 O

我希望它澄清。

Answer 2

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

第 14.4 节的Touch of Class: An Introduction to Programming Well Using Objects and Contracts，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.

Answer 3

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

一个示例是，当您在一个节点上混合使用节点指针和叶指针时，当您在完整节点上插入新值时，平衡系统决定创建第二个节点（无论是根节点还是另一个节点）：而不是创建一个根和两个叶子，通过拆分它，创建另一个节点更经济。