PAT Build A Binary Search Tree

1256 ワード

PAT データ構造∨

与えられた二叉の木に対して、このシーケンスの数字をこの二叉の木に入れて、この二叉の木を二叉の木に並べ替える.
考え方:
1)この二叉樹がBST->二叉樹であることを保証する.シーケンスはBST->順序良く挿入されたツリーの中から順に順序付けられている.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll __int64
using namespace std;
const int INF=0x3fffffff;

struct Node
{
    int data;
    int l,r;
}tree[205];
int n;
int a[205];
int k;

void InorderInsert(int root)
{
    if(root!=-1){
        InorderInsert(tree[root].l);
        tree[root].data=a[k++];
        InorderInsert(tree[root].r);
    }
}

void TraversalOutput(int root)
{
    k=0;
    queueq;
    q.push(0);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        if(i!=-1){
            cout<>n;
    for(int i=0;i>l>>r;
        tree[i].l=l;
        tree[i].r=r;
    }
    for(int i=0;i>a[i];
    }
    sort(a,a+n);
    k=0;
    InorderInsert(0);
    TraversalOutput(0);
    return 0;
}

【題解】Simpsons'Hdden Talents HDU-2594⭐⭐ 【拡張KMP】