0

我已经为此苦苦挣扎了几个小时，所以在不断地谷歌搜索并发现没什么可继续的之后，我终于决定看看 SO 可以为我的最新 CS hw 提供什么样的帮助。

我们的任务是读取和存储二叉树，它们以如下格式提供给我们： ( (root) (left_subtree) (right_subtree))

每组匹配的parens代表一棵树，第一个是根，接下来是左子树，然后是右子树。如果子树是叶子，则不需要被括号包围，但可以。为了澄清我的意思，请参阅以下示例，这些示例都是代码块下方所示树的所有有效表示。

(A B C)
(A (B) C)
(A B (C))
((A) (B) (C))

一颗树
（来源：otterbein.edu）

对于一个更复杂的示例，可以更好地说明定义的递归性质，以下树的一个可能字符串是：

(F(B A (D C E)) (G () (I (H))))

注意，在F的右子树[即“(G()(I(H)))”]中，G后面的“()”是必要的，用来表示空的左孩子——但还要注意， G ["(I (H))"] 也可以更简单地表示为 "(IH)"。

一棵更大的树

我已经完成了一个二叉树类（和匹配的 TreeNode 类），除了从这个输入构建树的基本功能，但我似乎无法理解如何准确地解析字符串。我对如何做到这一点有一个大致的了解——至少，递归是如何工作的——但是如何将问题分解成更小的部分让我头疼。

//pseudocode musings
TreeNode* Tree::buildFromString(string s){
TreeNode* temp = NULL
if ( the string doesn't represent an empty tree )
  temp = new TreeNode
  temp->data = part of s representing root
  temp->leftChild = buildFromString( part of s representing left subtree)
  temp->rightChild = same as above, but with right subtree     
}
return temp;

我对递归本身没有问题——这是有道理的，在你的脑海中粗略地追踪它并不难。基本情况有效 - 一旦到达叶节点，您就退出递归并返回调用，并在返回时链接子树。

但是我不知道如何在代码中将问题分解成更小的部分，这显然是递归的全部意义所在。我想创建原始的子字符串以传递给递归调用，但我似乎无法理解如何获得适当的部分。

有什么想法吗？

4

1 回答 1

1

你是对的，缺少的是：

  • 如果字符串以'（'开始，它开始一棵树，'A'之后是根
  • 如果它是，例如，'B'，那是一片叶子
  • 如果是'('，递归
  • 如果next是')'，关闭上面启动的节点
于 2013-02-14T02:19:13.227 回答