数据结构-关于各种树的详细编程总结（二叉树、BST查找树、AVL平衡树、完全二叉树、并查集、堆）C++

一、关于建树

1. 可以使用二叉链表, 一般用来二叉树的建树，同时创建树的时候，要使用new node，递归边界一般为root == NULL。建树的函数也要使用node* create(){}

struct node{
    int id;
    node* l;
    node* r;
};

2. 静态二叉树的建立, 适合于直接根据下标作为指针进行建树，简单。

struct node{
    int l, r;
}Node[MAXV];

3. 关于树的建立，有如下两种，要使用结构体，是因为要保存相关结点信息的情况，否则可以直接使用vector v[MAXN];进行建树，一般使用DFS进行遍历

struct node{
    int id;
    vector<int> sub;
};

vector<int> Node[MAXV];

二、关于树的遍历

1. DFS

void DFS(int root, int layer){
    if(递归边界){
        return；
    }
    for(int i = 0; i < 子树的数量; i++){
        DFS(root, layer + 1);
    }
}

2.BFS()实质就是层序遍历

void BFS(int root){
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        node* now = q.front();
        进行操作，对于该结点，可以用一个vector将其存起来
        if(左右结点不空) q.push(左右结点编号) 
    }
}

3.先序、中序和后序遍历

void pre(int root){
    if(递归边界){
        return;
    }
    对该结点进行操作，可以使用vector进行存储。
    pre(左子树结点)；
    pre(右子树结点)
}

三、关于各种树的一些操作

1. 二叉树-已知中序和前序或中序和后序，进行树的创建

node* create(int inL, int inR, int preL, int preR){
    if(preL > preR){
        return NULL;
    }
    node* root = new node;
    root->data = pre[preL];
    int k;
    for(k = inL; k <= inR; k++){
        if(in[k] == pre[preL]){
            break;
        }
    }
    int num = k - inL;
    root->l = create(inL, inL + num - 1, preL + 1, preL + num);
    root->R = create(k + 1, inR, preL + num + 1, preR);
}

2. BST二叉查找树

• 创建、查找、以及各种遍历；

void insert(node* root, int data){
    if(root = NULL){
        root = new node;
        root->data = data;
        root->l = root->r = NULL;
        return;
    }
    if(data < root->data) insert(root->l, data);
    else insert(root->r, data);
}

• 如果想遍历的结果存储起来，可以直接传入一个引用的vector向量数组；
• 关于镜像的问题，也就是遍历的时候直接将左右子树的操作顺序进行调换即可；
• 关于删除问题：

node* findMin(node* root){
    while(root->l != NULL){
        root = root->l;
    }
    return root;
}

node* findMax(node* root){
    while(root->r != NULL){
        root = root->r;
    }
    return root;
}

void deleteNode(node* &root, int x){
    if(root == NULL) return;
    if(root->data == x){
        if(root->l == NULL && root->r == NULL){
            root = NULL;
        }else if(root->l != NULL){
            node* pre = findMax(root->l);
            root->data = pre->data;
            deleteNode(root->l, pre->data);
        }else{
            node* next = findMin(root->r);
            root->data = next->data;
            deleteNode(root->r, next->data);
        }
    }else if(root->data < x){
        deleteNode(root->l, x);
    }else{
        deleteNode(root->r, x);
    }
}

3. 完全二叉树与查找树的结合

• 完全二叉树的性质是左右子树下标分别为2 x index， 2 x index + 1;
• 根结点下标为1，完全二叉树到空结点的标志为当前结点编号root大于结点个数n；
• 二叉查找树的中序遍历是从小到大的，然后根据完全二叉树的结点性质，可以进行建树，然后该数组直接输出便是层序遍历的结果；
• 判断完全二叉树的某个结点root是否为叶子结点的标志为：该结点的左子树的编号root * 2 大于总结点的个数n；
• 也要会提前使用一个数组将二叉树结点的值存好，然后使用Node[len++] 的方式进行赋值；
• 关于如何判断二叉树是否为完全二叉树，可以进行层序遍历，然后出现子树为空后，再出现子树不为空的情况，那么就说明不是完全二叉树，一般设置变量isComplete = 1， after = 0 :

vector<int> level;
int isComplete = 1, after = 0;
void BFS(node* root){
	queue<node*> q;
	q.push(root);
	while(!q.empty()){
		node* now = q.front();
		level.push_back(now->data);
		q.pop();
		if(now->l != NULL){
			if(after) isComplete = 0;
			q.push(now->l);
		}else{
			after = 1;
		}
		if(now->r != NULL){
			if(after) isComplete = 0;
			q.push(now->r);
		}else{
			after = 1;
		}
	}
}

4. AVL树

基本构成函数：

struct node{
	int data, height;
	node* l;
	node* r;
}; 
node* newNode(int v){
	node* root = new node;
	root->data = v;
	root->height = 1;
	root->l = root->r = NULL;
	return root;
}

• 当结点为NULL时，返回的高度应该为0，这一句不能省

int getH(node* root){
	if(root == NULL) return 0;
	return root->height;
}

int getB(node* root){
	return getH(root->l) - getH(root->r);
}
void updateH(node* root){
	root->height = max(getH(root->l), getH(root->r)) + 1;
}

左旋与右旋

