二叉搜索树查找 PTA
时间: 2025-01-10 17:24:25 浏览: 9
关于二叉搜索树的查找算法实现
构建二叉排序树
构建二叉排序树的过程涉及逐个插入节点,每次插入都遵循左子树小于根节点、右子树大于根节点的原则。
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}
此函数用于向已有的二叉排序树root
中插入新值val
[^1]。
计算平均查找长度
对于任意一棵二叉树来说,计算其所有结点在等概率情况下的平均查找长度可以通过遍历整棵树来统计各个节点的高度总和再除以节点数得出:
int getHeight(TreeNode* node) {
if (!node) return 0;
return max(getHeight(node->left), getHeight(node->right)) + 1;
}
double calculateASL(TreeNode* root) {
double sumHeights = 0;
queue<pair<TreeNode*, int>> q; // 存储<节点指针, 当前高度>
q.push({root, 1});
while (!q.empty()) {
auto p = q.front();
q.pop();
sumHeights += p.second;
if (p.first->left != nullptr)
q.push({p.first->left, p.second + 1});
if (p.first->right != nullptr)
q.push({p.first->right, p.second + 1});
}
int nNodes = countNodes(root); // 假设有一个countNodes()可以返回节点总数
return sumHeights / nNodes;
}
这段代码实现了对给定二叉树root
求解其平均查找长度的功能[^2]。
转化为平衡二叉树
为了使普通的二叉排序树转变为AVL树(即自调整的平衡二叉树),每当执行一次插入操作之后都需要检查当前路径上的每一个祖先节点是否满足平衡条件,并通过旋转等方式维持整个结构处于平衡状态。具体细节较为复杂,这里仅给出框架性的描述而不展开具体的旋转逻辑。
// 插入的同时保持平衡性质
TreeNode* balancedInsert(TreeNode*& root, int key) {
if (!root) {
root = new TreeNode(key);
return root;
}
if (key < root->val){
balancedInsert(root->left, key);
// 更新height...
// 判断失衡并做相应旋转...
}else{
balancedInsert(root->right, key);
// 同理处理右侧分支的情况...
}
return root;
}
上述伪码展示了如何在一个已经存在的二叉排序树基础上逐步建立成一个自动维护平衡特性的AVL树。