1123 Is It a Complete AVL Tree (30 分) 构造AVL输出层次遍历并判断是否为完全二叉树

╰半夏微凉° 2021-10-29 23:48 172阅读 0赞

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

### Input Specification: ###

Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

### Output Specification: ###

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print `YES` if the tree is complete, or `NO` if not.

### Sample Input 1: ###

5
    88 70 61 63 65

### Sample Output 1: ###

70 63 88 61 65
    YES

### Sample Input 2: ###

8
    88 70 61 96 120 90 65 68

### Sample Output 2: ###

88 65 96 61 70 90 120 68
    NO

**题意：**构造AVL输出层次遍历并判断是否为完全二叉树

构造方法也参考1066：[https://blog.csdn.net/TheWise\_lzy/article/details/99686223][https_blog.csdn.net_TheWise_lzy_article_details_99686223]

构造完后可以广搜or深搜存储层序遍历

判断是否为完全二叉树：数组的下标是否有（不是结尾的）空值

（一开始a数组全为-1，结点从0开始编号，结点的左儿子下标为2\*n+1，右儿子为2\*n+2）

注意for判断的时候：for循环走的是i，下标移动的是j

如果不设置j的话，在非完全二叉树的时候无法输出完整的层次遍历。

i控制的是输出的个数，j是层次遍历后的下标，注意区分~

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    struct node
    {
    	int val;
    	node *l,*r; 
    };
    int height(node *root)
    {
    	if(root==NULL)	return 0;
    	return max(height(root->l),height(root->r))+1;
    }
    node *right(node *root)
    {
    	node *t=root->l;
    	root->l=t->r;
    	t->r=root;
    	return t;
    }
    node *left(node *root)
    {
    	node *t=root->r;
    	root->r=t->l;
    	t->l=root;
    	return t;
    }
    node *rightleft(node *root)
    {
    	root->r=right(root->r);
    	return left(root);
    }
    node *leftright(node *root)
    {
    	root->l=left(root->l);
    	return right(root);
    }
    node *insert(node *root,int x)
    {
    	if(root==NULL)
    	{
    		root=new node();
    		root->val=x;
    		root->l=root->r=NULL;
    	}
    	else if(x<root->val)
    	{
    		root->l=insert(root->l,x);
    		if(height(root->l)-height(root->r)==2)
    		root= x<root->l->val ?right(root):leftright(root);
    		
    	}
    	else
    	{
    		root->r=insert(root->r,x);
    		if(height(root->l)-height(root->r)==-2)
    		root= x>root->r->val ?left(root):rightleft(root);
    		
    	}
    	return root;
    }
    int a[50];
    void dfs(node *root,int p)
    {
    	if(root==NULL) return;
    	a[p]=root->val;
    	dfs(root->l,2*p+1);
    	dfs(root->r,2*p+2);
    }
    int main()
    {
    	int n,i,x;
    	node *root=NULL;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&x);
    		root=insert(root,x);
    	}
    	memset(a,-1,sizeof a);
    	dfs(root,0);
    	int flag=0;
    	int j=1;
    	printf("%d",a[0]);
    	for(i=1;i<n;i++)
    	{
    		while(a[j]==-1)
    		{
    			flag=1;
    			j++;
    		}
    		printf(" %d",a[j++]);
    	}
    	if(flag) printf("\nNO\n");
    	else printf("\nYES\n");
    }

[https_blog.csdn.net_TheWise_lzy_article_details_99686223]: https://blog.csdn.net/TheWise_lzy/article/details/99686223