C语言实例实现二叉搜索树详解
时间：2022-09-06 13:35:52|栏目：C代码|点击： 次
有些算法题里有了这个概念，因为不知道这是什么蒙圈了很久。
先序遍历： root——>left——>right
中序遍历： left—— root ——>right
后序遍历 ：left ——right——>root
先弄一个只有四个节点的小型二叉树，实际上这种小型二叉树应用不大。
二叉树的真正应用是二叉搜索树，处理海量的数据。
代码很简单，两种遍历的代码也差不多
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *left;
struct node *right;
}Node;
void preorder(Node *p){//前序遍历
if(p!=NULL){
printf("%d\n",p->data);
preorder(p->left);
preorder(p->right);
}
}
void inorder(Node *p){//中序遍历
if(p!=NULL){
inorder(p->left);
printf("%d\n",p->data);
inorder(p->right);
}
}
int main(){
Node n1;
Node n2;
Node n3;
Node n4;
n1.data=15;
n2.data=32;
n3.data=44;
n4.data=17;
n1.left=&n2;
n1.right=&n3;
n2.left=&n4;
n2.right=NULL;
n3.left=NULL;
n3.right=NULL;
n4.left=NULL;
n4.right=NULL;
preorder(&n1);
puts(" ");
inorder(&n1);
// 15
// / \
// 32 44
// / \ / \
// 17
return 0;
}
讲的非常清楚。
为了构建一颗便于查找数据的树形结构，我们规定 树的节点的数据 value leftnode<value root <value rightnode
这样的一棵树叫做二叉搜索树
为了简单记忆我们就按函数中的根被访问的顺序分为前序（pre），中序（in），后序（post）
代码主要涉及前中后序遍历和求二叉搜索树的高度，和二叉搜索树的最大值的一共5中基本操作
#include<stdio.h>
#include<stdlib.h>
#define max(a,b) a>b?a:b
typedef struct node{
int data;
struct node *left;
struct node *right;
}Node;
typedef struct {
Node *root;
}Tree;
void insert(Tree*tree,int x){
Node *node;
node=(Node*)malloc(sizeof (Node));
node->data=x,node->left=NULL,node->right=NULL;
if(tree->root==NULL){
tree->root=node;
}else {
Node *temp=tree->root;
while(temp!=NULL){
if(x<temp->data){//如果左儿子的data<x ，考虑左边
if(temp->left==NULL){
temp->left=node;
return ;
} else temp=temp->left;
}else { //如果右儿子的data>x ，考虑右边
if(temp->right==NULL){
temp->right=node;
return ;
}else temp=temp->right;
}
}
}
}
void preorder(Node*node){//二叉树的前序遍历
if(node!=NULL){
printf("%d\n",node->data);
preorder(node->left);
preorder(node->right);
}
}
void inorder(Node*node){
if(node!=NULL){
inorder(node->left);
printf("%d\n",node->data);
inorder(node->right);
}
}
void postorder(Node*node){
if(node!=NULL){
postorder(node->left);
postorder(node->right);
printf("%d\n",node->data);
}
}
int get_height(Node *node){//递归求高度h=max(Heightleftsob,Heightrightson);
if(node==NULL){
return 0;
}else {
int m1=get_height(node->left);
int m2=get_height(node->right);
int m=max(m1,m2);
return m+1;
}
}
int max_e(Node*node){//递归求解最大值,max_e=max{root->data,max_leftson_e,max_rightson_e};
if(node==NULL){
return -0x3f3f3f3f;
}else {
int m1=max_e(node->left);
int m2=max_e(node->right);
int m=node->data;
return max(max(m1,m2),m);
}
}
int main(){
Tree tree;
tree.root=NULL;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
int t;
scanf("%d",&t);
insert(&tree,t);
}
preorder(tree.root);
inorder(tree.root);
postorder(tree.root);
int h=get_height(tree.root);
printf("h==%d\n",h);
int max_ele=max_e(tree.root);
printf("max_element==%d",max_ele);
return 0;
}
看起来很长但是实际上原理很简单，这是工程代码的特点，用数组模拟虽然会简单很多，但是无奈，两种都要会呀……
数组模拟版本：
const int N=2e5+10;
int cnt[N];// 结点x的值val出现的次数；
int lc[N],rc[N],sz[N];//结点x的左子结点和右子结点以及以x为节点的子树大小
int val[N];//结点x存储的数值
int n;
void print(int o){
if(!o) return ;
print(lc[o]);
for(int i=1;i<=cnt[o];i++) printf("%d\n",val[o]);
print(rc[o]);
}
int findmin(int o){
if(!lc[o]) return o;
return findmin(lc[o]);
}
int findmax(int o){
if(!rc[o]) return o;
return findmax(rc[o]);
}
void insert(int &o,int v){
if(!o) {
val[o=++n]=v;
cnt[o]=sz[o]=1;
lc[o]=rc[o]=0;
return ;
}
sz[o]++;
if(val[o]==v) {//如果节点o对应的值就是v 退出循环
cnt[o]++;
return ;
}
if(val[o]>v) insert(lc[o],v);
if(val[o]<v) insert(rc[o],v);
}
int deletemin(int &o){
if(!lc[o]){
int u=0;
o=rc[o];
return u;//递归终点
}else {
int u=deletemin(lc[o]);//用左子树的最大值替换他，然后将它删除
sz[o]-=cnt[u];
return u;
}
}
void del(int &o,int v){
sz[o]--;
if(val[o]==v){
if(cnt[o]>1) {//结点多于一个元素，--cnt
cnt[o]--;
return ;
}
if(lc[o]&&rc[o]) o=deletemin(rc[o]);
else o=lc[o]+rc[o];
return ;
}
if(val[o]>v) del(lc[o],v);
if(val[o]<v) del(rc[o],v);
}
//时间复杂度O（h） h为树的高度
//1.查找元素的排名
// 查找一个元素的排名，首先从根节点跳到这个元素，若向右跳，答案加上
//左儿子结点的个数加上当前结点的个数，最后答案加上终点的左子树的大小加1
int query(int o,int v){
if(val[o]==v) return sz[lc[o]]+1;
if(val[o]>v) return query(lc[o],v);
if(val[o]<v) return query(rc[o],v)+sz[lc[o]]+cnt[o];
}
//2.查找排名为k的元素
//根节点的排名取决于其左子树的大小
//若其左子树的大小大于等于k，则该元素在左子树，若其左子树大小在[k-cnt,k-1]则该元素为子树的根节点。
//若其左子树的大小小于k-cnt，则称该元素在右子树中
int querykth(int o,int k){
if(sz[lc[o]>=k] ) return querykth(lc[o],k);
if(sz[lc[o]]<k-cnt[o]) return querykth(rc[o],k-lc[o]-cnt[o]);
return val[o];
}