• 记住口诀，左旋为，临创建赋值根右根右临左临左赋值为根；右旋为，临创建赋值根左根左临右临右赋值为根，然后更新高度先根后临，最后根赋值临；
• 传参有引用别忘记

void L(node* &root){
	node* temp = root->r;
	root->r = temp->l;
	temp->l = root;
	updateH(root);
	updateH(temp);
	root = temp;
}
void R(node* &root){
	node* temp = root->l;
	root->l = temp->r;
	temp->r = root;
	updateH(root);
	updateH(temp);
	root = temp; 
}

关于各种平衡因子下需要调整的问题 ：

• 1. 如果是平衡因子为BF(root) = 2, BF(root->left) = 1,说明为LL型，对root进行右旋即可;
• 2. 如果是平衡因子为BF(root) = 2, BF(root->right) = -1,说明为LR型，先对左子树进行左旋，然后再对当前结点进行右旋;
• 3. BF(root) = -2, BF(root-right) = -1, 为RR型，进行左旋即可;
• 4. BF(root) = -2, BF(root-right) = 1, 为RL型，先对右子树进行右旋，然后进行左旋即可;

void insert(node* &root, int v){
	if(root == NULL){
		root = newNode(v);
		return;
	}
	if(v < root->data){
		insert(root->left, v);
		updateH(root);
		if(getB(root) == 2){
			if(getB(root->left) == 1){
				R(root);
			}else if(getB(root->left) == -1){
				L(root->left);
				R(root);
			}
		}
	}else{
		insert(root->right, v);
		updateH(root);
		if(getB(root) == -2){
			if(getB(root->right) == -1){
				L(root);
			}else if(getB(root->right) == 1){
				R(root->right);
				L(root);
			}
		}
	}
} 

5. 并查集

• 初始化：

const int MAXV = 10010;
int father[MAXV];
int course[MAXV] = {0};
int isRoot[MAXV] = {0};
void init(){
	for(int i = 1; i <= n; i++){
		father[i] = i;
	}
}

• 查找：

int findFather(int x){
	int a = x;
	while(x != father[x]){
		x = father[x];
	}
	while(a != father[a]){
		int z = a;
		a = father[a];
		father[z] = x;
	}
	return x;
}

• 合并：

void Union(int a, int b){
	int faA = findFather(a);
	int faB = findFather(b);
	if(faA != faB){
		father[faA] = faB;
	}
}

几点核心思想：

• 关于初始化的问题，可以把所有下标设置称为从1开始到n；
• 所有问题都可以转化为设置三个数组，一个是集合数组father，用于存储集合，也就是从1~n;
• 然后是数组course，用于存储其中具备该h属性所代表的根结点i（1 ~ n）；
• 设置isRoot数组，用于存储划分集合的个数，通过遍历所有数，然后通过函数findFather寻找其根结点，然后++，最后使用变量ans，再遍历一遍isRoot数组，不为0的++；
• 如果要查找属性是否是在同一个集合中，通过findFather(course[h1]) == findFather(course[h2]) ,进行判断即可。

6. 堆

建堆的几个关键函数：

• 向下调整函数: 原理解释，就是把当前结点跟其左右子树结点的值进行比较，如果返现比其中之一小，那么就交换，直到其比左右子树结点的值大；

void downAjust(int low, int high){
    int i = low, j = 2 * i;
    while(j <= high){
        if(j + 1 <= high && heap[j] < heap[j + 1]){
            j = j + 1;
        }
        if(heap[i] < heap[j]){
            swap(heap[i], heap[j]);
            i = j;
            j = 2 * i;
        }else{
            break;
        }
    }
}

• 建堆： 原理解释，将序列heap[N]，因为具备完全二叉树的性质，那么知道叶子结点是N/2之后的值，我们只需要将1~N/2非叶子结点，从后往前进行向下调整，即可保证以当前结点为根结点的值，一定是最大值；

void createHeap(){
    for(int i = N / 2; i >= 1; i--){
        downAjust(i, N);
    }
}

• 删除堆顶元素： 原理解释，将堆序列中的最后一个元素覆盖掉堆顶元素，然后进行向下调整即可；

void delete(){
    heap[1] = heap[n--];
    downAjust(1, n);
}

• 向上调整函数： 原理解释，也就是将当前序列中的最后一个结点，将其与父节点进行比较，如果发现比它大，那么两者交换；

void upAjust(int low, int high){
    int i = high, j = i / 2;
    while(j >= low){
        if(heap[i] > heap[j]){
            swap(heap[i], heap[j]);
            i = j;
            j = i / 2;
        }else{
            break;
        }
    }
}

• 插入函数： 原理解释，将一个结点插入堆中，首先将其放置在堆的末尾元素，然后使用向上调整函数即可；

void insert(int v){
    heap[++n] = v;
    upAjust(1, n);
}

• 堆排序： ，首先进行建堆，然后原理是，每次将堆首元素与末尾元素进行交换，放置在末尾，也就是将堆中的最大值放在序列的最后，然后使用向下调整函数进行调整；

void heapSort(){
    createHeap();
    for(int i = n; i >= 1; i--){
        swap(heap[i], heap[1]);
        downAjust(1, i-1);
    }
}

数据结构-关于各种树的详细编程总结（二叉树、BST查找树、AVL平衡树、完全二叉树、并查集、堆）C++

原文：https://www.cnblogs.com/tsruixi/p/13263485.html