PAT_A1099#Build A Binary Search Tree-白红宇

PAT_A1099#Build A Binary Search Tree

阅读量：5951 次

发布时间：2019-06-19

本文共 2960 字，大约阅读时间需要 9 分钟。

Source:

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

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:

91 62 3-1 -1-1 45 -1-1 -17 -1-1 8-1 -173 45 11 58 82 25 67 38 42

Sample Output:

58 25 82 11 38 67 45 73 42

Keys:

二叉树的建立

二叉树的遍历

Code:

1 /* 2 Data: 2019-06-26 16:22:18 3 Problem: PAT_A1099#Build A Binary Search Tree 4 AC: 21:23 5  6 题目大意： 7 BST定义：lchild < root <= rchild 8 给定一棵BST的树形，将所给序列填入BST中，并打印层次遍历 9 输入：10 第一行给出，结点数N<=10011 接下来N行，给出第i号结点，左孩子的序号，右孩子的序号（0~N-1，-1为空，0为根）12 最后一行，N个数13 输出：14 层次遍历15 16 基本思路：17 建立静态树，构建根结点与左右孩子之间的关系18 中序遍历静态树，由于BST的中序遍历就是从小到大递增的序列，把排序好的序列依次填入树的结点中19 层次遍历并打印输出20 */21 #include
     
      22 #include
      
       23 #include
       
        24 #include
        
         25 using namespace std;26 const int M=110;27 priority_queue
         
          
           ,greater
           
             > bst;28 struct node29 {30 int data;31 int lchild,rchild;32 }tree[M];33 34 void InOrder(int root)35 {36 if(root == -1)37 return;38 InOrder(tree[root].lchild);39 tree[root].data = bst.top();40 bst.pop();41 InOrder(tree[root].rchild);42 }43 44 void Travel(int root, int len)45 {46 queue
            
              q;47 q.push(root);48 while(!q.empty())49 {50 root = q.front();51 q.pop();52 printf("%d%c", tree[root].data, --len==0?'\n':' ');53 if(tree[root].lchild != -1)54 q.push(tree[root].lchild);55 if(tree[root].rchild != -1)56 q.push(tree[root].rchild);57 }58 }59 60 int main()61 {62 #ifdef ONLINE_JUDGE63 #else64 freopen("Test.txt", "r", stdin);65 #endif // ONLINE_JUDGE66 67 int n,x;68 scanf("%d", &n);69 for(int i=0; i