我最近意识到,虽然在我的生活中使用了BST,但我甚至都没有考虑过使用任何东西而是使用Inorder遍历(虽然我知道并且知道调整程序使用前/后顺序遍历是多么容易).
在意识到这一点之后,我拿出了一些旧的数据结构教科书,并寻找了预订和后序遍历的有用性背后的推理 - 但他们并没有说太多.
什么时候实际使用预订/后期订单的一些例子？什么时候比按顺序更有意义？
在我看来,Pre-order遍历和DFS与我们以深度方式遍历叶节点的两种情况相同.如果我错了,有人可以纠正我吗？
提前致谢!
我对不同网站上的一些文章非常困惑,这些文章是关于构建Binary Search Tree任何一个遍历(pre,post或in-order),或者它们中任意两个的组合.例如,在这个页面上,它表示给定pre,post或level顺序遍历,以及in-order遍历,可以构造BST.但是在这里和那里,他们向我们展示了BST从pre-order单独构建一个.此外,他们在这里向我们展示了如何构建BST来自给定pre和post-order遍历.在其他一些网站中,我找到了一个BST仅从post-order遍历构建一个解决方案的解决方案.
现在我知道,给定inorder和pre-order遍历,可以独特地形成一个BST.至于我提供的第一个链接,虽然他们说我们不能构造BSTfrom pre-order和post-order,我不能只是对post-order数组进行排序以获得它的inorder遍历,然后使用它和pre-order数组来形成BST？这与第4个链接中的解决方案相同,还是不同？pre-order只有给出,我可以排序,以获得in-order,然后使用它和pre-order得到BST.同样,这是否必须与链接2和3的解决方案不同？
具体来说,什么足以独特地产生BST？如果不需要in-order唯一性,那么我可以简单地对其进行排序以获得遍历,并以BST递归方式从其中构建N个可能的中的一个.
最近,我的问题被标记为重复,就像这样,即使它们不是.所以,让我先从下面开始,然后我将解释我的问题.
为什么这个问题不重复？
我不是在询问如何在顺序和前序遍历时创建二叉树.我要求证明,inorder + preorder遍历定义了一个唯一的二叉树.
现在,原来的问题.我去面试,面试官问我这个问题.我被困住了,无法继续.:|
问题: 给定二进制树的inorder和preorder遍历.证明给定数据只有一个二叉树.换句话说,证明两个不同的二叉树不能具有相同的顺序和前序遍历.假设树中的所有元素都是唯一的(感谢@envy_intelligence指出这个假设).
我尝试使用例子说服采访者,但采访者要求数学/直觉证明.任何人都可以帮我证明吗？
检查2个树节点是否相关(即祖先 - 后代)
而已.我将在下面讨论我的解决方案(方法).如果你想先考虑自己,请停止.
对于预处理,我决定做一个预订(先递归遍历root,然后是子),并给每个节点一个标签.
让我详细解释标签.每个标签将由逗号分隔的自然数组成,如"1,2,1,4,5" - 此序列的长度等于(节点的深度+ 1).例如,根的标签是"1",root的子节点将具有标签"1,1","1,2","1,3"等.下一级节点将具有类似"1,1,1"的标签. ","1,1,2",......,"1,2,1","1,2,2",......
假设节点的" 订单号 "是其父节点的子节点列表中的"该节点的从1开始的索引 ".
通用规则:节点的标签由其父标签后跟逗号和节点的" 订单号 "组成.
因此,为了回答O(1)中两个节点是否相关(即祖先 - 后代),我将检查其中一个节点的标签是否是另一个标签的" 前缀 ".虽然我不确定这些标签是否可以被认为占据O(N)空间.
预计会有任何批评者或其他方法.
我得到了严格二叉树的后序遍历，并被要求找到它的前序遍历。通常，我会先构建树，然后找到前序遍历。但是，我想知道是否有任何方法可以在不实际构建树的情况下找到预序遍历。
我知道你可以在给出它的顺序和前序遍历作为字符串时重建二叉树,但是只有在给定顺序遍历时才能找到后序和/或preoder遍历吗？
顺序、前序和后序这些名称背后的逻辑是什么？他们为什么这么称呼？
为了。为什么用“在”这个词，“在”是什么？
预购。“Pre”，意思是“前一个”，但是前一个是什么？
后订单。“Post”的意思是“之后”，但是之后呢？
我知道以前有一些线程询问如何使用这些顺序等遍历一棵树。请注意，这不是我在这里问的问题，因此这不是一个重复的问题。我想问的是这些名字的含义是什么。为什么他们被这样称呼。
对于二叉树，广度优先搜索遍历（BFS）是否与预序遍历相同？我对这两种不同类型的遍历有点困惑。任何人都可以向我解释一下吗？此外，预序遍历与深度优先搜索遍历(DFS) 相比如何？
非常感谢！
我使用本书中描述的二叉树 解决算法和数据结构问题
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
已经存在如下定义的预序遍历方法.
def preorder(tree):
if tree:
print(tree.self.key)
preorder(tree.getLeftChild())
preorder(tree.getRightChild())
我只想添加访问的节点列表的返回值.所以我可以做点什么
for i in preorder(tree):
etc...
我无法从递归方法返回列表.一旦它到达'返回',我就尝试使用变量,递归就会停止
return [tree.self.key] + preorder()
要么
yield ...
有任何想法吗？