L3-010. 是否完全二叉搜索树

时间限制

400 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

输入格式：

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

输出格式：

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出“YES”，如果该树是完全二叉树；否则输出“NO”。

输入样例1：

938 45 42 24 58 30 67 12 51

输出样例1：

38 45 24 58 42 30 12 67 51YES

输入样例2：

838 24 12 45 58 67 42 51

输出样例2：

38 45 24 58 42 12 67 51NO

思路：

二叉搜索树的建立比较常规，主要是完全二叉树的判断方式，完全二叉树的通俗理解是从根结点开始，依次从左到右填充树结点。也就是说最深的一行除外，其余节点构成的二叉树是完美二叉树，而最深的一行所有节点都集中在最左边。

判断方式：按照两种方式编号，第一种编号是在插入节点的时候顺便记录插入节点在二叉树中的位置。第二种编号则是依据层序遍历搜索顺序建立的编号，判断每个节点两种方式的编号是否相同，若有节点的两种编号不同，说明不是完全二叉树。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 using namespace std;#define N_MAX 20+5#define INF 0x3f3f3f3fint n;struct Node{ int key=0; int id=0; int num=0; Node* left, *right,*parent;}node[N_MAX];Node *root,*NIL;void insert(int k) { Node*x = root; Node *z=new(Node); z->key = k; z->left = NIL; z->right = NIL; Node*y = NIL; while (x!=NIL) { y = x; if (x->key < k) x = x->left; else x = x->right; } z->parent = y; if (y == NIL)root=z; else { if (z->key > y->key) { y->left = z; z->id = y->id * 2+1;//确定每个新增节点在二叉树中位置 } else { y->right = z; z->id = y->id * 2 + 2; } }}vector
                 
                  vec; bool flag;int num = 0;void bfs(Node root) { queue
                  
                   que; que.push(root); vec.push_back(root.key); while (!que.empty()) { Node p = que.front(); que.pop(); if (p.id != p.num)flag = 1;//p.id是按照节点p在二叉树的位置而定,p.num按照从左往右层序遍历的顺序编号，两者有不同说明不是完全二叉树 if (p.left != NIL) { num++; p.left->num = num; vec.push_back(p.left->key); que.push(*p.left); } if (p.right != NIL) { num++; p.right->num = num; vec.push_back(p.right->key); que.push(*p.right); } }}int main() { while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) { int x; scanf("%d",&x); insert(x); } vec.clear(); num = 0; flag = 0; bfs(*root); for (int i = 0; i < n; i++) printf("%d%c",vec[i],i+1==n?'\n':' '); if (flag)puts("NO"); else puts("YES"); } return 0;}

转载于:https://www.cnblogs.com/ZefengYao/p/8486287.html

你可能感兴趣的文章