0

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

这些是提供给我们的 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);

然而，他很难解释为什么这种方式更好。有人可以解释为什么这更有效吗？如果示例中需要更多代码，请询问。

4

6 回答 6

3

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

于 2009-11-19T23:31:47.733 回答
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 来定义树的底部两层（叶节点和它们上面的层），即每行定义[最多]三个节点。这样做的好处是将定义一棵树所需的行数大致减半（随着树的增长可能成为一个因素），并且不必为最多的节点（叶-节点）。现在......这样的结构/语法，当/如果树被附加到时，灵活性会大大降低，需要重新平衡它等等。（也许这就是为什么讲师建议对树进行硬编码，给学生对重新平衡树所需的操作类型有“感觉”。）

这说，

这两种方法都不是超级脆弱的expialidocious。

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

于 2009-11-20T00:15:55.043 回答
1

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

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

布丁的证据在吃：你想怎么处理这样一棵树？在第二种情况下，您从根节点开始，读取它的元素，如果它是一个运算符，则在适当的情况下递归读取子节点，然后对其值执行运算符的功能。然而，在第一种情况下，您不读取元素而是首先检查其类型——如果它是对另一个树节点的引用，则意味着它是一个运算符，因此您将该节点的值作为运算符。这个结论“它是一个树节点，所以它是一个运算符”对你来说应该听起来很可疑。如果你想对类型进行dipatching，类型应该是有意义的，所以操作符应该是“操作符”类型。不过，对于这个练习，我认为对字符串值进行分派就足够了。综上所述：

于 2009-11-20T14:25:57.623 回答
0

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

于 2009-11-19T23:32:12.040 回答
0

第二个读起来更好。如果您熟悉反向波兰符号，则第二个读起来就像您将输入到 RPN 计算器中一样。我认为效率在这里不应该是一个真正的问题，因为这只是一个验证类功能的测试。

于 2009-11-19T23:36:10.460 回答
0

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

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

于 2009-11-20T11:22:21.567 回答