从有序和后序遍历构造二叉树

我遇到了一个真正让我感兴趣的问题，但我不确定自己完全理解如何完成手头的任务：设计一个算法来构造二叉树两个n长序列，已知是相同二叉树的有序和后序遍历的输出。从有序和后序遍历构造二叉树

到目前为止我已经完成了很多工作。下面是我的（相关）代码，但是我也希望能够识别没有二叉树存在的序列。我不知道如何检查这一点。有人能给我一个正确的方向吗？

node* build_tree(int in[], int inStart, int inEnd, 
       int post[], int postStart, int postEnd) { 
    if(inStart > inEnd || postStart > postEnd) 
     return NULL; 

    int rootValue = post[postEnd]; 
    node *tNode = new_node(rootValue); 

    // find the index of this node in in-order traversal 
    int inIndex = search(in, inStart, inEnd, rootValue); 

    // Using index in in-order traversal, construct left and right subtrees 
    tNode->left = build_tree(in, inStart, inIndex-1, post, postStart, postStart+inIndex-(inStart+1)); 
    tNode->right = build_tree(in, inIndex+1, inEnd, post, postStart + inIndex - inStart, postEnd - 1); 

    return tNode; 
} 

// Function to find index of value in arr[start...end] 
// The function assumes that value is present in in[] 
int search(int arr[], int start, int end, int value) { 
    int i; 
    for(i = start; i < end; i++) { 
     if(arr[i] == value) 
      return i; 
    } 

    return i; 
} 

// function that allocates a new node with the 
// given data and NULL left and right pointers 
node* new_node(int data) { 
    node* n = (node*)malloc(sizeof(node)); 
    n->data = data; 
    n->left = NULL; 
    n->right = NULL; 

    return n; 
}

来源

2014-11-04 user3270760

你的问题的说明是好的。因此，请注意算法，以便我们可以批评您的方法。如果你不这样做，你会被低估和/或关闭。 – Gene 2014-11-04 00:45:40

我添加了我的代码到目前为止，我认为它很接近。我只是不知道如何验证输出并证明它正在工作。 – user3270760 2014-11-04 01:00:50

只需遍历树中你要产生的顺序和后序，并将它们与输入进行比较！ – Gene 2014-11-04 02:09:01

AFAIK二进制树不是可能的是，给定的时序列，

1）两个序列是相同长度的不 - 我们可以检查数组长度

2）搜索中序序列中的后序数值失败 - 当搜索失败而不是返回i时（for循环后），应修改搜索函数以返回负值

3）给定序列不代表后序和序同一棵树的 - 通过基因建议遍历树，并检查序列

来源

2015-01-27 08:08:09 Somali

我的代码对于这个问题:)

int searchelement(vector<int> &v , int start ,int end,int val) 
{ 
    for(int i=start;i<=end;i++) 
    { 
    if(v[i]==val) 
    return i; 
    } 
    return -1; 
} 
TreeNode * abc(vector<int> &postorder, vector<int> &inorder , int start ,int end , int &index) 
{ 
    if(start>end) 
    return NULL; 
    int i = searchelement(inorder,start,end,postorder[index--]); 
    TreeNode * temp = new TreeNode(inorder[i]); 
    if(start==end) 
    { 
     return temp; 
    } 
    temp->right=abc(postorder,inorder,i+1,end,index); 
    temp->left =abc(postorder,inorder,start,i-1,index); 
    return temp; 
} 

main(){ 
    TreeNode * head =NULL; 
    int start=0,end=inorder.size()-1,index=0; 
    head= abc(preorder,inorder,start,end,index); 
}

来源

2015-06-09 17:57:39 krishana

感谢您的回答。你能提供一些关于你的代码如何工作的更多信息，或许是一些评论吗？ – JAL 2015-06-09 18:16:44

@JAL 1）它只是从后序向量中挑选元素，然后搜索中序向量中的元素并找到索引。 2）根据索引拆分inorder向量。 – krishana 2015-06-10 13:58:17

从有序和后序遍历构造二叉树

回答

相关问题