(PAT 1123) Is It a Complete AVL Tree (平衡二叉树)

￡神魔★判官ぃ 2022-03-17 12:22 164阅读 0赞

1123 Is It a Complete AVL Tree （30 point(s)）

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二叉树模板即可

我的代码第三个测试用例死活过不去,在这里请教原因

#include<iostream>
    #include<algorithm>
    #include<queue>
    using namespace std;
    int N;
    int inputNodes[30];
    int layerOrders[1050000] = { 0 };
    struct SBNode {  //新节点
    	int sbData;
    	int sbHeight;
    	SBNode* lchild, *rchild;
    	SBNode(int sbValue) {
    		sbData = sbValue;
    		sbHeight = 1;
    		lchild = rchild = nullptr;
    	}
    };
    //获取树的高度
    int sbGetTreeHeight(SBNode* root) {
    	if (root == nullptr) return 0;
    	return root->sbHeight;
    }
    //获取平衡因子
    int getBalanceFactor(SBNode* root) {
    	return sbGetTreeHeight(root->lchild) - sbGetTreeHeight(root->rchild);
    }
    //更新树的高度
    void updateTreeHeight(SBNode* root) {
    	root->sbHeight = max(sbGetTreeHeight(root->lchild), sbGetTreeHeight(root->rchild)) + 1;  //获取树的高度
    }
    //左旋
    void sbLeftParade(SBNode* &root) {
    	SBNode* tempnode = root->rchild;
    	root->rchild = tempnode->lchild;
    	tempnode->lchild = root;
    	updateTreeHeight(root);
    	updateTreeHeight(tempnode);
    	root = tempnode;
    }
    //右旋
    void sbRightParade(SBNode* &root) {
    	SBNode* tempNode = root->lchild;
    	root->lchild = tempNode->rchild;
    	tempNode->rchild = root;
    	updateTreeHeight(root);
    	updateTreeHeight(tempNode);
    	root = tempNode;
    }
    //插入新节点并作调整
    void sbInsert(SBNode* &root, int bvalue) {
    	if (root == nullptr) {
    		root = new SBNode(bvalue);
    		return;
    	}
    	if (bvalue < root->sbData) {
    		sbInsert(root->lchild, bvalue);
    		updateTreeHeight(root);
    		if (getBalanceFactor(root) == 2) {  //向左节点插入的
    			if (getBalanceFactor(root->lchild) == 1) {  //LL
    				sbRightParade(root);
    			}
    			if (getBalanceFactor(root->lchild) == -1) {  //LR
    				sbLeftParade(root->lchild);
    				sbRightParade(root);
    			}
    		}
    	}
    	else {
    		sbInsert(root->rchild, bvalue);
    		updateTreeHeight(root);
    		if (getBalanceFactor(root) == -2) {  //向右节点插入的
    			if (getBalanceFactor(root->rchild) == 1) {  // RL
    				sbRightParade(root->rchild);
    				sbLeftParade(root);
    			}
    			if (getBalanceFactor(root->rchild) == -1) {  // RR
    				sbLeftParade(root);
    			}
    		}
    	}
    }
    //建树
    SBNode* SBcreateTree(int datas[], int n) {
    	SBNode* root = nullptr;
    	for (int i = 0; i < n; ++i) {
    		sbInsert(root, datas[i]);
    	}
    	return root;
    }
    //层序遍历
    int nums = 0;
    void layer_output(SBNode* root) {
    	queue<SBNode*> layer_queue;
    	layer_queue.push(root);
    	while (!layer_queue.empty()) {
    		SBNode* curNode = layer_queue.front();
    		cout << curNode->sbData;
    		if (nums < N - 1) cout << " ";
    		nums++;
    		layer_queue.pop();
    		if (curNode->lchild != nullptr) {
    			layer_queue.push(curNode->lchild);
    		}
    		if (curNode->rchild != nullptr) {
    			layer_queue.push(curNode->rchild);
    		}
    	}
    }
    //判断完全二叉树
    void getCompletearrays(SBNode* root,int pos) {
    	layerOrders[pos] = root->sbData;
    	if (root->lchild != nullptr) {
    		getCompletearrays(root->lchild, 2 * pos);
    	}
    	if (root->rchild != nullptr) {
    		getCompletearrays(root->rchild, 2 * pos + 1);
    	}
    }
    
    int main() {
    	cin >> N;
    	for (int i = 0; i < N; ++i) {
    		cin >> inputNodes[i];  //插入结点
    	}
    	SBNode* sroot = SBcreateTree(inputNodes, N);
    	layer_output(sroot);
    	//判断完全二叉树
    	cout << endl;
    	getCompletearrays(sroot, 1);  //填数组
        //判断是否是完全二叉树
    	bool flag = true;
    	for (int i = 1; i <= N; ++i) {
    		if (layerOrders[i] == 0) {
    			flag = false;
    			break;
    		}
    	}
    	if (flag) {
    		cout << "YES" << endl;
    	}
    	else {
    		cout << "NO" << endl;
    	}
    
    	system("PAUSE");
    	return 0;
    }