Fork me on GitHub

PAT(甲级)渡劫(十)-Build A Binary Search(30)


PAT(甲级)渡劫(十)-Build A Binary Search(30)

算法思想:

首先在输入数据的时候就构造二叉树的结构,然后将输入的数据进行排序,将排序好的数字在中序遍历中赋值给构造好的二叉树,最后用层次遍历输出即可。

代码如下:

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define N 200
using namespace std;

struct TNode{
int data;
struct TNode *lchild,*rchild;
}Tree[N];
int key[N];
int cnt = 0;
void inOrder(TNode *T){
if(T != NULL){
inOrder(T->lchild);
T->data = key[cnt++];
inOrder(T->rchild);
}
}

int main(){
//freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i = 0 ; i <n ; i++){
int a,b;
scanf("%d%d",&a,&b);
if(a != -1){
Tree[i].lchild = &Tree[a];
}else{
Tree[i].lchild = NULL;
}

if(b != -1){
Tree[i].rchild = &Tree[b];
}else{
Tree[i].rchild = NULL;
}
}
for(int i = 0 ; i < n ; i++)
scanf("%d",&key[i]);
sort(key,key+n);

inOrder(&Tree[0]);

queue<TNode> Q;
Q.push(Tree[0]);
printf("%d",Tree[0].data);
while(Q.empty() != true){
TNode tmp = Q.front();
Q.pop();

if(tmp.lchild != NULL){
printf(" %d",tmp.lchild->data);
Q.push(*(tmp.lchild));
}
if(tmp.rchild != NULL){
printf(" %d",tmp.rchild->data);
Q.push(*(tmp.rchild));
}
}
return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%