二叉排序树的基本操作
1.插入结点
2.删除结点
3.查找比x结点的前驱
4.查找x结点的后继
5.输出>=x结点的所有值
6.判断是否为二叉排序树
7.非递归插入结点
8.折半查找(八股文版)
9.求平衡二叉树的高度
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/**
* 插入、删除、查找
* 插入:根据值的大小找到叶结点插入
* 删除:叶结点直接删除;
* 单分支结点将左子树或右子树上提;
* 双分支结点找到前驱结点,将前驱结点赋值给双分支结点,删除该前驱结点
* 查找:找x的前驱,找到x左子树的最右结点的最大值并输出
*
*/
const int INF = 1e8;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int _val): val(_val), left(NULL), right(NULL){}
}*root;
void insert(TreeNode* &root, int x)
{
if(!root) root = new TreeNode(x);
if(root->val == x) return;//放在创建结点之后
else if(x < root->val) insert(root->left, x);
else insert(root->right, x);
}
void remove(TreeNode *&root, int x)
{
if(!root) return;
if(root ->val > x) remove(root->left, x);
else if(root ->val < x) remove(root->right, x);
else
{
if(!root->left && !root->right) root = NULL;
else if(!root->left || !root->right)
{
if(root->left) root = root->left;
else root = root->right;//这里不能用if(root->right)替代else,替代会出错,如果是用的单个的if(root->right)来判断就不能区分出是单分支结点还是双分支结点
}
// else if (!root->left) root = root->right;//判断条件必须是取反操作用于区分是双分支还是单分支
// else if (!root->right) root = root->left;
else
{
TreeNode* p = root->left;
while(p ->right) p = p->right;//注意先验证下一个点的位置后移动指针
root->val = p ->val;
remove(root->left, p->val);
}
}
}
int get_pre(TreeNode* root, int x)//递归找x的前驱结点,递归比较最小哨兵和根结点的值
{
if (!root) return -INF;
if (root->val >= x) return get_pre(root->left, x);
return max(root->val, get_pre(root->right, x));
}
int get_suc(TreeNode* root, int x)
{
if (!root) return INF;
if (root->val <= x) return get_suc(root->right, x);
return min(root->val, get_suc(root->left, x));
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int t, x;
cin >> t >> x;
if(t == 1) insert(root, x);
if(t == 2) remove(root, x);
if(t == 3) cout << get_pre(root, x) << endl;
if(t == 4) cout << get_suc(root, x) << endl;
}
}
5.输出所有>=x结点的值
void Print(TreeNode* T)
{ //中序输出 T 为根的二叉排序树的所有结点
//首先从根结点开始查找,找到数值小于 x
//的结点后,将其与双亲断开;如果根结点值小于x,则沿右子树查找第一个大于等于 x
//的结点,找到后与上面做同样的处理,输出处理后的二叉排序树
if(T)
{
Print(T->left);
cout<<T->val << " ";
Print(T->right);
}
}
void Printx(TreeNode*& T, int x)
{
auto p = T;
if(p)
{
while(p && p->val < x) p = p->right;
T = p;
if(p)
{
auto q = p;
p = p->left;
while(p && p->val >= x) {q = p; p = p -> left;}
if(p) q ->left =NULL;
}
}
Print(T);
}
6.判断是否为二叉排序树
//1. 假设T为二叉排序树
//2. 中序遍历二叉树,判断根结点是否比它上一个结点要来的大,来的大话就将该结点设置为上一个结点。否则非二叉排序树
TreeNode* pre = NULL;
int flag = 1;
void JudgeBST(TreeNode* T)
{
if(T)
{
JudgeBST(T->left);
if(!pre) pre = T;
else if(pre->val < T->val) pre = T;
else flag = 0;
JudgeBST(T->right);
}
}
7.非递归插入结点
//1.生成一个结点存入x
//2.如果树为空则直接存入该结点
//3.树不为空则用p指针搜索树T,循环找到和x相同的值则计数加一返回,在树不为空时,分别找左或右同时记录父节点。如果循环后仍找不到则按二叉树定义存下该点
int sum = 0;
void SearchBST(TreeNode* &T, int x)
{
TreeNode* s = new TreeNode(x);
if(!T) {T = s; return;}
TreeNode* f =new TreeNode(0);
auto p = T;
while(p)
{
if(p->val == x) { sum += 1; return; }
else if(p->val > x) {f = p; p = p->left;}
else {f = p; p = p->right;}
}
if(f->val > x) f->left = s;
else f->right = s;
}
8.折半查找算法
//非递归
int search_binary(int a[],int n,int x)
{
int l = 1, r = n;
while(l <= r)
{
int mid = (l + r) / 2;
if(a[mid] == x) return mid;
else if(a[mid] > x) r = mid - 1;
else l = mid + 1;
}
return 0;
}
//折半查找记录比较次数
int search_binary(int a[],int n,int x)
{
int l = 1, r = n;
int num = 0;
while(l <= r)
{
int mid = (l + r) / 2;
if(a[mid] == x) return num;
else if(a[mid] > x) r = mid - 1;
else l = mid + 1;
num ++;
}
num --;
return num;
}
//递归版
int search_binary(int a[],int n, int x, int l, int r)
{
if(l > r) return 0;
int mid = l + r>> 1;
if(a[mid] == x) return mid;
else if(a[mid] > x) return search_bianry(a, n, x, l, mid - 1);
else return search_bianry(a, n, x, mid + 1, r);
}
9.求平衡二叉树的高度
int Height(TreeNode* T)//需要一棵树,每个节点含有平衡因子,平衡因子<0则右子树比左子树大 ,平衡因子>0则右子树比左子树小
{
int level = 0;
auto p = T;
while(p)
{
level ++;
if(p->b < 0) p = p->right;
else p = p->left
}
return level;
}