快捷導(dǎo)航

C語(yǔ)言實(shí)例實(shí)現(xiàn)二叉搜索樹(shù)詳解

更新時(shí)間：2022年05月24日 10:40:07 作者：litian355

二叉搜索樹(shù)是以一棵二叉樹(shù)來(lái)組織的。每個(gè)節(jié)點(diǎn)是一個(gè)對(duì)象，包含的屬性有l(wèi)eft，right，p和key，其中，left指向該節(jié)點(diǎn)的左孩子，right指向該節(jié)點(diǎn)的右孩子，p指向該節(jié)點(diǎn)的父節(jié)點(diǎn)，key是它的值

#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;
}

二叉樹(shù)代碼實(shí)現(xiàn)

講的非常清楚。

為了構(gòu)建一顆便于查找數(shù)據(jù)的樹(shù)形結(jié)構(gòu)，我們規(guī)定樹(shù)的節(jié)點(diǎn)的數(shù)據(jù) value leftnode<value root <value rightnode

這樣的一棵樹(shù)叫做二叉搜索樹(shù)

為了簡(jiǎn)單記憶我們就按函數(shù)中的根被訪問(wèn)的順序分為前序（pre），中序（in），后序（post）

代碼主要涉及前中后序遍歷和求二叉搜索樹(shù)的高度，和二叉搜索樹(shù)的最大值的一共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){//二叉樹(shù)的前序遍歷
	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;
}

看起來(lái)很長(zhǎng)但是實(shí)際上原理很簡(jiǎn)單，這是工程代碼的特點(diǎn)，用數(shù)組模擬雖然會(huì)簡(jiǎn)單很多，但是無(wú)奈，兩種都要會(huì)呀……

數(shù)組模擬版本：

const  int N=2e5+10;
int cnt[N];// 結(jié)點(diǎn)x的值val出現(xiàn)的次數(shù)；
int  lc[N],rc[N],sz[N];//結(jié)點(diǎn)x的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)以及以x為節(jié)點(diǎn)的子樹(shù)大小
int val[N];//結(jié)點(diǎn)x存儲(chǔ)的數(shù)值
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) {//如果節(jié)點(diǎn)o對(duì)應(yīng)的值就是v 退出循環(huán)
       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;//遞歸終點(diǎn)
  }else {
      int u=deletemin(lc[o]);//用左子樹(shù)的最大值替換他，然后將它刪除
      sz[o]-=cnt[u];
      return u;
  }
}
void del(int &o,int v){
    sz[o]--;
    if(val[o]==v){
        if(cnt[o]>1) {//結(jié)點(diǎn)多于一個(gè)元素，--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);
}
//時(shí)間復(fù)雜度O（h） h為樹(shù)的高度
//1.查找元素的排名
// 查找一個(gè)元素的排名，首先從根節(jié)點(diǎn)跳到這個(gè)元素，若向右跳，答案加上
//左兒子結(jié)點(diǎn)的個(gè)數(shù)加上當(dāng)前結(jié)點(diǎn)的個(gè)數(shù)，最后答案加上終點(diǎn)的左子樹(shù)的大小加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的元素
//根節(jié)點(diǎn)的排名取決于其左子樹(shù)的大小
//若其左子樹(shù)的大小大于等于k，則該元素在左子樹(shù)，若其左子樹(shù)大小在[k-cnt,k-1]則該元素為子樹(shù)的根節(jié)點(diǎn)。
//若其左子樹(shù)的大小小于k-cnt，則稱該元素在右子樹(shù)中
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];
}

到此這篇關(guān)于C語(yǔ)言實(shí)例實(shí)現(xiàn)二叉搜索樹(shù)詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言二叉搜索樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: