二叉查找树C语言实现
1. 二叉查找树的定义：
左子树不为空的时候，左子树的结点值小于根节点，右子树不为空时，右子树的结点值大于根节点，左右子树分别为二叉查找树
2. 二叉查找树的最左边的结点即为最小值，要查找最小值，仅仅需遍历左子树的结点直到为空为止，同理，最右边的结点结尾最大值，要查找最大值，仅仅需遍历右子树的结点直到为空为止。二叉查找树的插入查找和删除都是通过递归的方式来实现的，删除一个结点的时候，先找到这个结点S，然后并非真正的删除这个结点S，而是在其右子树找到后继结点，将后继结点的值付给S，然后删除这个后继结点就可以。
3. 二叉查找树的C实现：
# include <iostream>
# include <cstdlib>
using namespace std; struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
}; TreeNode *insert(TreeNode *root,int val) //插入元素
{
if(root==NULL)
{
root=new TreeNode(val);
return root;
}
if(val<root->val)
root->left=insert(root->left,val);
if(val>root->val)
root->right=insert(root->right,val);
return root;
} TreeNode *findmin(TreeNode *root)
{
if(root==NULL)
return NULL;
if(root->left==NULL&&root->right==NULL)
return root;
if(root->left)
return findmin(root->left);
} bool find(TreeNode *root,int val) //查找元素，若存在返回1，不存在返回0
{
if(root==NULL)
return false;
if(root->val==val)
return true;
if(val<root->val)
return find(root->left,val);
else
return find(root->right,val);
return false;
} TreeNode *delnum(TreeNode *root,int val)
{
if(root==NULL)
return NULL;
if(val>root->val)
root->right=delnum(root->right,val);
else if(val<root->val)
root->left=delnum(root->left,val);
else
{
if(root->left&&root->right) //待删除结点有两个孩子的情形
{
TreeNode *tmp=findmin(root->right);
root->val=tmp->val;
root->right=delnum(root->right,tmp->val);
}
else //待删除结点仅仅有一个或者没有孩子
{
if(root->left==NULL)
root=root->right;
else if(root->right==NULL)
root=root->left;
}
}
return root;
} int main() //測试代码
{ TreeNode *root=NULL;
root=insert(root,3);
root=insert(root,2);
root=insert(root,4);
root=insert(root,1);
cout<<find(root,2)<<endl;
root=delnum(root,2);
cout<<find(root,2)<<endl;
system("pause");
return 0;
}