algorithm - 来自中序和级序遍历的二叉树？

我们能否证明可以从二叉树的中序遍历和层序遍历中明确地构造一棵二叉树？

我正在考虑通过对级别数进行归纳来证明。

基本情况:具有 1 或 2 层的树。这些案例一目了然。

假设这适用于具有 l 层的树。也就是说:可以从它的中序遍历和层序遍历中明确地构造一棵具有 l 层的二叉树。

归纳案例:证明这适用于具有 l+1 层的树。不清楚在这种情况下如何进行。任何帮助将不胜感激。

最佳答案

不确定证据，但这样做的方法很简单，

f(inorder, levelorder):
      if length(levelorder) == 0:
          return None
      root = levelorder[0]#set root to first element in levelorder
      subIn1, subIn2 = partition(inorder, levelorder[0]) #partition inorder based on root
      subLevel1 = extract(levelOrder, subIn1)#remove elements in level order not in subIn1
      subLevel2 = extract(levelOrder, subIn2)#remove elements in level order not in subIn2
      root->left = f(subIn1, subLevel1)
      root->right = f(subIn2, subLevel2)
      return root

为了证明这一点，您必须证明在有序遍历中根节点的左序列是左子树的有序遍历，然后对于右子树也是有序遍历。是的，但要证明很乏味。

您还需要显示为子树维护了levelorder。也是正确的，但要证明很乏味。

哦，是的，您可能必须证明级别顺序遍历的第一个元素是树的根，但这应该来自定义。

关于algorithm - 来自中序和级序遍历的二叉树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4575719/