1123 Is It a Complete AVL Tree（30 分）

水深无声 2023-03-01 10:05 13阅读 0赞

[1123 Is It a Complete AVL Tree（30 分）][1123 Is It a Complete AVL Tree_30]  
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.

![在这里插入图片描述][20200723202829541.png]

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

考点：

1、AVL树的建立（参照1066）；

2、完全二叉树的判断

3、完全二叉树的层次遍历。

本题中建立AVL树后，直接用DFS进行层次遍历，直接假定他为完全二叉树，则左右孩子的节点的标号与节点的关系为2*index和2*index+1；在判断是否为完全二叉树，只要看遍历的数组中有无空则可以判断。

#include <iostream>
    #include <vector>
    using namespace std;
    vector<int>level(205, -1);
    struct node{ 
    	int value;
    	node *left, *right;
    	node(int x): value(x), left(nullptr), right(nullptr){ };
    };
    node *rotateL(node *root){ 
    	node *temp = root->right;
    	root->right = temp->left;
    	temp->left = root;
    	return temp; 
    }
    node *rotateR(node *root){ 
    	node *temp = root->left;
    	root->left = temp->right;
    	temp->right = root;
    	return temp;
    }
    node *rotateLR(node *root){ 
    	root->left = rotateL(root->left);
    	return rotateR(root);
    }
    node *rotateRL(node *root){ 
    	root->right = rotateR(root->right);
    	return rotateL(root);
    }
    int getHeight(node *root){ 
    	if(root == nullptr)
    		return 0;
    	return max(getHeight(root->right), getHeight(root->left)) + 1;
    }
    node *insert(node *root, int val){ 
    	if(root == nullptr)
    		root = new node(val);
    	else if(root->value > val){ 
    		root->left = insert(root->left, val);
    		if(getHeight(root->left) - getHeight(root->right) == 2)
    			root = val < root->left->value ? rotateR(root) : rotateLR(root);
    	}
    	else{ 
    		root->right = insert(root->right, val);
    		if(getHeight(root->right) - getHeight(root->left) == 2)
    			root = val > root->right->value ? rotateL(root) : rotateRL(root);
    	}
    	return root;
    }
    void dfs(node *root, int index){ 
    	if(root == nullptr)
    		return;
    	level[index] = root->value;
    	dfs(root->left, 2 * index);
    	dfs(root->right, 2 * index + 1);
    }
    int main(){ 
    	int n, temp, cur = 2;
    	node *root = nullptr;
    	scanf("%d", &n);
    	for(int i = 0; i < n; ++ i){ 
    		scanf("%d", &temp);
    		root = insert(root, temp);
    	}
    	dfs(root, 1);
    	bool flag = true;
    	printf("%d", level[1]);
    	for(int i = 1; i < n; ++ i){ 
    		while(level[cur] == -1){ 
    			++ cur;
    			flag = false;
    		}
    		printf(" %d", level[cur ++]);
    	}
    	printf("\n%s",flag == true ? "YES" : "NO");
    }

[1123 Is It a Complete AVL Tree_30]: https://pintia.cn/problem-sets/994805342720868352/problems/994805351302414336
[20200723202829541.png]: /images/20230209/5add64fa5ecf46c4b880f533cee29349.png