时间戳

首页 > 解决方案 > One-line output operator for a binary tree

c++ - One-line output operator for a binary tree

问题描述

I wrote a simple binary tree class in C++ and want to add an output operator to it. My first attempt was:

ostream& operator<<(ostream& out, const Tree& tree) {
    out << tree.myData;
    if (tree.myLeft)
        out << "(" << (*tree.myLeft)  << ")";
    if (tree.myRight)
        out << "[" << (*tree.myRight)  << "]";
    return out;
}

(where myLeft and myRight are pointers to left and right child of the current tree, respectively). This works correctly, however, it is not sufficiently cool, since it spans several lines and requires to write "out << " several times.

As an attempt to create a one-line operator, I wrote this:

ostream& operator<<(ostream& out, const Tree& tree) {
    return (out << tree.myData
        << "(" << (tree.myLeft? *tree.myLeft: "")  << ")"
        << "[" << (tree.myRight? *tree.myRight: "") << "]");
}

But, this generates an error:

incompatible operand types ('Tree' and 'const char [1]')

So I tried this:

ostream& operator<<(ostream& out, const Tree& tree) {
    return (&tree?
        out << tree.myData
            << "(" << *(tree.myLeft)  << ")"
            << "[" << *(tree.myRight) << "]":
        out);
}

This works on my computer, but generates a warning implying that this is undefined behavior:

Reference cannot be bound to dereferenced null pointer in well-defined C++ code; pointer may be assumed to always convert to true [-Wundefined-bool-conversion]

QUESTION: Is there a way to write this output operator in a simple single statement?

标签： c++outputbinary-tree

解决方案

一个简单而优雅的解决方案是重新设计您的树以在没有空指针的情况下工作。相反，将当前使用的空指针替换为指向具有与空树一致的行为的哨兵树节点的指针。

然后你可以重写你的输出流操作符，如下所示：

ostream& operator<<(ostream& out, const Tree& tree) {
    if (&tree == &Tree::NULL_TREE_SENTINEL) return out;
    return out << tree.myData
        << "(" << *tree.myLeft  << ")"
        << "[" << *tree.myRight << "]";
}

（这假设内部有一个相应的静态成员Tree，哨兵是指针，就像单例一样。）

或者，哨兵树节点可以是Tree具有这种行为的子类的一个实例。这有时被称为空对象模式。然而，它需要动态调度（即通过虚拟成员函数的运行时多态性）才能工作。

除此之外，您还不能完全正确地诊断出第二个代码的问题：

这适用于我的电脑

它似乎有效，但实际上并没有。我不知道在什么情况下该代码实际上会做一些讨厌的事情。但为了清楚起见，由于子表达式*(tree.myLeft)和*(tree.myRight): 这些表达式正在取消引用空指针，您的代码是非法的，这绝不是合法的。您收到的有关&tree测试的警告消息只是先前错误的症状。

推荐阅读