二叉树搜索树

简单的二叉树搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
原理：二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。
代码实现：
定义的二叉搜索树的数据结构体

typedef int BDataType;

typedef struct BSTreeNode
{
	struct BSTreeNode* _pLeft;
	struct BSTreeNode* _pRight;
	BDataType _data;
}BSTNode;

初始化二叉搜索树，很简单，就是将他置为空就好。

void InitBSTree(BSTNode** pRoot)
{
	assert(*pRoot);
	*pRoot = NULL;
}

往二叉搜索树中插入节点：首先封装一个买节点的函数出来，然后插入函数采用递归的方式。注意一点，二叉搜索树中不允许出现重复的元素，因此也不能插入相同的元素。

BSTNode* BuyNode(BDataType data)
{
	BSTNode* temp = NULL;
	temp = (BSTNode*)malloc(sizeof(BSTNode));
	if (!temp)
	{
		assert(0);
		return;
	}
	temp->_data = data;
	temp->_pLeft = temp->_pRight = NULL;
}


int InsertBSTree(BSTNode** pRoot, BDataType data)
{
	if (NULL == *pRoot)
	{
		*pRoot = BuyNode(data);
		return 1;
	}
	else
	{
		if (data == (*pRoot)->_data)
			return 0;
		else if (data < (*pRoot)->_data)
			InsertBSTree(&((*pRoot)->_pLeft), data);
		else 
			InsertBSTree(&((*pRoot)->_pRight), data);
	}

插入的非递归写法:思路和递归的思路一样。

int InsertBSTree(BSTNode** pRoot, BDataType data)
{
	assert(pRoot);
	BSTNode* pCur = NULL;
	BSTNode* pParent = NULL;

	if (*pRoot == NULL)
	{
		*pRoot = BuyNode(data);
		return 1;
	}

	pCur = *pRoot;
	while (pCur)
	{
		pParent = pCur;
		if (data < pCur->_data)		
			pCur = pCur->_pLeft;
		else if (data>pCur->_data)
			pCur = pCur->_pRight;
		else
			return 0;
	}

	pCur = BuyNode(data);
	if (data < pParent->_data)
		pParent->_pLeft = pCur;
	else
		pParent->_pRight = pCur;

	return 1;
}

删除一个二叉搜索树中一个节点：采用递归的方式先找到要删除的节点，然后在判断该节点是叶子节点还是只有左子树或者只有右字树或者左右子树都存在。不同的情况分别处理。

int DeleteBSTree(BSTNode** pRoot, BDataType data)
{
	if (NULL == *pRoot)
		return 0;

	if (data < (*pRoot)->_data)
		DeleteBSTree(&((*pRoot)->_pLeft), data);
	else if (data>(*pRoot)->_data)
		DeleteBSTree(&((*pRoot)->_pRight), data);
	else
	{
		BSTNode* del_node = *pRoot;
		if ((*pRoot)->_pRight == NULL)
		{
			*pRoot = del_node->_pLeft;
			free(del_node);
			return 1;
		}
		else if ((*pRoot)->_pLeft == NULL)
		{
			*pRoot = del_node->_pRight;
			free(del_node);
			return 1;
		}
		else
		{
			BSTNode* temp = (*pRoot)->_pRight;

			while (temp->_pLeft)
				temp = temp->_pLeft;
			(*pRoot)->_data = temp->_data;

			return(DeleteBSTree(&((*pRoot)->_pRight), temp->_data));
		}
	}
}

删除的非递归写法：只是将递归变成了循环，思路大体上都是一样的。

int DeleteBSTree(BSTNode** pRoot, BDataType data)
{
	assert(pRoot);
	BSTNode* pCur = NULL;
	BSTNode* pParent = NULL;
	if (*pRoot == NULL)
		return 0;

	pCur = *pRoot;
	while (pCur)
	{
		pParent = pCur;
		if (data == pCur->_data)
			break;
		else if (data < pCur->_data)
			pCur = pCur->_pLeft;
		else
			pCur = pCur->_pRight;
	}

	if (pCur == NULL)
		return 0;

	if (NULL == pCur->_pLeft)
	{
		if (pCur == *pRoot)
			*pRoot = pCur->_pRight;
		else
		{
			if (pParent->_pLeft == pCur)
				pParent->_pLeft = pCur->_pRight;
			else
				pParent->_pRight = pCur->_pRight;
		}
		free(pCur);
		pCur = NULL;
	}
	else if (NULL == pCur->_pRight)
	{
		if (pCur == *pRoot)
			*pRoot = pCur->_pLeft;
		else
		{
			if (pParent->_pLeft == pCur)
				pParent->_pLeft = pCur->_pLeft;
			else
				pParent->_pRight = pCur->_pLeft;
		}
		free(pCur);
		pCur = NULL;
	}
	else
	{
		BSTNode* temp = pCur->_pRight;
		pParent = pCur;

		while (temp->_pLeft)
		{
			pParent = temp;
			temp = temp->_pLeft;
		}
			
		pCur->_data = temp->_data;

		if (pParent->_pLeft == temp)
			pParent->_pLeft = temp->_pRight;
		else
			pParent->_pRight = temp->_pRight;

		pCur = temp;
	}
	free(pCur);
	pCur = NULL;
}

查找二叉搜索树中的某一个节点：也是采用递归的方式，如果走到空节点还没有找到，那么说明这个节点没有在二叉搜索树中。

BSTNode* FindBSTree(BSTNode* pRoot, BDataType data)
{
	if (NULL == pRoot)
		return NULL;
	else if (data == pRoot->_data)
		return pRoot;
	else if (data < pRoot->_data)
		FindBSTree(pRoot->_pLeft, data);
	else
		FindBSTree(pRoot->_pRight, data);
}

查找的非递归写法

BSTNode* FindBSTree(BSTNode* pRoot, BDataType data)
{
	BSTNode* pCur = pRoot;
	
	while (pCur)
	{
		if (data == pCur->_data)
			return pCur;
		else if (data < pCur->_data)
			pCur = pCur->_pLeft;
		else
			pCur = pCur->_pRight;
	}

	if (pCur == NULL)
		return NULL;
}

删除二叉搜索树：采取递归的方式进行删除，先删除左右子树再删除根节点，一定要注意这个顺序，否则一开始删除了根节点，左右子树就会找不到。

void DestroyBSTree(BSTNode** pRoot)
{
	if (*pRoot)
	{
		DestroyBSTree(&((*pRoot)->_pLeft));
		DestroyBSTree(&((*pRoot)->_pRight));

		free(*pRoot);
		*pRoot = NULL;
	}
}

中序遍历二叉搜索树

void InOrder(BSTNode* pRoot)
{
	if (pRoot == NULL)
		return;
	InOrder(pRoot->_pLeft);
	printf("%d ", pRoot->_data);
	InOrder(pRoot->_pRight);
}

二叉树搜索树

最后附上的我的所有代码，包括测试代码

这个是递归方式的代码。

#pragma once


typedef int BDataType;

typedef struct BSTreeNode
{
	struct BSTreeNode* _pLeft;
	struct BSTreeNode* _pRight;
	BDataType _data;
}BSTNode;


void InitBSTree(BSTNode** pRoot);
int InsertBSTree(BSTNode** pRoot, BDataType data);
int DeleteBSTree(BSTNode** pRoot, BDataType data);
BSTNode* FindBSTree(BSTNode* pRoot, BDataType data);
void InOrder(BSTNode* pRoot);
void DestroyBSTree(BSTNode** pRoot);

///
// BSTree.c

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


void InitBSTree(BSTNode** pRoot)
{
	assert(*pRoot);
	*pRoot = NULL;
}

BSTNode* BuyNode(BDataType data)
{
	BSTNode* temp = NULL;
	temp = (BSTNode*)malloc(sizeof(BSTNode));
	if (!temp)
	{
		assert(0);
		return;
	}
	temp->_data = data;
	temp->_pLeft = temp->_pRight = NULL;
}


int InsertBSTree(BSTNode** pRoot, BDataType data)
{
	if (NULL == *pRoot)
	{
		*pRoot = BuyNode(data);
		return 1;
	}
	else
	{
		if (data == (*pRoot)->_data)
			return 0;
		else if (data < (*pRoot)->_data)
			InsertBSTree(&((*pRoot)->_pLeft), data);
		else 
			InsertBSTree(&((*pRoot)->_pRight), data);
	}
}


int DeleteBSTree(BSTNode** pRoot, BDataType data)
{
	if (NULL == *pRoot)
		return 0;

	if (data < (*pRoot)->_data)
		DeleteBSTree(&((*pRoot)->_pLeft), data);
	else if (data>(*pRoot)->_data)
		DeleteBSTree(&((*pRoot)->_pRight), data);
	else
	{
		BSTNode* del_node = *pRoot;
		if ((*pRoot)->_pRight == NULL)
		{
			*pRoot = del_node->_pLeft;
			free(del_node);
			return 1;
		}
		else if ((*pRoot)->_pLeft == NULL)
		{
			*pRoot = del_node->_pRight;
			free(del_node);
			return 1;
		}
		else
		{
			BSTNode* temp = (*pRoot)->_pRight;

			while (temp->_pLeft)
				temp = temp->_pLeft;
			(*pRoot)->_data = temp->_data;

			return(DeleteBSTree(&((*pRoot)->_pRight), temp->_data));
		}
	}
}


BSTNode* FindBSTree(BSTNode* pRoot, BDataType data)
{
	if (NULL == pRoot)
		return NULL;
	else if (data == pRoot->_data)
		return pRoot;
	else if (data < pRoot->_data)
		FindBSTree(pRoot->_pLeft, data);
	else
		FindBSTree(pRoot->_pRight, data);
}


void InOrder(BSTNode* pRoot)
{
	if (pRoot == NULL)
		return;
	InOrder(pRoot->_pLeft);
	printf("%d ", pRoot->_data);
	InOrder(pRoot->_pRight);
}


void DestroyBSTree(BSTNode** pRoot)
{
	if (*pRoot)
	{
		DestroyBSTree(&((*pRoot)->_pLeft));
		DestroyBSTree(&((*pRoot)->_pRight));

		free(*pRoot);
		*pRoot = NULL;
	}
}

void TestBSTree()
{
	BSTNode* pRoot;
	InitBSTree(&pRoot);
	int array[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
		InsertBSTree(&pRoot, array[i]);

	InOrder(pRoot);
	printf("\n");

	if (FindBSTree(pRoot, 0))
		printf("0 is in bstree\n");
	else
		printf("0 is not in bstree\n");

	if (FindBSTree(pRoot, 10))
		printf("10 is in bstree\n");
	else
		printf("10 is not in bstree\n");

	DeleteBSTree(&pRoot, 0);
	InOrder(pRoot);
	printf("\n");

	DeleteBSTree(&pRoot, 8);
	InOrder(pRoot);
	printf("\n");

	DeleteBSTree(&pRoot, 5);
	InOrder(pRoot);
	printf("\n");

	DestroyBSTree(&pRoot);
}

void main()
{
	TestBSTree();
	return 0;
}

这个是非递归方式的代码

#pragma once
#include <assert.h>
#include <malloc.h>
#include <stdio.h>

typedef int BDataType;

typedef struct BSTreeNode
{
	struct BSTreeNode* _pLeft;
	struct BSTreeNode* _pRight;
	BDataType _data;
}BSTNode;


void InitBSTree(BSTNode** pRoot)
{
	assert(pRoot);
	*pRoot = NULL;
}

BSTNode* BuyNode(BDataType data)
{
	BSTNode* Node = NULL;
	Node = (BSTNode*)malloc(sizeof(BSTNode));
	if (!Node)
	{
		assert(0);
		return;
	}
	Node->_data = data;
	Node->_pLeft = Node->_pRight = NULL;
}

int InsertBSTree(BSTNode** pRoot, BDataType data)
{
	assert(pRoot);
	BSTNode* pCur = NULL;
	BSTNode* pParent = NULL;

	if (*pRoot == NULL)
	{
		*pRoot = BuyNode(data);
		return 1;
	}

	pCur = *pRoot;
	while (pCur)
	{
		pParent = pCur;
		if (data < pCur->_data)		
			pCur = pCur->_pLeft;
		else if (data>pCur->_data)
			pCur = pCur->_pRight;
		else
			return 0;
	}

	pCur = BuyNode(data);
	if (data < pParent->_data)
		pParent->_pLeft = pCur;
	else
		pParent->_pRight = pCur;

	return 1;
}


int DeleteBSTree(BSTNode** pRoot, BDataType data)
{
	assert(pRoot);
	BSTNode* pCur = NULL;
	BSTNode* pParent = NULL;
	if (*pRoot == NULL)
		return 0;

	pCur = *pRoot;
	while (pCur)
	{

		if (data == pCur->_data)
			break;
		else if (data < pCur->_data)
		{
			pParent = pCur;
			pCur = pCur->_pLeft;
		}
		else
		{
			pParent = pCur;
			pCur = pCur->_pRight;
		}
	}

	if (pCur == NULL)
		return 0;

	if (NULL == pCur->_pLeft)
	{
		if (pCur == *pRoot)
			*pRoot = pCur->_pRight;
		else
		{
			if (pParent->_pLeft == pCur)
				pParent->_pLeft = pCur->_pRight;
			else
				pParent->_pRight = pCur->_pRight;
		}
		free(pCur);
		pCur = NULL;
	}
	else if (NULL == pCur->_pRight)
	{
		if (pCur == *pRoot)
			*pRoot = pCur->_pLeft;
		else
		{
			if (pParent->_pLeft == pCur)
				pParent->_pLeft = pCur->_pLeft;
			else
				pParent->_pRight = pCur->_pLeft;
		}
		free(pCur);
		pCur = NULL;
	}
	else
	{
		BSTNode* temp = pCur->_pRight;
		pParent = pCur;

		while (temp->_pLeft)
		{
			pParent = temp;
			temp = temp->_pLeft;
		}
			
		pCur->_data = temp->_data;

		if (pParent->_pLeft == temp)
			pParent->_pLeft = temp->_pRight;
		else
			pParent->_pRight = temp->_pRight;

		pCur = temp;
	}
	free(pCur);
	pCur = NULL;
}


BSTNode* FindBSTree(BSTNode* pRoot, BDataType data)
{
	BSTNode* pCur = pRoot;
	
	while (pCur)
	{
		if (data == pCur->_data)
			return pCur;
		else if (data < pCur->_data)
			pCur = pCur->_pLeft;
		else
			pCur = pCur->_pRight;
	}

	if (pCur == NULL)
		return NULL;
}


void InOrder(BSTNode* pRoot)
{
	if (pRoot == NULL)
		return;
	InOrder(pRoot->_pLeft);
	printf("%d ", pRoot->_data);
	InOrder(pRoot->_pRight);
}

void DestroyBSTree(BSTNode** pRoot)
{
	assert(pRoot);
	if (*pRoot)
	{
		DestroyBSTree(&((*pRoot)->_pLeft));
		DestroyBSTree(&((*pRoot)->_pRight));
		free(*pRoot);
		*pRoot = NULL;
	}
}

void TestBSTree()
{
	BSTNode* pRoot;
	InitBSTree(&pRoot);
	int array[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); ++i)
		InsertBSTree(&pRoot, array[i]);

	InOrder(pRoot);
	printf("\n");

	if (FindBSTree(pRoot, 0))
		printf("0 is in bstree\n");
	else
		printf("0 is not in bstree\n");

	if (FindBSTree(pRoot, 10))
		printf("10 is in bstree\n");
	else
		printf("10 is not in bstree\n");

	DeleteBSTree(&pRoot, 0);
	InOrder(pRoot);
	printf("\n");

	DeleteBSTree(&pRoot, 8);
	InOrder(pRoot);
	printf("\n");

	DeleteBSTree(&pRoot, 5);
	InOrder(pRoot);
	printf("\n");

	DestroyBSTree(&pRoot);
}

上方如果有问题，欢迎下方讨论。。。

二叉树搜索树

简单的二叉树搜索树

这个是递归方式的代码。

这个是非递归方式的代码

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器