二叉查找树-BinarySearchTree-C语言实现

灰太狼 2023-01-07 10:12 151阅读 0赞

## 二叉查找树-BinarySearchTree ##

二叉查找树即二叉树的左子树的值都小于根节点的值，右子树的值都大于根节点的值。有几个显而易见的性质：  
1.最左子节点为最小值；  
2.最右子节点为最大值；  
3.中序遍历得到从小到大的节点值序列。  
实现主要分为**binary\_search\_tree.h**和**binary\_search\_tree.c**两个文件，在linux上已经跑通并做了简单的测试。  
首先为binary\_search\_tree.h

typedef struct treenode{
        
    		int val;
    		struct treenode * left;
    		struct treenode * right;
    }TreeNode;
    #define bool int
    #define true 1
    #define false 0
    TreeNode * tree_node_init(int val);           //initial a node
    TreeNode * binary_search_tree_init(int val);  //initial root
    int find_min(TreeNode *root);
    int find_max(TreeNode *root);                 //find min and max node value
    void traverse(TreeNode * root);                //traverse the tree
    bool insert_node(TreeNode * root, int val);    //insert a node
    bool find(TreeNode * root, int val);           //find a node
    TreeNode * find_node_ptr(TreeNode * root, int val); //find a node pointer
    TreeNode * node_parent(TreeNode * root, int val); //find a node's parent
    TreeNode * book_delete_node(TreeNode * root, int val); //delete a node

.c实现

TreeNode * tree_node_init(int val){
        
    	TreeNode * temp  = malloc(sizeof(TreeNode));
    	temp -> val = val;
    	temp -> left = NULL;
    	temp -> right = NULL;
    	return temp;
    }
    TreeNode * binary_search_tree_init(int val){
        
    	TreeNode * root = tree_node_init(val);
    	return root;
    }
    int find_min(TreeNode *root){
        
    	if(root==NULL){
        
    		printf("root is empty\n");
    		return -1;
    	}
    	TreeNode * ptr = root;
    	int ret = root -> val;
    	while(ptr != NULL)
    	{
        
    		ret = ptr -> val;
    		ptr = ptr -> left;
    	}
    	return ret;	
    }
    int find_max(TreeNode *root){
        
    	if(root==NULL){
        
    		printf("root is empty\n");
    		return -1;
    	}
    	TreeNode * ptr = root;
    	int ret = root -> val;
    	while(ptr != NULL)
    	{
        
    		ret = ptr -> val;
    		ptr = ptr -> right;
    	}
    	return ret;	
    }
    void traverse(TreeNode * root){
        
    	if(root==NULL)
    		return;
    	traverse(root->left);
    	printf("%d\n",root->val);
    	traverse(root->right);	
    }
    bool insert_node(TreeNode * root, int val){
        
    	if(root==NULL)
    		return false;
    	if(val<(root->val))
    	{
        
    		if(root->left==NULL)
    		{
        
    			TreeNode * temp = tree_node_init(val);
    			root->left=temp;
    			return true;
    		}
    		else
    		{
        
    			insert_node(root->left,val);
    		}
    	}
    	else if(val>(root->val))
    	{
        
    		if(root->right==NULL)
    		{
        
    			TreeNode * temp = tree_node_init(val);
    			root->right=temp;
    			return true;
    		}
    		else
    		{
        
    			insert_node(root->right,val);
    		}
    	}
    	else
    	{
        
    		return true;
    	}
    }
    bool find(TreeNode * root, int val){
        
    	if(root==NULL)
    		return false;
    	if((root->val)==val)
    		return true;
    	else if((root->val)>val)
    		find(root->left,val);
    	else
    		find(root->right,val);
    }
    TreeNode * find_node_ptr(TreeNode * root, int val){
        
    	if(root==NULL)
    		return;
    	if((root->val)==val)
    		return root;
    	else{
        
    		find_node_ptr(root->left,val);
    		find_node_ptr(root->right,val);
    	}
    }
    TreeNode * node_parent(TreeNode * root, int val){
        
    	
    }
    TreeNode * book_delete_node(TreeNode * root, int val){
        
    	TreeNode * TempCell;
    	if(root==NULL){
        
    		printf("root is NULL\n");
    		return NULL;
    	}
    	else if(val<(root->val)){
        
    		root->left = book_delete_node(root->left,val);
    	}
    	else if(val>(root->val)){
        
    		root->right = book_delete_node(root->right,val);
    	}
    	else if(root->left && root->right){
        
    		TreeNode * t = root->right;
    		while(t->left!=NULL)
    			t=t->left;
    		TmpCell = t;
    		root->val = t->val;
    		root->right = book_delete_node(root->right,t->val);
    	}
    	else{
        
    		TmpCell = root;
    		if(root->left==NULL)
    			root = root->right;
    		else if(root->right==NULL)
    			root=root->left;
    		free(TmpCell);
    	}
    	return root;
    }