投稿
  1. 高性能架构探索首页
  2. C/C++

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

admin • • C/C++ • 阅读 165

一、关于建树

  1. 可以使用二叉链表, 一般用来二叉树的建树，同时创建树的时候，要使用new node，递归边界一般为root == NULL。建树的函数也要使用node* create(){}
struct node{
    int id;
    node* l;
    node* r;
};
  1. 静态二叉树的建立, 适合于直接根据下标作为指针进行建树，简单。
struct node{
    int l, r;
}Node[MAXV];
  1. 关于树的建立，有如下两种，要使用结构体，是因为要保存相关结点信息的情况，否则可以直接使用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(inL > inR) return NULL;
    node* root = new node;
    root->v = pre[preL];
    int k = inL;
    while(pre[preL] != in[k]) k++;
    int num = k - inL;
    root->l = create(inL, k - 1, preL + 1, preL + num);
    root->r = create(k + 1, inR, preL + num + 1, preR);
    return root;
}

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;
        }
    }
}
  • 遍历完全二叉树到叶子结点的所有路径，按照一定的顺序打印输出，使用push_back()和pop_back()进行深度回溯遍历：但是，要记得将第一个根结点先插入v数组中；
//按照先右子树然后左子树的遍历顺序进行遍历输出结果；
void dfs(int index){
    if(index * 2 > n){
        if(index <= n){//是为了考虑完全二叉树可能出现只有一个左子树的现象
            for(int i = 0; i < v.size(); i++){
                printf("%d%s", v[i], v.size() - 1 != i ? " " : "\n");
            }
        }
    }else{
        v.push_back(a[index * 2 + 1]);
        dfs(index * 2 + 1);
        v.pop_back();
        v.push_back(a[index * 2]);
        dfs(index * 2);
        v.pop_back();
    }
}

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进行右旋即可;
    1. 如果是平衡因子为BF(root) = 2, BF(root->right) = -1,说明为LR型，先对左子树进行左旋，然后再对当前结点进行右旋;
    1. BF(root) = -2, BF(root-right) = -1, 为RR型，进行左旋即可;
    1. 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;
  • bool vis[] 数组可以用来记录所有集合，便于后面使用int isRoot[] 数组进行类别数量的统计；
  • 要区分题目中想要查询的意思来进行isRoot的利用；

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);
    }
}
关于堆的编程总结：
  • 一个是判断堆是大顶堆还是小顶堆以及不是堆，使用方法主要有两种，一个是首先定义变量int Min = 1， Max = 1；然后堆的序列从第二个元素开始判断如果，出现当前顶点值小于父节点的值，那么将Min = 0，如果出现当前顶点大于父节点的值，那么将Max = 0；最后判断输出：
int isMax = 1, isMin = 1;
int a[1009];
for(int i = 2; i <= n; i++){
    if(a[i/2] > a[i]) isMin = 0//如果父节点比当前结点大，就不是小顶堆；
    if(a[i/2] < a[i]) isMax = 0;//如果父节点比当前结点小，就不是大顶堆；
}
最后结果如果isMax 和isMin都是0，那么说明不是堆。

7. LCA(二叉树)

  • 第一步根据题目进行建树;
struct node{
    int v;
    node* l;
    node* r;
};
vector<int> pre, in;
node* create(int inL, int inR, int preL, int preR){
    if(inL > inR) return NULL;
    node* root = new node;
    root->v = pre[preL];
    int k = inL;
    while(pre[preL] != in[k]) k++;
    int num = k - inL;
    root->l = create(inL, k - 1, preL + 1, preL + num);
    root->r = create(k + 1, inR, preL + num + 1, preR);
    return root;
}
  • 然后使用dfs函数进行查找;
  • lca使用记录最近公共祖先的，bool类型的f1和f2 用来看所给结点是否在树中可以找到;
int lca = -1;
bool f1 = false, f2 = false;
int search(node* root, int u, int v, bool &f1, bool &f2){
    if(root == NULL) return 0;
    int cnt = search(root->l, u, v, f1, f2) + search(root->r, u, v, f1, f2);
    if(root->v == u){
        f1 = true;
        cnt++;
    }
    if(root->v == v){
        f2 = true;
        cnt++;
    }
    if(lca == -1 && cnt == 2){
        lca = root->v;
    }
    return cnt;
}
  • 最后根据题目要求进行输出
int main(){
    int n, m, d;
    cin >> m >> n;
    for(int i = 0; i < n; i++){
        scanf("%d", &d);
        pre.push_back(d);
        in.push_back(d);
    }
    sort(in.begin(), in.end());
    node* root = create(0, n-1, 0, n-1);
    int a, b;
    for(int i = 0; i < m; i++){
        scanf("%d%d", &a, &b);
        lca = -1;
        f1 = false, f2 = false;
        int cnt = search(root, a, b, f1, f2);
        if(!f1 && !f2){
            printf("ERROR: %d and %d are not found.\n", a, b);
            continue;
        }else if(!f1 && f2){
            printf("ERROR: %d is not found.\n", a);
            continue;
        }else if(!f2 && f1){
            printf("ERROR: %d is not found.\n", b);
            continue;
        }
        if(lca == b){
            printf("%d is an ancestor of %d.\n", b, a);
            continue;
        }else if(lca == a){
            printf("%d is an ancestor of %d.\n", a, b);
            continue;
        }else{
            printf("LCA of %d and %d is %d.\n", a, b, lca);
        }
    }
    return 0;
}

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

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

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

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/363315

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午2:52
下一篇 2023年3月2日 下午2:53

相关推荐