天天看點
傳回

PAT A1123 Is It a Complete AVL TreePAT A1123 Is It a Complete AVL Tree

PAT A1123 Is It a Complete AVL Tree

PAT A1123 Is It a Complete AVL TreePAT A1123 Is It a Complete AVL Tree
  • 思路 1：
  1. 建樹
  2. 層序周遊，初始起點的id即為1，每次将目前出隊節點now的id在has表裡标記上，now的左孩子id為：

    2 * now->id

     ，右孩子id：

    2 * now->id + 1
  3. 周遊has表，如果1~n有點未被标記：不是完全二叉樹，否則YES：如果是完全二叉樹，按id記錄下來的節點，一定是從1到n連續的 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 50;
int insertion[maxn];
struct node{
	int data, height, id;
	node *lc, *rc;
	node(){lc = rc = NULL; height = 1;}	//Wrong 1:初始樹高為1:别寫成0了 
};
int getHeight(node* r){
	if(r == NULL) return 0;	//Wrong 2:getHeight()别忘了r==NULL的情況，空樹高度0
	return r->height;
}
void updateHeight(node* r){
	r->height = max(getHeight(r->lc), getHeight(r->rc)) + 1;
}
int getBalanceFactor(node* r){
	return getHeight(r->lc) - getHeight(r->rc);
}
void L(node* &r){
	node* tmp = r->rc;
	r->rc = tmp->lc;
	tmp->lc = r;
	updateHeight(r);	
	updateHeight(tmp);	///!!!Wrong 3:順序不能颠倒，要先更新下面的，再更新上面的 
	r = tmp;
}
void R(node* &r){
	node* tmp = r->lc;
	r->lc = tmp->rc;
	tmp->rc = r;
	updateHeight(r);
	updateHeight(tmp);
	r = tmp;
}
void insert(node* &r, int x){	//Wrong 4:傳回值為viod：直接r上操作，不需要傳回root了（node*） 
	if(r == NULL){
		r = new node;
		r->data = x;
		return;
	}
	if(x < r->data){
		insert(r->lc, x);
		updateHeight(r);
		if(getBalanceFactor(r) == 2){
			if(getBalanceFactor(r->lc) == 1){	//LL
				R(r);
			}else if(getBalanceFactor(r->lc) == -1){	//LR
				L(r->lc);
				R(r);
			}
		}
	}else{
		insert(r->rc, x);
		updateHeight(r);
		if(getBalanceFactor(r) == -2){
			//!!!:Wrong 5:複制過來，千萬不要忘記改rc/lc 
			if(getBalanceFactor(r->rc) == -1){	//RR
				L(r);
			}else if(getBalanceFactor(r->rc) == 1){	//RL
				R(r->rc);
				L(r);
			}
		}
	}
}
node* create(int n){
	node* r = NULL;
	for(int i = 0; i < n; ++i)
		insert(r, insertion[i]);
	return r;
}
vector<int> ans;
int levelo[maxn];
void levelOrder(node* r){
	queue<node*> q;
	r->id = 1;
	q.push(r);
	while(!q.empty()){
		node* now = q.front();
		ans.push_back(now->data);
		levelo[now->id] = 1;
		q.pop();
		if(now->lc != NULL){
			now->lc->id = now->id * 2;
			q.push(now->lc);
		} 
		if(now->rc != NULL){
			now->rc->id = now->id * 2 + 1;
			q.push(now->rc);
		}
	}
}
int main(){
	int n;
	scanf("%d", &n);	
	for(int i = 0; i < n; ++i){
		scanf("%d", &insertion[i]);
	}
	node* root = create(n);
	levelOrder(root);
	for(int i = 0; i < ans.size(); ++i){
		if(i == 0) printf("%d", ans[0]);
		else printf(" %d", ans[i]);
	} 
	bool flag = false;
	for(int i = 1; i <= n; ++i){
		if(levelo[i] == 0){
			flag = true;
		} 
	}
	printf("\n%s", flag ? "NO" : "YES");
	return 0;
}
  • AVL：注意事項

  • Wrong 1:

    一個節點的樹的高度初始為1

  • Wrong 2：

    getHeight()别忘了r==NULL的情況，空樹高度0

  • Wrong 3：

    左旋右旋操作後，更新r和tmp高度的順序不能颠倒，要先更新下面的，再更新上面的（因為更新前r和tmp還沒交換，所有tmp在上，先更新r）

  • Wrong 4:

    注意傳回值類型，如這裡插入和L/R都是通過在傳入參數

    node* &root

     直接修改，故傳回值為viod：直接r上操作，不需要傳回root了

  • Wrong 5:

    插入裡的左右判斷，如果直接把左的情況複制粘貼到右的情況，千萬不要忘記改rc/lc

  • TIPS 1:

    可以改為後序周遊遞歸查高度，省去了updateHeight()

