数据结构：构建完全二叉查找树

文章目录

- 1、步骤 1: 对给定数组排序
- 2、步骤 2: 递归构建完全二叉查找树
- 3、注意
- 4、在有序数组中寻找根结点位置
- 5、代码实现
- 6、其他方法？
- - 基本思路
  - 插入操作
  - 删除操作
  - 特别考虑

对于一个给定序列的二叉查找树，有很多种，但是完全二叉查找树只有一种，因为树形是确定的，我们按照中根序列遍历的顺序也是按照数值大小顺序的，因此按照树结点的中根遍历顺序将序列按照数值大小顺序填入这颗树形确定的完全二叉树中，可以得到一颗唯一确定的完全二叉树。并且对于根结点，其左子树的所有结点都小于根结点，右子树的所有结点都大于等于根结点。
构建一颗 完全二叉查找树（Complete Binary Search Tree，CBST）的算法关键在于如何保证二叉树的完全性质，同时维护二叉查找树（BST）的特性：对于任意节点，其左子树的所有节点的值小于该节点的值，其右子树的所有节点的值大于等于该节点的值。

以下是构建完全二叉查找树的一种有效算法：

1、步骤 1: 对给定数组排序

由于二叉查找树的中序遍历结果是一个有序数组，**首先要对输入的无序数组进行排序。**根结点的位置是可以唯一确定的。

2、步骤 2: 递归构建完全二叉查找树

选择中间元素作为树的根：从排序好的数组中选择中间的元素作为二叉查找树的根节点。如果有两个中间元素，选择它们中的任意一个。
递归构建左子树和右子树：将根节点左侧的元素递归地构建成左子树，将根节点右侧的元素递归地构建成右子树。

3、注意

完全二叉树的定义是除了最后一层外，每一层都是完全填满的，而最后一层从左向右填充。上述算法构建的是一棵高度平衡的二叉查找树，但不一定满足完全二叉树的严格定义。构建满足完全二叉树定义的二叉查找树需要更复杂的逻辑来确保所有层（除了可能的最后一层）都完全填满。
确保完全性的一个方法是通过计算给定元素数量所能构建的完全二叉树的最大高度，然后在构建过程中控制树的形态，使其满足完全二叉树的性质。

4、在有序数组中寻找根结点位置

在这里插入图片描述

完全二叉树的性质：

性质的数学公式换算：
- 树的结点个数n 取对数可以得到树高： Treeheight=log2(n)
- 通过树高可以得到除最后一层之外的右子树结点个数：rightTree1=pow(2,Treeheight-1)-1
- 通过树高以及树的结点个数可以得到树的最后一层结点个数：lastLevelNodes=n-(pow(2,Treeheight)-1)
- 最后可以得到右子树结点个数：rightTree=rightTree1+((lastLevelNodes-pow(2,Treeheight-1))>0?(lastLevelNodes-pow(2,Treeheight-1)) :0)
直接求满了的层的总结点个数：
- 利用快速幂思想，即取出总结点数n的二进制位数的最高位。
- 然后计算即可得到右子树的个数

5、代码实现

数学性质

#include<bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 构建完全二叉查找树
TreeNode* createTree(int start, int end, vector<int>& sortedValues) {
    if (start > end) return nullptr;

    // 计算完全二叉树的最后一层前的所有节点数和最后一层的节点数
    int totalNodes = end - start + 1;
    int fullLevels = log2(totalNodes + 1);
    int lastLevelNodes = totalNodes - (pow(2, fullLevels) - 1);
    int leftSubtreeNodes = pow(2, fullLevels - 1) - 1 + min((int)pow(2, fullLevels - 1), lastLevelNodes);

    // 根据左子树的节点数确定根节点
    int rootIndex = start + leftSubtreeNodes;
    TreeNode* root = new TreeNode(sortedValues[rootIndex]);
    root->left = createTree(start, rootIndex - 1, sortedValues);
    root->right = createTree(rootIndex + 1, end, sortedValues);

    return root;
}

// 层次遍历
void traversal(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* current = q.front(); q.pop();
        cout << current->val << " ";
        if (current->left) q.push(current->left);
        if (current->right) q.push(current->right);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> values(n);
    for (int& value : values) {
        cin >> value;
    }
    sort(values.begin(), values.end());

    TreeNode* root = createTree(0, n - 1, values);
    traversal(root);
    return 0;
}

直接计算

#include<bits/stdc++.h>
using namespace std;
struct TreeNode{
    TreeNode * left=nullptr;
    TreeNode * right=nullptr;
    int val;
    TreeNode (int v=0):val(v) {}
};
TreeNode * createTree(int left,int right,vector<int> & baby){//O(nlogn)
    if(left>right) return nullptr;
    if(left==right) return new TreeNode(baby[left]);
    TreeNode * root=nullptr;
    int flag=right-left+2;
    int b=1;
    while(flag!=1){//O(logn) 每次建树logn，n个结点共nlogn
        b*=2;
        flag>>=1;
    }
    int rightTree_size=b/2-1;
    if(rightTree_size+2-b-b/2>0){
       rightTree_size+=rightTree_size+2-b-b/2;
    }
    root=new TreeNode(baby[right-rightTree_size]);
    root->left=createTree(left,right-rightTree_size-1,baby);
    root->right=createTree(right-rightTree_size+1,right,baby);
    return root;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> baby;
    for(int i=0;i<n;++i){
        int j;cin>>j;
        baby.emplace_back(j);
    }
    sort(baby.begin(),baby.end());//O(nlogn)
    createTree(0,n-1,baby);
    return 0;
}