我有一个完美的二叉树,它列举了后序方式.这种树的一个例子是
15
7 14
3 6 10 13
1 2 4 5 8 9 11 12
树的大小是我所知道的.我正在寻找一个公式或一个简单的算法,它将一个数字作为输入(我感兴趣的顶点的ID)并返回一个数字 - 父亲的ID.从顶部遍历树并获得结果非常容易O(log n).有更快的解决方案吗？我最感兴趣的是叶子,所以如果有特殊情况的解决方案,也可以带上它.
我对不同网站上的一些文章非常困惑,这些文章是关于构建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个可能的中的一个.
我理解预订,有序和后序树遍历算法就好了.(参考).我理解了一些用法:按顺序遍历二进制搜索树,预先克隆树.但我不能为我的生活提出一个现实世界的任务,我需要后序遍历才能完成.
能给我举个例子？并且:你能为我提供更好的预订遍历用途吗？
编辑:除了表达式树和RPN之外,还有谁可以给我一个例子吗？这真的是所有的后期订单都有用吗？
我有一个递归函数,在给定起始根节点的情况下返回所有子树节点.
private IEnumerable<Node> getAllNodesRecursively(Node subnode)
{
foreach (Node node in subnode.Nodes)
getAllNodesRecursively(node);
yield return subnode;
}
对于以下树结构:
A
|
+--B
|
+--C
| |
| +--D
|
+--E
当我尝试迭代时:
foreach (Node n in getAllNodesRecursively(a))
{
Console.WriteLine(n);
}
该函数返回唯一的A值.
我希望使用yield-return和递归,并检索Preorder中的元素(在本例中为A,B,C,D,E).
(如果我把收益率的回报放在foreach之前,那么foreach永远不会发生).
这可能吗？
我得到了严格二叉树的后序遍历，并被要求找到它的前序遍历。通常，我会先构建树，然后找到前序遍历。但是，我想知道是否有任何方法可以在不实际构建树的情况下找到预序遍历。
我知道你可以在给出它的顺序和前序遍历作为字符串时重建二叉树,但是只有在给定顺序遍历时才能找到后序和/或preoder遍历吗？
顺序、前序和后序这些名称背后的逻辑是什么？他们为什么这么称呼？
为了。为什么用“在”这个词，“在”是什么？
预购。“Pre”，意思是“前一个”，但是前一个是什么？
后订单。“Post”的意思是“之后”，但是之后呢？
我知道以前有一些线程询问如何使用这些顺序等遍历一棵树。请注意，这不是我在这里问的问题，因此这不是一个重复的问题。我想问的是这些名字的含义是什么。为什么他们被这样称呼。
考虑具有以下属性的二叉树:
树上的级别顺序遍历将生成1和0的字符串(通过在访问每个节点时打印奇怪的值).现在给定此字符串构造二叉树并在树上执行post order遍历.后订单字符串应该是程序的输出.
例如:输入字符串是
111001000.从中创建二叉树.然后在树上执行post order遍历,这将导致输出:001001011
问题的"症结"是仅从级别顺序字符串创建二叉树.我该怎么做？
我有一个预订遍历函数,如下所示:
void listInPreOrder(node* hd){
if(hd != NULL) {
printf("%d, ", hd->value);
listInPreOrder(hd->left);
listInPreOrder(hd->right);
}
}
这实际上是有效的,但我认为将它发布到订单就像这样简单
void listInPostOrder(node* hd){
if(hd != NULL) {
listInPreOrder(hd->left);
listInPreOrder(hd->right);
printf("%d, ", hd->value);
}
}
但遗憾的是,它并没有那么好用.我想知道如何解决这个问题,也许我正在做一些简单的错误.或许这是完全错误的.
我目前是一名学生，他的作业涉及将二叉树方法调整为通用树方法。我唯一的问题是，我对以下通用树的后序遍历是否正确？如果是这样，那么我知道我的算法正在工作，我只是无法正确掌握后序遍历的窍门，我觉得并认为该网站可以提供帮助。
B
--------------------|------------------
| | |
A ------D----- ---I---
| | | | |
C E G H L
|
F
我的结果是：ACEFGDHLIB