二叉树节点 - 哪条路？

Question

对于数据结构中给出的作业，我们必须创建一个测试类来确定给出的代码是否正确遍历测试类中的二叉树。

这些是提供给我们的 BinaryTreeNode 类的 3 个构造函数：

public BinaryTreeNode(Object theElement, BinaryTreeNode theleftChild, BinaryTreeNode therightChild)
{
    element = theElement;
    leftChild = theleftChild;
    rightChild = therightChild;
}

public BinaryTreeNode(Object theElement)
{
    element = theElement;
}

public BinaryTreeNode() {} 

我很快在我的测试类中进行了以下操作，以创建指定的树之一：

// tree for ( A - B ) / C
BinaryTreeNode b1 = new BinaryTreeNode("A");
BinaryTreeNode b2 = new BinaryTreeNode("-");
BinaryTreeNode b3 = new BinaryTreeNode("B");
BinaryTreeNode b4 = new BinaryTreeNode("/");
BinaryTreeNode b5 = new BinaryTreeNode("C");
BinaryTreeNode bAB = new BinaryTreeNode(b2, b1, b3);
BinaryTreeNode bRoot = new BinaryTreeNode(b4, bAB, b5);
q.put(bRoot);

然而，我的朋友建议我这样做：

// tree for ( A - B ) / C
BinaryTreeNode b1 = new BinaryTreeNode("A");
BinaryTreeNode b2 = new BinaryTreeNode("B");
BinaryTreeNode b3 = new BinaryTreeNode("C");
BinaryTreeNode bRoot= new BinaryTreeNode("/", new BinaryTreeNode("-", b1, b2), b3);
q.put(bRoot);

然而，他很难解释为什么这种方式更好。有人能解释一下为什么这样效率更高吗？如果示例需要更多代码，请询问。

Answer 1

第二个使用字符串作为“元素”值，第一个使用 BinaryTreeNode。我不知道“element”的值应该是什么，但我的直觉告诉我它应该是一个字符串。这是这些片段之间的唯一区别。

Answer 2

这是一个混合包；-)

第二种方法在输出方面似乎更好：
它始终将字符串放入 BinaryTreeNode 的元素成员中，第一种方法为此目的混合使用字符串和 BinaryTreeNode 实例。

至少，我建议将第一个片段重写为

BinaryTreeNode b1 = new BinaryTreeNode("A");
BinaryTreeNode b3 = new BinaryTreeNode("B");
BinaryTreeNode b5 = new BinaryTreeNode("C");
BinaryTreeNode bAB = new BinaryTreeNode("-", b1, b3);
BinaryTreeNode bRoot = new BinaryTreeNode("/", bAB, b5);

第二种方法的另一个优点是它不需要中间节点的额外存储（bAB，例如上面的例子）。这不是一个大问题，因为这些变量是引用类型，因此需要很少的存储并且复制非常有效。第二种方法本质上是在原位构建这些节点，这可以被认为更有效。 （这就是说，随着树的深度增长，尝试以这种方式创建所有中间节点很快就会变得不可行......）

有一个有趣的停顿，一个教学时刻;-)，我们反思 过早优化...

另一方面...第一种方法（指示了语义变化）的优点是它使代码的支出更加更加规则，这可能有助于定位树结构中的问题更容易。
[编辑：] 一种可能的混合解决方案是使用解决方案 #2 来定义树的底部两层（叶节点及其上方的层），即定义 [最多]每行三个节点。这样做的优点是将定义树所需的行数大致减半（随着树的增长可能成为一个因素），并且不必计算和引用最多节点（叶节点）的变量。节点）。现在......这样的结构/语法，当/如果附加树时，会不太灵活，需要重新平衡它等（也许这就是为什么讲师建议对树进行硬编码，以给出学生对重新平衡树所需的操作类型有一种“感觉”。）

也就是说，这

两种方法都不是 Supercalifragilisticexpialidocious。

稍微酷一点的方法可能是从文本文件中读取树。该文本中的语法可能相当接近地反映了方法#1 布局中明显的每行一个命名节点，因此有人可能会认为，它本身并不会带来很大的收获......也许只是节省几次击键。然而，当我们考虑到这将“数据”与“代码”解耦时，这种解决方案的优点就变得更加明显。我们不需要重新编译程序（或者拥有该二进制文件的无数不同版本）为了在不同的树上工作，我们只需将程序指向不同的文本文件。此外，当/如果代码被重构（例如修改节点类的名称）时，这种解耦也会变得有趣。在极端情况下，这种代码与数据独立性将允许使用完全不同的树库，唯一必要的更改是在从文件解析节点的逻辑结构之后生成一些映射节点构造和组装的逻辑。

Answer 3

左边是第一个代码生成的结构，右边是第二个代码生成的结构：

          * -- "/"            "/"
         / \                  / \
        /   \                /   \
"-" -- *    "C"            "-"   "C"
      / \                  / \
     /   \                /   \
   "A"   "B"            "A"   "B"

布丁的证明在于吃：你想如何处理这样一棵树？在第二种情况下，您从根节点开始，读取其元素，如果它是运算符，则根据需要递归地读取子节点，然后对其值执行运算符的函数。然而，在第一种情况下，您不会读取该元素，而是首先检查其类型 - 如果它是对另一个树节点的引用，则意味着它是一个运算符，因此您将该节点的值作为运算符。这个结论“它是一个树节点，所以它是一个运算符”对您来说应该听起来很可疑。如果要对类型进行双分配，类型应该具有含义，因此运算符应该是“operator”类型。不过，对于本练习，我认为对字符串值进行调度就足够了。结论：将算子直接放入节点中。

Answer 4

每个节点的元素不需要是 BinaryTreeNode 本身。任何任意对象都可以。

Answer 5

第二个读起来更好。如果您熟悉逆波兰表示法，那么第二个表示法读起来就像输入 RPN 计算器一样。我认为效率实际上不应该成为问题，因为这只是验证类功能的测试。

Answer 6

我是朋友，我的理由是，将元素作为节点是不合适的，因为在这种情况下，我们使用它来表示数学方程。据我了解，您可以为单独的树提供一个根节点，作为节点的元素引用，但这对于本示例来说是完全不合适的。

我在第一种方式中看到的错误是，当他使用变量 bAB（即 bAB 中的节点 b1、b2 和 b3）时，他试图存储整个子树，我觉得这在工作时会错过使用树的要点来表示数学方程。