從有序和後序遍歷構造二叉樹

我遇到了一個真正讓我感興趣的問題，但我不確定自己完全理解如何完成手頭的任務：設計一個算法來構造二叉樹兩個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

從有序和後序遍歷構造二叉樹

回答

相關問題