最佳实践：子节点对其父节点的了解

Question

我想了解树中的子节点应该了解其父节点多少信息的最佳实践。

我当前的问题相当简单直接。我有一棵信息树，想要获取叶节点的“全名”（在本例中，它将是树中每个节点到叶节点的名称，并用点分隔）。我可以通过向叶节点添加一个“getFullName”方法来完成此操作，该方法遍历树到根并在每个父级的名称前面添加并返回最终结果，但这需要叶节点知道其父级的类类型（叶和非叶子不是同一类）。或者我可以在其他地方添加一个实用函数，该函数基本上执行相同的操作，但了解不同的类类型。

我试图四处搜索，但问题有点太宽泛，无法在谷歌上获得任何有用的结果。

提前致谢。

Answer 1

您确实在这里有很多选择，是的，您的问题解决了一种常见情况，即一方面权衡处理效率，另一方面增加存储需求和可能的冗余。

不存在单一的最佳实践。空间/时间权衡取决于您的情况。如果您使用冗余存储，将子链接和父链接保留在节点内，则需要确保数据结构正确封装，并且您的方法保持所有内容一致。

由于您有一个从顶部遍历到节点的用例，因此父链接工作正常，您可以通过递归或从后到前构建字符串来组成全名。因为用例适合您的情况，所以这不是一个坏主意。

另一种选择是将全名存储在节点中，但这会在移动节点时增加冗余。

简而言之，您不必担心违反最佳实践，但您应该权衡所有选择，做出适合您的选择。

现在，如果您正在制作一个通用的树数据结构，例如 Java 的 TreeNode，您可能会创建一个接口并允许人们按照他们认为合适的方式实现事物，提供一个合适的通用实现（DefaultMutableTreeNode），该实现具有所有链接 - 父级、孩子和兄弟姐妹。

Answer 2

您描述的情况是使用递归的典型情况。换句话说，树中的每个节点都可以有一个名为 getFullName 的方法，以这种方式定义：（

string getFullName() {
    myFullName = myParent.getFullName() + myLocalName;
    return myFullName;
}

这是伪代码；我假设如果 myParent 为 nil，那么myParent.getFullName() 是空字符串，您可以根据您的特定语言进行更改）

当没有父级时，递归结束。节点必须知道的唯一事情是它自己的名称以及它的父节点是谁。

Answer 3

我不认为让子节点类“了解”其父节点有任何问题。如果您担心可扩展性，父母可以实现一个接口。

另一种选择是让父类更新其子树中所有子节点的“名称”字段......如果您创建一棵大树然后只查询它（恒定时间查找），这可能是有意义的。同样，如果您担心耦合过多，接口可以提供帮助。

Answer 4

至少每个节点应该知道它的父节点。叶节点和非叶节点具有不同的类，但这意味着每个父节点都属于同一类。使用它来遍历树并构建名称（反向）。