数据结构：二叉搜索树(BST)

今天咱们来聊聊二叉搜索树,先从字面上来理解,二叉,指的是有两个分支，左子树和右子树；搜索树，啥意思呢，搜索，是不是就是之前学过dfs和bfs那边学过，对啊，dfs就是深度优先搜索，是不是用递归写的，是不是当时被搜索支配的很难受。。。。我也是的。。。
那么BST有什么特殊地方呢,这个问题就是我们讨论的重点和难点。
特殊:一颗大树而言，我们对于任何一个非叶子结点（如果不知道什么是叶子结点，叶子结点就是没有孩子结点），它的左子树的数值比根节点的数值小于或等于,右子树的数值比根节点的数值大，是不是很好理解，对于每个非叶子结点都符合这样的条件，那这颗树是不是非常特殊。咱们在仔细想想，对于一颗大树而言，根节点左边子树的数值是不是全部小于或等于根节点的数值,右子树的数值是不是全部大于根节点的数值，是不是很奇妙。

是不是很简单，我们发现对于每个非叶子结点是不是满足上面说的特征。
代码怎么写呢？？？？
首先我们需要先把这个树建立起来，是不是很容易想到递归建树，先看个代码，在代码中理解

struct node{ 
	int data;//数值
	node *lchild;//左孩子指针
	node *rchild;//右孩子指针
};
void build_BST(node *&root,int v){ 
	if(root==NULL){ //当遇到空结点的时候，说明这个地方符合条件并且正好是插入的地方
		root = new node;//新建一个结点
		root->data = v;//给结点赋值
		root->lchild = root->rchild = NULL;//标识一下，左右孩子都为空
		return ;//返回到该结点的上一个级，也就是父亲结点
	}
	else if(root->data<v) build_BST(root->rchild,v);//如果比该节点数值大，就往右子树搜索
	else build_BST(root->lchild,v);//如果比该节点数值小或等于，就往左子树搜索
}

是不是很简单

我们可以出个题目：有n个结点的树(编号:1-n),现在输出它所构成的二叉搜索树的前序遍历。（自己可以先尝试尝试）
输入:5
1 3 8 -2 9

输出:-2 1 3 8 9

#include<bits/stdc++.h>
using namespace std;
struct node{ 
	int data;
	node *lchild;//左孩子
	node *rchild;//右孩子
};
void build_BST(node *&root,int v){ 
	if(root==NULL){ //递归出口
		root = new node;//新建结点
		root->data = v;//赋值
		root->lchild = root->rchild = NULL;//左右孩子为空
		return ;
	}
	else if(root->data<v) build_BST(root->rchild,v);//右子树搜索
	else build_BST(root->lchild,v);//左子树搜索
}
//前序遍历
void pre_order(node *root){ 
	if(root==NULL) return ;
	pre_order(root->lchild);
	cout<<root->data<<" ";
	pre_order(root->rchild);
}
int main(){ 
	node *root = NULL;//先把根节点标为空结点
	int n,temp;
	cin>>n;//n个数
	for(int i=0;i<n;i++){ 
		cin>>temp;
		build_BST(root,temp);//对每个数进行插入
	}
	pre_order(root);//前序遍历
	return 0;
}

完了，撒花，撒花！！