将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。
输入格式:
输入第一行给出一个不超过20的正整数N
;第二行给出N
个互不相同的正整数,其间以空格分隔。
输出格式:
将输入的N
个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果,数字间以1个空格分隔,行的首尾不得有多余空格。第二行输出YES
,如果该树是完全二叉树;否则输出NO
。
输入样例1:
1 2
| 9 38 45 42 24 58 30 67 12 51
|
输出样例1:
1 2
| 38 45 24 58 42 30 12 67 51 YES
|
输入样例2:
1 2
| 8 38 24 12 45 58 67 42 51
|
输出样例2:
1 2
| 38 45 24 58 42 12 67 51 NO
|
思路
跟上一题7-9 完全二叉树的层序遍历 (25 分)的思路十分类似,先得到层序遍历中每一个节点的左右子节点坐标,再将给出的N个正整数插入二叉搜索树中。
结构体数组node存放每个节点的左右孩子在层序遍历中的坐标和该节点的数据,首先判断node[0]的数据是否为0,若为0说明二叉搜索树为空,将该节点设为根节点;否则判断该数据与节点数据大小,如果大于,判断左孩子节点是否为空,如果为空,插入,否则继续判断;如果小于,判断右节点是否为空,如果为空,插入,否则继续判断
插入完成之后,判断从node数组中1到n是否有数据为空的节点,如果有则说明不是完全二叉树,输出NO
;否则输出YES

代码
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
| #include <iostream> using namespace std; struct Node{ int data, l, r; }node[21]; void Insert(int data) { if(node[1].data == 0) { node[1].data = data; return; } int t = 1; while(1){ if(data < node[t].data) t = node[t].r; else t = node[t].l; if(node[t].data == 0) { node[t].data = data; break; } } } int main() { int n; cin >> n; for(int i = 1; i <= n; i++) { node[i].l = i*2; node[i].r = i*2+1; } for(int i = 0; i < n; i++) { int t; cin >> t; Insert(t); } int flag = 0, cnt = 0; for(int i = 1; cnt < n; i++) { if(node[i].data) { if(i > 1) cout << " "; cout << node[i].data; cnt++; } else flag = 1; } if(flag) cout << "\nNO"; else cout << "\nYES"; }
|