实现二叉树

现在我们将创建一棵二叉树（不是二叉搜索树）。二叉树的关键因素是，我们必须为左子节点和右子节点准备两个占位符，以及我们要在节点中存储的数据。二进制节点的简单实现如下所示：

前面的代码显示，我们有一个带有树属性的类，用于存储数据左侧和右侧。在构建新节点时，我们会将节点值添加到 data 属性中，而左右属性则保持为 NULL，因为我们不确定是否需要这些属性。我们还有一个 addChildren 方法，用于为特定节点添加左侧子节点和右侧子节点。

现在，我们将创建一个二叉树类，在该类中，我们可以定义根节点和遍历方法，这与本章前面的基本树实现类似。两种实现方式的区别在于遍历过程。在上一个示例中，我们使用 foreach 遍历每个子节点，因为我们不知道有多少个节点。由于二叉树中的每个节点最多可以有两个节点，而且它们被命名为左节点和右节点，因此我们只能遍历左节点，然后再遍历右节点。更改后的代码如下：

它看起来与本章前面的基本树类非常相似。现在，让我们用一些节点来填充二叉树。通常，在任何足球或板球比赛中，我们都会有淘汰赛，两支球队相互比赛，胜者晋级，然后进入决赛。在我们的例子中，也可以使用类似的二叉树结构。因此，让我们创建一些二进制节点，并将其结构化：

首先，我们创建了一个名为决赛的节点，并将其作为根节点。然后，我们创建了两个半最终节点和四个四分之一最终节点。两个半最终节点各有两个四分之一最终节点作为左右子节点。最终节点有两个半最终节点作为左右子节点。addChildren 方法正在为节点分配子节点。在最后一行中，我们遍历了树并分层显示了数据。如果在命令行中运行这段代码，我们将看到以下输出：