int getHeight(node *tree){    
	if (tree == NULL) return 0;    
	int l = getHeight(tree->left);    
	int r = getHeight(tree->right);    
	return max(l, r) + 1; 
}
  • 思路1-2：先序存入數組法：同PAT A1064 Complete Binary Search Tree、PAT A1066 Root of AVL Tree

step 1：建樹後，通過先序周遊将樹存入heap數組（初始化為INF），期間若有元素下标超過n，說明不是CBT

step 2：右往左依次輸出數組中非INF元素，即為層序周遊序列

  • T2 code 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50, INF = 0xfffffff;
struct node{
	int data, height;
	node *lc, *rc;
};
node* NewNode(int x){
	node* r = new node;
	r->data = x;
	r->lc = r->rc = NULL;
	r->height = 1;
	return r;
}
int GetHeight(node* r){
	return r == NULL ? 0 : r->height;
}
void UpdateHeight(node* r){
	r->height = max(GetHeight(r->lc), GetHeight(r->rc)) + 1;
}
int GetBalanceFactor(node* r){
	return GetHeight(r->lc) - GetHeight(r->rc);
}
void L(node* & r){
	node* tmp = r->rc;
	r->rc = tmp->lc;
	tmp->lc = r;
	UpdateHeight(r);
	UpdateHeight(tmp);
	r = tmp;
}
void R(node* & r){
	node* tmp = r->lc;
	r->lc = tmp->rc;
	tmp->rc = r;
	UpdateHeight(r);
	UpdateHeight(tmp);
	r = tmp;
}
void Insert(node* & r, int x){
	if(r == NULL){
		r = NewNode(x);
		return; 
	}
	if(r->data > x){
		Insert(r->lc, x);
		UpdateHeight(r);
		if(GetBalanceFactor(r) == 2){
			if(GetBalanceFactor(r->lc) == -1) L(r->lc);
			R(r);
		}
	}else{
		Insert(r->rc, x);
		UpdateHeight(r);
		if(GetBalanceFactor(r) == -2){
			if(GetBalanceFactor(r->rc) == 1) R(r->rc);
			L(r);
		}
	}
}
int heap[maxn];
bool flag = true;
void PreOrder(int id, int n, node* r){
	if(r == NULL) return;
	PreOrder(2 * id, n, r->lc);
	if(id > n) flag = false;
	heap[id] = r->data;
	PreOrder(2 * id + 1, n, r->rc);
}
int main(){
	int n, tmp;
	scanf("%d", &n);
	node* r = NULL;
	for(int i = 0; i < n; ++i){
		scanf("%d", &tmp);
		Insert(r, tmp);
	}
	fill(heap, heap+maxn, INF);
	PreOrder(1, n, r);
	for(int i = 1; i < maxn; ++i){
		if(i == 1) printf("%d", heap[i]);
		else if(heap[i] != INF) printf(" %d", heap[i]);
	}
	printf("\n%s", flag ? "YES" : "NO");
	return 0;
}

  • 思路 2：柳神的思路

    如果一個孩子節為空，後面所有孩子節點都不會空了，否則就不是完全二叉樹

    類似程序同步互斥，當有孩子空時，lock開鎖，後面如果還有進入if(lock)的說明後面還有不空節點，标記為false

  • code 2: 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 50;
