C++ 在打印 AVL 树元素时删除最后一个逗号

Question

我知道有人问过类似的问题，但我似乎找不到通过递归调用的函数进行打印的答案。我正在尝试打印 AVL 树的前序、后序和中序遍历，并递归地实现了这些功能。

即

void inOrder(Node* root)
{
    if(root != nullptr) {
        inOrder(root->left);
        cout << root->data << ", ";
        inOrder(root->right);
    }
}

除最后一个值外，数据应以逗号分隔打印，但我不确定该怎么做。我已经进行了研究，但在递归遍历 AVL 树时找不到任何似乎适用的东西。这是可能的还是我应该在没有递归的情况下实现这些功能？

Answer 1

做一个内部实现函数，维护一个flag，表示要输出的数据项是否是第一个。然后为除第一个以外的所有项目在输出前加上逗号。

void inOrderImpl(Node* root, bool& first)
{
    if(root != nullptr) {
        inOrderImpl(root->left, first);
        if (first)
            first = false;
        else
            cout << ", ";
        cout << root->data;
        inOrderImpl(root->right, first);
    }
}

void inOrder(Node* root)
{
    bool first = true;
    inOrderImpl(root, first);
}

Answer 2

我通常用于此类事情的模式是使用我在循环中更改的分隔符指针。第一次迭代是 ""，所以什么都不打印，随后的每次迭代都打印分隔符。对于您的递归情况，它将作为参数传递，如下所示：

void inOrder(Node* root, char ** sep)
{
    if(root != nullptr) {
        inOrder(root->left, sep);
        cout << **sep << root->data;
        *sep = ", ";
        inOrder(root->right, sep);
    }
}

这样称呼它：

char * sep = "";
inOrder(root, &sep);

循环看起来好多了。主要优点是在每个循环中没有 if/else 分支，只是一个快速的指针赋值来更新分隔符。

Answer 3

正如我的评论所建议的那样，编写执行任何 BST 遍历的代码的一种雄心勃勃（且更好）的方法是使用更通用的方法：

template <typename Fn>
void inOrder(Node* root, Fn& func)
{
    if(root != nullptr) 
    {
        inOrder(root->left, func);
        func(root);
        inOrder(root->right, func);
    }
}

鉴于以上内容，您基本上可以做任何事情，因为 func 将使用 root 的当前值调用。

那么这对我们有什么帮助呢？现在考虑以下内容：

struct TreePrinter
{ 
   bool initial = true; 
   void operator()(Node *root)
   {
     if ( initial )
        initial = false;
     else
        std::cout << ",";
    std::cout << root->data;
   }
};

以上是覆盖了 operator() 的 class。这样我们就可以把this传递给遍历函数，遍历函数直接调用即可。

请注意 initial 是在 TreePrinter 对象中设置的状态。

然后是这样实现的：

TreePrinter tp;
Node root;
//...
inOrder(&root, tp);

这里是live example using a dummy BST.

所以你不仅可以打印一个逗号，还可以提供任何可调用对象（函数指针、函数对象、lambda 等），基本上可以使用传入的 root 来做任何需要做的事情完成。

C++ 在打印 AVL 树元素时删除最后一个逗号

C++ Remove last comma when printing AVL tree elements

c++

recursion

avl-tree