如何使用stringstream C++递归打印出二叉搜索树中的所有节点

Question

我想使用字符串流和递归来打印二叉搜索树中所有节点的内容。问题是当我使用这段代码时，只显示根目录的内容。我知道原因是每次我递归调用函数 InOrder(BSTNode* bst_node) 时，都会再次创建我的 stringstream 变量。我可以对我的代码做些什么来解决这个问题，同时仍然使用 stringstream 进行输出？

这是我的代码：

string BSTree::InOrder(BSTNode* bst_node) {
  stringstream ss;
  if (root_ ==  NULL) {
    return "";
  } else {
    if (bst_node->GetLeftChild() != NULL) {
      InOrder(bst_node->GetLeftChild());
    }
    ss << bst_node->GetContents() << " ";
    if (bst_node->GetRightChild() != NULL) {
      InOrder(bst_node->GetRightChild());
    }
  }
  return ss.str();
}

Answer 1

也许是这样的？

string BSTree::InOrder(BSTNode* bst_node)
{
  if (!bst_node)
    return "";
  ostringstream ss;
  ss << InOrder(bst_node->GetLeftChild());
  ss << bst_node->GetContents() << " ";
  ss << InOrder(bst_node->GetRightChild());
  return ss.str();
}

或者，您可以传递相同的字符串流实例：

void BSTree::InOrderImpl(BSTNode* bst_node, ostringstream &ss)
{
  if (bst_node)
  {
    InOrderImpl(bst_node->GetLeftChild(), ss);
    ss << bst_node->GetContents() << " ";
    InOrderImpl(bst_node->GetRightChild(), ss);
  }
}

string BSTree::InOrder(BSTNode* bst_node)
{
  ostringstream ss;
  InOrder(bst_node, ss);
  return ss.str();
}

Answer 2

我对此毫不费力 - 通过引用此方法将字符串流作为参数传递：

static stringstream existingSSreference;
string BSTree::InOrder(BSTNode* bst_node, stringstream & ss = existingSSreference) {

  if (root_ ==  NULL) {
    return "";
  } else {
    if (bst_node->GetLeftChild() != NULL) {
      InOrder(bst_node->GetLeftChild(), ss);
    }
    ss << bst_node->GetContents();
    if (bst_node->GetRightChild() != NULL) {
      InOrder(bst_node->GetRightChild(), ss);
    }
  }
  return ss.str();
}

并且您想要在使用方法之前声明字符串流：

stringstream ss;
string myResult = bstreeObj->InOrder(bstNode, ss);

或者不传就直接使用

string myResult = bstreeObj->InOrder(bstNode);

这应该有效。最好在函数外定义stringstream，调用函数时传递。

编辑

正如 Ajay 所指出的，引用参数不能有默认值，除非我们传递一个实际存在的实例作为默认值（这样我们就可以保留省略第二个参数的可能性）。

Answer 3

简单：只需定义一个效用函数，其中 stringstream 作为参数传递：

void BSTree::InOrder(BSTNode *root, std::stringstream &ss)
{
  if (root == nullptr) { return; }
  InOrder(root->GetLeftChild(), ss)
  ss << root->GetContents() << " ";
  InOrder(root->GetRightChild(), ss)
}

string BSTree::InOrder(BSTNode* bst_node) {
  stringstream ss;
  InOrder(bst_node, ss);
  return ss.str();
}

请注意，仅实例化一个 stringstream 来转储整个树可能比为树的每个节点实例化一个 stringstream 更有效（如果您定义效用函数，就会发生这种情况）作为获取节点并返回字符串的东西）。

如何使用stringstream C++递归打印出二叉搜索树中的所有节点

How to recursively print out all the nodes in a binary search tree using stringstream C++

c++

recursion

inorder

binary-search-tree