pat 甲级 1064 ( Complete Binary Search Tree ) (数据结构)

1064 Complete Binary Search Tree （30 分）

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input:

10

1 2 3 4 5 6 7 8 9 0

Sample Output:

6 3 8 1 5 7 9 0 2 4

重点在递归的过程建树

详见代码：

#include <iostream>

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

int a[1005];

int cnt[12]={-1,1,3,7,15,31,63,127,255,511,1023};

struct node

{

    int v;

    node *left=NULL,*right=NULL;

};

int mypow(int a,int b)

{

    int res=1;

    while(b--)res*=a;

    return res;

}

node* build(int l,int r,int num)

{

    if(l>r){return NULL;}

    if(l==r)

    {

        node *tt=new node();tt->v=a[l];

        return tt;

    }

    if(num<=0)return NULL;

    node *thi;

    int k1=0;

    while(cnt[k1+1]<num)k1++;

    int k2=k1+1;

    int rr=num-(cnt[k1]);

    int tmp=mypow(2,k2-2);

    if(rr>=tmp)

    {

        int lnum=cnt[k1];

        int rnum=num-lnum-1;

        int id=l+lnum;

        thi=new node();

        thi->v=a[id];

        thi->left=build(l,id-1,lnum);

        thi->right=build(id+1,r,rnum);

    }

    else {

        int lnum=num-1-cnt[k1-1];

        int rnum=cnt[k1-1];

        int id=l+lnum;

        thi=new node();thi->v=a[id];

        thi->left=build(l,id-1,lnum);

        thi->right=build(id+1,r,rnum);

    }

    return thi;

}

int main()

{

    //freopen("in.txt","r",stdin);

    cin>>n;

    for(int i=1;i<=n;i++)cin>>a[i];

    sort(a+1,a+1+n);

    int l=1;int r=n;

    node *head=build(l,r,n);

    queue< node* >q;

    while(!q.empty())q.pop();

    q.push(head);

    vector<int>ans;ans.clear();

    node *now;

    while(!q.empty())

    {

        now=q.front();q.pop();

        ans.push_back(now->v);

        if(now->left!=NULL)q.push(now->left);

        if(now->right!=NULL)q.push(now->right);

    }

    for(int i=0;i<ans.size();i++)

    {

        cout<<ans[i];if(i!=ans.size()-1)cout<<" ";

    }

    cout<<endl;

    return 0;

}

巴特西

pat 甲级 1064 ( Complete Binary Search Tree ) (数据结构)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

最新文章

热门文章