PAT_A1099#Build A Binary Search Tree

Source:

PAT A1099 Build A Binary Search Tree (30 分)

Description:

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.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤) 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 − 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

Keys:

二叉树的建立
二叉树的遍历
二叉查找树（Binary Search Tree）

Code:

 /*

 Data: 2019-06-26 16:22:18

 Problem: PAT_A1099#Build A Binary Search Tree

 AC: 21:23

 题目大意：

 BST定义：lchild < root <= rchild

 给定一棵BST的树形，将所给序列填入BST中，并打印层次遍历

 输入：

 第一行给出，结点数N<=100

 接下来N行，给出第i号结点，左孩子的序号，右孩子的序号（0~N-1，-1为空，0为根）

 最后一行，N个数

 输出：

 层次遍历

 基本思路：

 建立静态树，构建根结点与左右孩子之间的关系

 中序遍历静态树，由于BST的中序遍历就是从小到大递增的序列，把排序好的序列依次填入树的结点中

 层次遍历并打印输出

 */

 #include<cstdio>

 #include<queue>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const int M=;

 priority_queue<int,vector<int>,greater<int> > bst;

 struct node

 {

     int data;

     int lchild,rchild;

 }tree[M];

 void InOrder(int root)

 {

     if(root == -)

         return;

     InOrder(tree[root].lchild);

     tree[root].data = bst.top();

     bst.pop();

     InOrder(tree[root].rchild);

 }

 void Travel(int root, int len)

 {

     queue<int> q;

     q.push(root);

     while(!q.empty())

     {

         root = q.front();

         q.pop();

         printf("%d%c", tree[root].data, --len==?'\n':' ');

         if(tree[root].lchild != -)

             q.push(tree[root].lchild);

         if(tree[root].rchild != -)

             q.push(tree[root].rchild);

     }

 }

 int main()

 {

 #ifdef ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif // ONLINE_JUDGE

     int n,x;

     scanf("%d", &n);

     for(int i=; i<n; i++)

         scanf("%d %d", &tree[i].lchild,&tree[i].rchild);

     for(int i=; i<n; i++)

     {

         scanf("%d", &x);

         bst.push(x);

     }

     InOrder();

     Travel(,n);

     return ;

 }

巴特西

PAT_A1099#Build A Binary Search Tree

Source:

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

Code:

最新文章

热门文章