如何使用{pre，in，post}命令遍历结果重建BST

Question

我们知道预定序，遍历序和遍历序。什么算法会重建BST？

Answer 1

因为是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类似。

Answer 2

我个人发现但丁的回答有点难以遵循。我通过解决方案工作，发现它与此处发布的内容类似。http://geeksforgeeks.org/?p=6633

复杂性是O（N^2）。

这里的建筑使用后序遍历树的另一种方法：http://www.technicallyidle.com/2011/02/15/build-binary-search-tree-using-post-order-traversal-trace/

希望这有助于

Answer 3

对于二叉树要么序+序或+序需要后序的重建。正如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; 
} 

Answer 4

这里是一个红宝石递归溶液

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