PAT 1099

题目 ： Build A Binary Search Tree

分值 ： 30
难度 ： 中等题
思路 ： 按照他的输出构建树,然后把数字按照升序中序遍历插入,最后层序打印出来.
坑点 ： 时隔一个月,sort什么时候升序忘记了,然后在处理节点和节点指针时不够老练,要脱离ide编程

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 #include <iostream>
#include <algorithm>
using namespace std ;
bool cmp(int a , int b )
{
    return a < b ;
}
int arr[101] ;
int cur = 0 ;
typedef struct Node{
    int self ;
    Node* left ;
    Node* right ;
}Nodes;
Nodes data[101];
void insert(int pos , int l ,int r )
{
    data[pos].self = pos ;
    if(l!= -1)
        data[pos].left =  &data[l] ;
    else data[pos].left =NULL ;
    if(r!= -1 )
        data[pos].right = &data[r];
    else data[pos].right = NULL ;
    return ;
}
void inorder(Nodes* pos)
{
    if(pos)
    {
        inorder(pos->left);
        //cout << pos->self <<" ";
        data[pos->self].self = arr[cur++] ;
        inorder(pos->right) ;
    }
}
int main() {
    int N ;
    cin >> N ;
    Nodes* head = &data[0] ;
    for(int i = 0 ; i< N ; i++)
    {
        int c1,c2 ;
        cin >> c1 >>c2 ;
        insert(i , c1,c2) ;
    }
    for(int i= 0 ; i< N ; i++)
        cin >> arr[i] ;
    sort(arr ,arr+N , cmp) ;
    //for(int i = 0 ; i< N ; i++)
      //  cout << arr[i] <<" " ;
    inorder(head);
    Nodes Queen[101] ;
    int temp= 0, count =0 ;
    Queen[count++] = data[0] ;
    //cout << endl ;
    while(temp < count )
    {
        if(temp)
            cout << " " ;
        cout << Queen[temp].self;
        if(Queen[temp].left!= NULL )
            Queen[count++] = *Queen[temp].left ;
        if(Queen[temp].right!= NULL)
            Queen[count++] = *Queen[temp].right ;
        temp ++ ;
    }

}