二叉搜索树C语言代码实现

有些算法题里有了这个概念，因为不知道这是什么蒙圈了很久。

先序遍历： root——>left——>right

中序遍历： left—— root ——>right

后序遍历 ：left ——right——>root

先弄一个只有四个节点的小型二叉树，实际上这种小型二叉树应用不大。

二叉树的真正应用是二叉搜索树，处理海量的数据。

代码很简单，两种遍历的代码也差不多

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

[C语言教程]二叉树代码实现02_哔哩哔哩_bilibili

 讲的非常清楚。

为了构建一颗便于查找数据的树形结构，我们规定 树的节点的数据   value leftnode

这样的一棵树叫做二叉搜索树

为了简单记忆我们就按函数中的根被访问的顺序分为前序（pre），中序（in），后序（post）

代码主要涉及前中后序遍历和求二叉搜索树的高度，和二叉搜索树的最大值的一共5中基本 *** 作

#include
#include
#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(xdata){//如果左儿子的dataleft==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;
}

看起来很长但是实际上原理很简单，这是工程代码的特点，用数组模拟虽然会简单很多，但是无奈，两种都要会呀……