struct node{
int id;
node* l;
node* r;
};
struct node{
int l, r;
}Node[MAXV];
struct node{
int id;
vector<int> sub;
};
vector<int> Node[MAXV];
void DFS(int root, int layer){
if(递归边界){
return;
}
for(int i = 0; i < 子树的数量; i++){
DFS(root, layer + 1);
}
}
void BFS(int root){
queue<int> q;
q.push(root);
while(!q.empty()){
node* now = q.front();
进行操作,对于该结点,可以用一个vector将其存起来
if(左右结点不空) q.push(左右结点编号)
}
}
void pre(int root){
if(递归边界){
return;
}
对该结点进行操作,可以使用vector进行存储。
pre(左子树结点);
pre(右子树结点)
}
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);
}
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);
}
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);
}
}
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;
}
}
}
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;
}
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;
}
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);
}
}
}
}
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;
}
}
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;
}
}
}
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