您的位置: 首页  >  文章  >  数据结构C_二叉搜索树

数据结构C_二叉搜索树

分类: 文章 • 2022-10-06 14:19:41

二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树

· 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值    

· 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

· 它的左右子树也分别为二叉搜索树,

数据结构C_二叉搜索树

int a [ ] = {5,3,4,1,7,8,2,6,0,9};

 

二叉搜索树基本操作

BinarySearchTree.h



#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>

typedef int BSTDataType;

typedef struct BSTreeNode
{
	struct BSTreeNode* _left;
	struct BSTreeNode* _right;
	BSTDataType _data;
}BSTreeNode;

//插入
int BSTreeInsert(BSTreeNode** tree, BSTDataType x);
//递归插入
int BSTreeInsert_R(BSTreeNode** tree, BSTDataType x);
//删除
int BSTreeRemove(BSTreeNode** tree, BSTDataType x);
//递归删除
int BSTreeRemove_R(BSTreeNode** tree, BSTDataType x);
//查找
BSTreeNode* BSTreeFind(BSTreeNode** tree, BSTDataType x);
//递归查找
BSTreeNode* BSTreeFind_R(BSTreeNode** tree, BSTDataType x);
//中序遍历
void BSTreeInOrder(BSTreeNode** tree);

BinarySearchTree.c

#include"BinarySearchTree.h"

//申请节点
BSTreeNode * BuyBSTreeNode(BSTDataType x)
{
	BSTreeNode * node = (BSTreeNode*)malloc(sizeof(BSTreeNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
	return node;
}

//插入
int BSTreeInsert(BSTreeNode** tree, BSTDataType x)
{
	BSTreeNode* cur;
	BSTreeNode*	root = *tree;
	if (root == NULL)
	{
		*tree = BuyBSTreeNode(x);
		return 1;
	}
	root = *tree;
	cur = root;
	while (root)
	{
		if (root->_data > x)
		{
			cur = root;
			root = root->_left;
		}
		else if (root->_data < x)
		{
			root = root->_right;
		}
		else
		{
			return 0;
		}
	}
	if (cur->_data>x)
		cur->_left = BuyBSTreeNode(x);
	else
		cur->_right = BuyBSTreeNode(x);
	return 1;
}

//递归插入
int BSTreeInsert_R(BSTreeNode** tree, BSTDataType x)
{
	assert(tree);
	if (*tree = NULL)
	{
		//二级指针解引用表示要查入位置的地址
		*tree = BuyBSTreeNode(x);
		return 1;
	}
	if ((*tree)->_data > x)
		return BSTreeInsert_R(&(*tree)->_left, x);
	else if ((*tree)->_data < x)
		return BSTreeInsert_R(&(*tree)->_right, x);
	else
		return 0;
}

//删除
int BSTreeRemove(BSTreeNode** tree, BSTDataType x)
{
	BSTreeNode* parent;
	BSTreeNode* cur;    
	cur = *tree;
	parent = NULL;
	while (cur)
	{
		if (cur->_data > x)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_data < x)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			//左为空或者右为空
			if (!cur->_left || !cur->_right)
			{
				if (parent == NULL)
				{
					if (cur->_left == NULL)
						*tree = cur->_right;
					else
						*tree = cur->_left;
					break;
				}
				if (parent->_left == cur)
				{
					if (cur->_left == NULL)
						parent->_left = cur->_right;
					else
						parent->_left = cur->_left;
					break;
					}
				else
				{
					if (cur->_left == NULL)
						parent->_right = cur->_right;
					else
						parent->_right = cur->_left;
					break;
				}
			}
			//左右都不为空
			else
			{
				//不能使用parent去充当临时指针
				BSTreeNode* ret;
				ret = cur->_right;
				while (ret->_left)
					ret = ret->_left;
				cur->_data = ret->_data;
				BSTreeRemove(&cur->_right, ret->_right);
			}
		}
	}
	if (cur == NULL)
		return 0;
	free(cur);
	cur = NULL;
	return 1;
}

//递归删除
int BSTreeRemove_R(BSTreeNode** tree, BSTDataType x)
{
	BSTreeNode* parent;
	BSTreeNode* cur;
	assert(tree);
	cur = *tree;
	parent = NULL;
	if (cur == NULL)
		return 0;
	if (cur->_data == x)
	{
		if (cur->_left == NULL)
			*tree = cur->_right;
		else if (cur->_right == NULL)
			*tree = cur->_left;
		else
		{
			parent = cur->_right;
			while (parent->_left)
				parent = parent->_left;
			cur->_data = parent->_data;
			return BSTreeRemove_R(&cur->_right, cur->_data);
		}
		free(cur);
		cur = NULL;
		return 1;
	}
	else if (cur->_data > x)
		return BSTreeRemove_R(&cur->_left, x);
	else
		return BSTreeRemove_R(&cur->_right, x);
	return 0;
}

//查找
BSTreeNode* BSTreeFind(BSTreeNode** tree, BSTDataType x)
{
	BSTreeNode* node = *tree;
	while (node)
	{
		if (node->_data > x)
			node = node->_right;
		else if (node->_data < x)
			node = node->_left;
		else
			return node;
	}
	return NULL;
}

//递归查找
BSTreeNode* BSTreeFind_R(BSTreeNode** tree, BSTDataType x)
{
	if (*tree == NULL)
		return NULL;
	if ((*tree)->_data > x)
		return BSTreeFind_R(&(*tree)->_left, x);
	if ((*tree)->_data < x)
		return BSTreeFind_R(&(*tree)->_right, x);
	else
		return *tree;
}

//中序遍历
void BSTreeInOrder(BSTreeNode** tree)
{
	if ((*tree) == NULL)
		return;
	BSTreeInOrder(&(*tree)->_left);
	printf("%d ", (*tree)->_data);
	BSTreeInOrder(&(*tree)->_right);
}

test.c

#include"BinarySearchTree.h"


void TestBSTree() 
{ 
	//BSTreeNode* tree = NULL; 
	//BSTreeInsert(&tree, 4); 
	//BSTreeInsert(&tree, 2); 
	//BSTreeInsert(&tree, 1); 
	//BSTreeInsert(&tree, 3); 
	//BSTreeInsert(&tree, 2); 
	//const BSTreeNode* node = BSTreeFind(tree, 2); 
	//printf("Find 2? %d\n", node->_data); 
	int a[] = {5,3,4,1,7,8,2,6,0,9}; 
	BSTreeNode* tree = NULL; 
	for (int i = 0; i < sizeof(a)/sizeof(a[0]); ++i) 
	{ 
		BSTreeInsert(&tree, a[i]); 
	} 
	BSTreeInOrder(&tree); 
	printf("\n"); 
	BSTreeRemove(&tree, 4); 
	BSTreeRemove(&tree, 8); 
	BSTreeRemove(&tree, 3); 
	BSTreeRemove(&tree, 7); 
	BSTreeRemove(&tree, 5); 
	BSTreeInOrder(&tree); 
	printf("\n");
	BSTreeRemove(&tree, 0); 
	BSTreeRemove(&tree, 1); 
	BSTreeRemove(&tree, 2); 
	BSTreeRemove(&tree, 3); 
	BSTreeRemove(&tree, 4); 
	BSTreeRemove(&tree, 5); 
	BSTreeRemove(&tree, 6); 
	BSTreeRemove(&tree, 7); 
	BSTreeRemove(&tree, 8); 
	BSTreeRemove(&tree, 9);  
	BSTreeInOrder(&tree); 
	printf("\n"); 
} 

int main()
{
	TestBSTree();
	system("pause");
	return 0;
}

 

相关推荐