学步园

学习二叉排序树时写的代码。

二叉排序树是一颗动态，是在动态的过程中生成的，不是一成不变的。

特点是：根节点左边的比根节点的值小，右边的值比根节点大，平均查找复杂度为O(log2*n);

用二维指针来建树，注意new node()，返回的是结构体指针。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <stack> 
using namespace std;

typedef struct node
{
	int data;
	struct node *left, *right;
}bst, *Link;

void inorder_print(Link L)
{
	if(L != NULL)
	{
		inorder_print(L->left);
		printf("%d\n", L->data);
		inorder_print(L->right);
	}
}

void insert(Link *L, int key)
{
	if(*L == NULL)
	{ 
		(*L) = new node();
		(*L)->left = (*L)->right = NULL;
		(*L)->data = key;
	}
	else
	{
		if(key == (*L)->data) return ;
		else if(key < (*L)->data) insert(&(*L)->left, key);
		else insert(&(*L)->right, key);
	}
}

Link *Search(Link *L, int key)
{
	if(*L)
	{
		if((*L)->data == key) return L;
	    if(key < (*L)->data) return Search(&(*L)->left, key);
	    else return Search(&(*L)->right, key);
	}
	return NULL;
}

Link Del(Link *L)
{
	if((*L)->left != NULL)
	{
		Link fa, cur;
		fa = cur = (*L)->left;
		while(cur != NULL)
		{
			fa = cur;
			cur = cur->left;
		}
		(*L)->data = cur->data;
		if(fa != cur) fa->right = cur->left;
		else (*L)->left = cur->left;
		free(cur);
	}
	else
	{
		Link cur = (*L);
		(*L) = (*L)->right;
		free(cur);
		cur = NULL;
	}
}

void calmin(Link *L, int &ans)
{
	Link p = (*L);
	ans = min(ans, p->data);
	while(p != NULL)
	{
		ans = min(ans, p->data);
		//printf("***%d\n", p->data);
		p = p->left;
	}
}

void calmax(Link *L, int &ans)
{
	Link p = (*L);
	ans = max(ans, p->data);
	while(p != NULL)
	{
		ans = max(ans, p->data);
		//printf("***%d\n", p->data);
		p = p->right;
	}
}

int main()
{
	Link L = NULL;
	for(;;)
	{
		printf("插入 查询 删除 遍历 最大值 最小值\n");
		int q; scanf("%d", &q);
		int x;
		if(q == 1)
		{
			scanf("%d", &x);
			insert(&L, x);
		}
		else if(q == 2)
		{
			scanf("%d", &x);
			Link *Q = Search(&L, x);
			if(Q) printf("存在\n");
			else printf("不存在\n");
		}
		else if(q == 3)
		{
			scanf("%d", &x);
			Link *Q = Search(&L, x);
			if(!Q) printf("不存在\n");
			else Del(Q);
		}
		else if(q == 4)
		{
			inorder_print(L);
		}
		else if(q == 5)
		{
			int ans = 0;
			calmax(&L, ans);
			printf("%d\n", ans);
		}
		else if(q == 6)
		{
			int ans = 100000000LL;
			calmin(&L, ans);
			printf("%d\n", ans);
		}
	}
	return 0;
}