1099. Build A Binary Search Tree (30)

向右看齐 2022-05-30 03:42 140阅读 0赞

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.

Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.

![h8_nkqjeu5lglo.jpg][]

**Input Specification:**

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format "left\_index right\_index", provided that the nodes are numbered from 0 to N-1, and 0 is always the root. If one child is missing, then -1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.

**Output Specification:**

For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.

**Sample Input:**

9
    1 6
    2 3
    -1 -1
    -1 4
    5 -1
    -1 -1
    7 -1
    -1 8
    -1 -1
    73 45 11 58 82 25 67 38 42

**Sample Output:**

58 25 82 11 38 67 45 73 42

--------------------

题目大意：

代码：

#include<stdio.h>
    #include<algorithm>
    #include<queue>
    using namespace std;
    struct node
    {
        int data;
        int lchild,rchild;
    }tree[110];
    int arr[110];
    int num=0;
    void midtraverl(int index)
    {
        if(index!=-1)
        {
           midtraverl(tree[index].lchild);
           tree[index].data=arr[num++];
           midtraverl(tree[index].rchild);
        }
    }
    void leveltraverl(int index)
    {
        queue<struct node> q;
        q.push(tree[index]);
        int flag=0;
        while(!q.empty())
        {
            struct node tmp=q.front();
            q.pop();
            if(tmp.lchild!=-1)
            q.push(tree[tmp.lchild]);
            if(tmp.rchild!=-1)
            q.push(tree[tmp.rchild]);
            if(flag==0)
            {
                printf("%d",tmp.data);
                flag=1;
            }
            else
            {
                printf(" %d",tmp.data);
            }
        }
    }
    int main()
    {
        int i,j,n,m,k,t;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
           scanf("%d %d",&tree[i].lchild,&tree[i].rchild);
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",&arr[i]);
        }
        sort(arr,arr+n);
        midtraverl(0);
        leveltraverl(0);
        return 0;
    }

[h8_nkqjeu5lglo.jpg]: http://nos.patest.cn/h8_nkqjeu5lglo.jpg