我们知道预定序,遍历序和遍历序。什么算法会重建BST?如何使用{pre,in,post}命令遍历结果重建BST
3
A
回答
11
因为是BST,所以in-order
可以从pre-order
或post-order
< 1>。其实,无论是pre-order
或post-order
只需要....
< 1>如果你知道的比较功能是什么
从pre-order
和in-order
,构建一个二叉树
BT createBT(int* preOrder, int* inOrder, int len)
{
int i;
BT tree;
if(len <= 0)
return NULL;
tree = new BTNode;
t->data = *preOrder;
for(i = 0; i < len; i++)
if(*(inOrder + i) == *preOrder)
break;
tree->left = createBT(preOrder + 1, inOrder, i);
tree->right = createBT(preOrder + i + 1, inOrder + i + 1, len - i - 1);
return tree;
}
背后的理由:
在预订中,第一个节点是根。找到有序的根。然后,树可以分为左和右。以递归方式进行。
与post-order
和in-order
类似。
0
我个人发现但丁的回答有点难以遵循。我通过解决方案工作,发现它与此处发布的内容类似。http://geeksforgeeks.org/?p=6633
复杂性是O(N^2)。
这里的建筑使用后序遍历树的另一种方法:http://www.technicallyidle.com/2011/02/15/build-binary-search-tree-using-post-order-traversal-trace/
希望这有助于
0
对于二叉树要么序+序或+序需要后序的重建。正如BST已经指出的那样,我们可以使用预先订购或者后续订购进行重建,因为排序中的任何一个都会给我们提供订单。
可以使用下面的函数,它是通过给定@brainydexter重建树的代码的修改,而不使用静态变量:
struct node* buildTree(char in[],char pre[], int inStrt, int inEnd,int preIndex){
// start index > end index..base condition return NULL.
if(inStrt > inEnd)
return NULL;
// build the current node with the data at pre[preIndex].
struct node *tNode = newNode(pre[preIndex]);
// if all nodes are constructed return.
if(inStrt == inEnd)
return tNode;
// Else find the index of this node in Inorder traversal
int inIndex = search(in, inStrt, inEnd, tNode->data);
// Using index in Inorder traversal, construct left and right subtress
tNode->left = buildTree(in, pre, inStrt, inIndex-1,preIndex+1);
tNode->right = buildTree(in, pre, inIndex+1, inEnd,preIndex+inIndex+1);
return tNode;
}
0
这里是一个红宝石递归溶液
def rebuild(preorder, inorder)
root = preorder.first
root_inorder = inorder.index root
return root unless root_inorder
root.left = rebuild(preorder[1, root_inorder], inorder[0...root_inorder])
root.right = rebuild(preorder[root_inorder+1..-1], inorder[root_inorder+1..-1])
root
end
并举一个例子
class Node
attr_reader :val
attr_accessor :left, :right
def initialize(val)
@val = val
end
def ==(node)
node.val == val
end
def inspect
"val: #{val}, left: #{left && left.val || "-"}, right: #{right && right.val || "-"}"
end
end
inorder = [4, 7, 2, 5, 1, 3, 8, 6, 9].map{|v| Node.new v }
preorder = [1, 2, 4, 7, 5, 3, 6, 8, 9].map{|v| Node.new v }
tree = rebuild(preorder, inorder)
tree
# val: 1, left: 2, right: 3
tree.left
# val: 2, left: 4, right: 5
tree.left.left
# val: 4, left: -, right: 7
相关问题
- 1. BST级别遍历
- 2. BST遍历预订
- 3. 遍历bash命令
- 4. 迭代后序遍历bst?
- 5. BST字符串遍历
- 6. Windows命令行:如何遍历列表?
- 7. python如何遍历二叉搜索树使用inorder/pre/post /没有递归?
- 8. 如何使用递归工作遍历BST?
- 9. 遍历数据库结果,使用number_format()
- 10. 如何循环遍历结果?
- 11. Neo4j Cypher:如何遍历ExecutionResult结果
- 12. 遍历$ _ POST
- 13. jquery-in-place-editor pre post hooks?
- 14. 结果集不能遍历
- 15. 遍历搜索结果列
- 16. 遍历equal_range结果集
- 17. 遍历结果集bs4
- 18. mysqli的遍历结果集
- 19. 如何重定向结果“!find ...”命令把lftp命令
- 20. 如何使某个命令重复一遍又一遍?
- 21. 使用命令的结果
- 22. 如何使用if/else语句遍历sql结果数组?
- 23. 了解BST的Inorder遍历的逻辑
- 24. 使用in命令创建一个SQL视图命令
- 25. 如何遍历linq-to-sql查询结果的结果并追加结果?
- 26. 如何遍历使用thymeleaf
- 27. 遍历命令行参数对
- 28. 使用按钮遍历mysql结果集使用php
- 29. Python:二叉树类:用遍历重建
- 30. diff命令+如何使用+如何解释结果
关于第一句话:假设你知道什么是公司重新功能是... – 2011-03-20 15:33:21
@Moron,酷点。 – 2011-03-20 16:17:41
姜先生,请解释为什么对于正确的孩子,预购从'preOrder + i + 1'开始 – brainydexter 2011-03-22 01:20:50