证明具有相同的顺序和预订遍历的二进制树是相同的？ [英] Prove that binary trees with the same inorder and preorder traversals are identical?

问题描述

有人知道如何证明如果两个二进制树具有相同的顺序和预订遍历，那么它们是相同的？ （或许通过显示你不能有两个不同的二进制树，具有相同的排序和预订遍历）

Does anybody know how to prove that if two binary trees have the same inorder and preorder traversals, then they are identical? (perhaps by showing that you can't have two different binary trees with identical inorder and preorder traversals)

或者，显示一个会反驳这种情况，或显示为什么可以不要这样做？

Alternatively, show a case that would disprove this, or show why can't it be done?

（我承认，这纯粹是学术性的，但不是作业或任何东西，我的本能告诉我，这是真的，

(I'll admit, this is purely academic but it's not homework or anything. My instincts tell me that it's true, but I don't think I ever did any proofs on graphs.)

推荐答案

基本思想是如何按照给定的顺序重构二叉树并且预先遍历。

The basic idea is how to reconstruct a binary tree by the given inorder and preorder traversals.

可以从排序和预订遍历中重构只有一个二进制树。

It's possible to reconstruct only one binary tree from the inorder and preorder traversals.

请参阅：

• 
  的非递归算法从
  遍历重建二叉树（纸）


• 重建一棵树从它的
  预订和后期列表（SO问题）

• Nonrecursive algorithms for reconstructing a binary tree from its traversals (paper)
• reconstructing a tree from its preorder and postorder lists (SO question)

这篇关于证明具有相同的顺序和预订遍历的二进制树是相同的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！