树数据结构通常是根据节点或子树定义的吗？

Question

我正在通过为Ruby编写树库来研究树遍历算法。就基本建筑而言，似乎有两个合理的选择；

1. 只有树。树有根值和子树
2. 存在树和节点。一个节点有一个值，子节点。树有根节点和子树。子树的根节点是树的根节点的子节点

其中一种设计更常见吗？在这个库的开发过程中，1）太幼稚或2）不必要的冗余会变得“明显”吗？本图书馆的预期用途为一般用途；我希望它可以用于巨树、二进制搜索树或解析树等。

我能想到其他不那么合理的建筑；

3） 树是节点的集合。树有一个根节点。节点有一个值和子节点。没有子树的概念。

4）如果我选择了一个只有节点的体系结构，我不能合理地问节点诸如“这棵树中有多少节点”或“平衡这棵树”。

Answer 1

我从两个方面研究过树木。第一个是，只有节点具有属性（通常是数据引用、子引用，可能还有父引用）和行为。这很好用，因为没有单独的树数据类型。但它也有缺点，因为空树由空节点表示。因此，您的代码中充满了以下内容：

if (tree == null)
    tree = node;
else
    tree.Insert(node);

检查null会导致代码难以读取。

不过，一个好处是，可以将任何节点视为一棵树。例如，你可以写：

tree.Right.CountNodes();

这将返回右子树的节点数。

因此，创建一个包含节点的树数据结构。现在，节点只是数据，树具有行为。在内部，有一个根节点可以为null，树行为必须处理它。但客户机代码只能写：

tree.Insert(node);

您仍然可以计算子树中的节点，不过：

tree.CountNodes(node);  // counts nodes in the subtree rooted at node

你使用哪种设计在很大程度上取决于风格。我发现更容易构建一个树数据结构，从而抽象出处理节点之类的复杂问题。