c++ - 旋转二叉树

Question

我正在尝试打印非静态二叉树。它确实打印但向左旋转。我无法找到一种方法来纠正此问题并使其直立旋转。 5 是根节点。代码:

template <class dataType>
void displaybinarytree(BinaryTree <dataType> * p, int indent)
{
if(p != NULL) {
    if(p->right()) {
        displaybinarytree(p->right(), indent+4);
    }

    if (indent) {
        cout << setw(indent) << ' ';
    }

    if (p->right()){
        cout<<" /\n" << setw(indent) << ' ';
    }

    cout<< p->getData() << "\n ";

    if(p->left()) {
        cout << setw(indent) << ' ' <<" \\\n";
        displaybinarytree(p->left(), indent+4);
    }
  }
}

输出:

预期输出:

Answer 1

递归方法不适用于基于行的输出，其中一行由来自多个子树的项目组成。

您应该切换到广度优先遍历，在其中为每个树级别创建一个工作集。您可能需要预先计算较低树级别的空间要求，以便在较高级别输出所需的对齐方式。

一小段起始代码，它并没有真正将树显示为树，但至少在正确的行中显示了每个节点。

void displaybinarytree(BinaryTree <int> * p, int indent)
{
    deque<BinaryTree<int>*> current;
    deque<BinaryTree<int>*> next;
    next.push_back(p);

    while (!next.empty())
    {
        current.swap(next);
        while  (!current.empty())
        {
            BinaryTree<int>* node = current.front();
            current.pop_front();
            if (node->left)
            {
                next.push_back(node->left);
            }
            if (node->right)
            {
                next.push_back(node->right);
            }
            // instead of a single space, appropriate spacing is needed
            cout << " " << node->data;
        }
        // instead of a single newline, appropriate spacing and connector characters / \ are needed
        cout << endl;
    }
}

请参阅代码内注释以了解此代码中缺少的内容。我用 int 替换了你的 dataType 并使用原始字段而不是 getter 函数，因为它对这个概念并不重要。