当前位置:编程学习 > C/C++ >>

UVa 548 - Tree 二叉树的重建——中序遍历与后续遍历进行建树

题目大意:
给两个组数字,都是在同一棵二叉树上的,第一组是按中序遍历(inorder)顺序输出的,第二组是按后序遍历(postorder)输出的, 根据这两组数据构建出原来的二叉树,然后计算从根结点到每个叶子结点的路径上的数字之和, 输出最小之和。

样例输入:
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

样例输出:
1
3
255

分析:
这题就是运用了二叉树重建, 以及遍历。
二叉树的遍历:先序遍历,中序遍历,后序遍历
只要有一个中序序列再加上另一个序列就可唯一地重建原来二叉树。
进行了二叉树重建之后,只要对这棵二叉树进行搜索, 取得各个路径之和,然后找出最小的那个和即可。


由中序遍历 分别和前序遍历,后序遍历进行建树的方法:
[cpp] 
// 由中序和后序遍历序列进行建树, 返回根结点指针 
Node * InPostCreateTree(int *mid,int *post,int len){ 
    if(len == 0) 
        return NULL; 
    int i=len-1; 
    while(post[len-1] != mid[i]) 
        --i; 
    Node *h=NewNode(); 
    h->data=post[len-1]; 
    h->left=InPostCreateTree(mid,post,i); 
    h->right=InPostCreateTree(mid+i+1,post+i,len-i-1); 
    return h; 

  
// 由前序和中序遍历序列进行建树, 返回根结点的指针 
Node * PreInCreateTree(int *mid,int *pre,int len)   //n标识s2的长度 
{  
    if(len==0) 
        return NULL; 
     
    int i = 0; 
    while(*mid != pre[i]) 
    ++i; 
 
    Node *h=NewNode(); 
    h->data= *mid; 
    h->left  = PreInCreateTree(mid+1, pre, i); 
    h->right = PreInCreateTree(mid+i+1, pre+i+1, len-i-1); 
    return h; 

 

AC代码:
[cpp]
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<vector> 
using namespace std; 
const int MAXN = 10005; 
int inOrder[MAXN], postOrder[MAXN], nIndex; 
 
class Node{ 
public: 
    int data; 
    Node *left; 
    Node *right; 
}; 
 
int nodeIndex; 
Node node[MAXN]; 
vector<int>result; 
vector<Node*>pResult; 
bool flag; 
int ans; 
 
inline Node* NewNode(){ 
    node[nodeIndex].left = NULL; 
    node[nodeIndex].right = NULL; 
    return &node[nodeIndex++]; 

  
inline void input(){ 
    nIndex=1; 
    while(getchar()!='\n')  
        scanf("%d", &inOrder[nIndex++]); 
    // 输入第二行,后序遍历 
    for(int i=0; i<nIndex; ++i)  
        scanf("%d", &postOrder[i]); 
}  
 
// 由中序和后序遍历序列进行建树, 返回根结点指针 
Node * InPostCreateTree(int *mid,int *post,int len){ 
    if(len == 0) 
        return NULL; 
    int i=len-1; 
    while(post[len-1] != mid[i]) 
        --i; 
    Node *h=NewNode(); 
    h->data=post[len-1]; 
    h->left=InPostCreateTree(mid,post,i); 
    h->right=InPostCreateTree(mid+i+1,post+i,len-i-1); 
    return h; 

 
void dfs(Node *root, int n){ 
    if(!root->left && !root->right){ 
        result.push_back(n+root->data); 
        pResult.push_back(root); 
        return ; 
    } 
    if(root->left) dfs(root->left, n+root->data); 
    if(root->right) dfs(root->right, n+root->data); 

 
int main(){ 
    freopen("input.txt","r",stdin); 
    while(~scanf("%d", &inOrder[0])){ 
        input(); 
        nodeIndex = 0; 
        Node *root = InPostCreateTree(inOrder, postOrder, nIndex); 
        result.clear(); 
        pResult.clear(); 
        dfs(root, 0); 
        int minPos = 0; 
        for(int i=1; i<result.size(); ++i) 
            if(result[i] < result[minPos]) minPos=i; 
         
        printf("%d\n",pResult[minPos]->data); 
    }   
    return 0; 

 

作者:shuangde800
补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,