二叉查找树C语言实现

绝地灬酷狼 2022-03-29 15:12 209阅读 0赞

二叉查找树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;
    }