int insertion[maxn];
struct node{
	int data;
	node *lc, *rc;
	node(){lc = rc = NULL;}	 
};
int getHeight(node* r){
	if(r == NULL) return 0;
	int lH = getHeight(r->lc);    
	int rH = getHeight(r->rc);    
	return max(lH, rH) + 1; 
}
void L(node* &r){
	node* tmp = r->rc;
	r->rc = tmp->lc;
	tmp->lc = r;
	r = tmp;
}
void R(node* &r){
	node* tmp = r->lc;
	r->lc = tmp->rc;
	tmp->rc = r;
	r = tmp;
}
void insert(node* &r, int x){	
	if(r == NULL){
		r = new node;
		r->data = x;
		return;
	}
//	int lH = getHeight(r->lc), rH = getHeight(r->rc);	//!!!Wrong 1：必須放到裡面！WHY？ 
	if(x < r->data){
		insert(r->lc, x);
		int lH = getHeight(r->lc), rH = getHeight(r->rc);
		if(lH - rH >= 2){
			if(x < r->lc->data) R(r);	//LL
			else{	//LR
				L(r->lc);
				R(r);
			}
		}
	}else{
		insert(r->rc, x);
		int lH = getHeight(r->lc), rH = getHeight(r->rc);
		if(rH - lH >= 2){
			if(x > r->rc->data) L(r);	//RR
			else{	//RL
				R(r->rc);
				L(r);
			}
		}
	}
}
node* create(int n){
	node* r = NULL;
	for(int i = 0; i < n; ++i)
		insert(r, insertion[i]);
	return r;
}
bool isComplete = true, lock = false;
vector<int> ans;
void levelOrder(node* r){
	queue<node*> q;
	q.push(r);
	while(!q.empty()){
		node* now = q.front();
		q.pop();
		ans.push_back(now->data);
		if(now->lc != NULL){
			if(lock) isComplete = false;
			q.push(now->lc);
		}else lock = true; 
		if(now->rc != NULL){
			if(lock) isComplete = false;
			q.push(now->rc);
		}else lock = true;
	}
}
int main(){
	int n;
	scanf("%d", &n);	
	for(int i = 0; i < n; ++i){
		scanf("%d", &insertion[i]);
	}
	node* root = create(n);
	levelOrder(root);
	for(int i = 0; i < ans.size(); ++i){
		if(i == 0) printf("%d", ans[0]);
		else printf(" %d", ans[i]);
	} 
	printf("\n%s", isComplete ? "YES" : "NO");
	return 0;
}
  • T4 code: 
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int data, height;
    node *lc, *rc;
};
node* NewNode(int x)
{
    node* r = new node;
    r->data = x;
    r->height = 1;
    r->lc = r->rc = nullptr;
    return r;
}
int GetHeight(node* r) { return r == nullptr ? 0 : r->height; }
void UpdateHeight(node* r) { r->height = max(GetHeight(r->lc), GetHeight(r->rc)) + 1; }
int GetBalanceFactor(node* r) { return GetHeight(r->lc) - GetHeight(r->rc); }
void L(node* & r)
{
    node* tmp = r->rc;
    r->rc = tmp->lc;
    tmp->lc = r;
    UpdateHeight(r);
    UpdateHeight(tmp);
    r = tmp;
}
void R(node* & r)
{
    node* tmp = r->lc;
    r->lc = tmp->rc;
    tmp->rc = r;
    UpdateHeight(r);
    UpdateHeight(tmp);
    r = tmp;
}
void Insert(node* & r, int x)
{
    if(r == nullptr)
    {
        r = NewNode(x);
    }else if(x < r->data)
    {
        Insert(r->lc, x);
        UpdateHeight(r);
        if(GetBalanceFactor(r) == 2)
        {
            if(GetBalanceFactor(r->lc) == -1) L(r->lc);
            R(r);
        }
    }else
    {
        Insert(r->rc, x);
        UpdateHeight(r);
        if(GetBalanceFactor(r) == -2)
        {
            if(GetBalanceFactor(r->rc) == 1) R(r->rc);
            L(r);
        }
    }
}
struct v
{
    int data, id;
    bool operator < (const v & tmp) const { return id < tmp.id; }
};
set<v> ans;
void Pre(node* r, bool & isCBT, int id, int n)
{
    if(r == nullptr) return;
    if(id > n) isCBT = false;
    ans.insert(v{r->data, id});
    Pre(r->lc, isCBT, 2 * id, n);
    Pre(r->rc, isCBT, 2 * id + 1, n);
}
int main()
{
    int n;
    scanf("%d", &n);
    node* r = nullptr;
    for(int i = 0; i < n; ++i)
    {
        int tmp;
        scanf("%d", &tmp);
        Insert(r, tmp);
    }
    bool isCBT = true;
    Pre(r, isCBT, 1, n);
    for(auto it = ans.begin(); it != ans.end(); ++it)
    {
        if(it == ans.begin()) printf("%d", it->data);
        else printf(" %d", it->data);
    }
    printf("\n%s", isCBT ? "YES" : "NO");
    return 0;
}
PAT A AVL
上一篇: 618活動，來就送
下一篇: 1123. Is It a Complete AVL Tree (30)[AVL樹+層序周遊]

繼續閱讀