博客

二叉树的一个重要应用是查找其中的元素，二叉搜索树就是针对数据的动态查找而设计的一种高效的数据结构类型。二叉搜索树是一种特殊的二叉树，它可以为空；如果不为空，满足以下性质：1.  非空 左子树 的所有键值小于其根结点的键值。2.  非空 右子树 的所有键值大于其根结点的键值。3.  左右子树都是二叉搜索树。

由于定义的不同，二叉搜索树也有一些不同于二叉树的操作函数，本文实现了二叉搜索树的指定元素查找、最小元素查找、最大元素查找、插入和删除元素等功能。常用的如AVL树等二叉搜索树，其高度的最大值为O(logN)，N为节点的个数。正因为如此，在编写二叉搜索树的程序时，一般不必担心栈空间被用完。

类型定义和函数声明

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

typedef struct BiTNode{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
} BiTNode, *BiTree, *Position;

void CreateBiTree(BiTree *T);
void ProOrderTraversal(BiTree T);
Position Find(int tar, BiTree T);
Position Find2(int tar, BiTree T);
Position FindMax(BiTree T);
Position FindMin(BiTree T);
BiTree Insert(int data, BiTree T);
BiTree Delete(int data, BiTree T);

在二叉搜索树中查找指定元素

查找的效率取决于树的高度（每递归一次，程序进入树的下一层进行查找）。查找操作的思想也可应用到接下来的插入操作和删除操作。查找程序是用尾递归的方法实现的，而尾递归的程序都可以转换成循环的形式。关于尾递归的理解见点击打开链接

//从二叉搜索树T中查找元素，返回其所在结点的地址(尾递归实现)
Position Find(int tar, BiTree T)
{
	if (!T)/*没有找到该元素*/
		return NULL;
	if (tar > T->data)/*该元素在该节点的右子树中*/
		return Find(tar, T->rchild);
	else if (tar < T->data)/*该元素在该节点的左子树中*/
		return Find(tar, T->lchild);
	else/*找到该元素*/
		return T;
}

//从二叉搜索树T中查找元素，返回其所在结点的地址(循环实现)
Position Find2(int tar, BiTree T)
{
    while (T && T->data != tar)
    {
        if (T->data > tar)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

查找搜索二叉树中最小和最大元素

依据搜索二叉树的结构特点，查找最小最大元素分别就是分别寻找树的最左端结点和最右端结点。

//查找最小元素（尾递归）
Position FindMin(BiTree T)
{
	if (!T)
		return NULL;
	else if (!T->lchild)
		return T;
	else
		return FindMin(T->lchild);
}

//查找最大元素（迭代）
Position FindMax(BiTree T)
{
	if (T)/*没有该判断语句 对空树是不安全的*/
	{
		while (T->rchild)
			T = T->rchild;
	}
	return T;
}

在搜索二叉树中插入元素

插入操作的关键是找到元素应该插入的位置，其思想与Find函数类似。

//插入元素(递归)
//最终返回元素为根节点指针
BiTree Insert(int data, BiTree T)
{
	if (!T)//找到插入位置,进行插入
	{
		T = (BiTree)malloc(sizeof(BiTNode));
		T->data = data;
		T->lchild = T->rchild = NULL;
	}
	else if (data > T->data)//进行右子树递归插入
		T->rchild = Insert(data, T->rchild);
	else if (data < T->data)//进行左子树递归插入
		T->lchild = Insert(data, T->lchild);
        else//插入失败
                printf("元素已经存在，插入失败");
	return T;
}

在搜索二叉树中删除元素

删除函数是这里面最困难的函数。被删除元素有三种具体情况：叶子结点、度为1的结点和度为2的结点。关键在于将度为2的结点通过其左子树的最大元素或右子树的最小元素替换成度为1的结点而完成删除操作。

//删除元素(递归)
//最终返回元素为根节点指针
BiTree Delete(int data, BiTree T)
{
	Position Tmp;

	if (!T)
		printf("没有找到待删除元素");
	else if (data > T->data)//进行右子树递归删除
		T->rchild = Delete(data, T->rchild);
	else if(data < T->data)//进行左子树递归删除
		T->lchild = Delete(data, T->lchild);
	//找到对应节点
	else if (T->lchild && T->rchild)//被删除节点有左右两个子节点(需要转换成有一个子节点或没有子节点的情况)
		{
			Tmp = FindMax(T->lchild);
			T->data = Tmp->data;
			T->lchild = Delete(T->data, T->lchild);
		}
	else//被删除节点有一个子节点或没有子节点
		{
			Tmp = T;
			if (!T->rchild)//有左节点或没有子节点
				T = T->lchild;
			else if (!T->lchild)//有右节点或没有子节点
				T = T->rchild;
			free(Tmp);
		}
	return T;
}

二叉树的创建与遍历

为完成新函数的测试，用到了前边博文中编写的二叉树创建函数和二叉树遍历函数，通过二叉树创建函数手动创建一个BST。

注：在创建二叉树时，输入0表示该结点为空！

//根据前序扩展序列建立二叉树
void CreateBiTree(BiTree *T)//注意：T为指向结构体的指针的指针 
{							
	int data, tmp;

	scanf_s("%d", &data);
	tmp = getchar();

	if (data == 0)//0标致着节点为空。
		*T = NULL;
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!(*T)) exit(-1);//分配内存空间失败
		(*T)->data = data;
		printf("输入%d的左子节点：", data);//这句便于调试、找错和验证结果的正确性！
		CreateBiTree(&(*T)->lchild);
		printf("输入%d的右子节点：", data);//这句便于调试、找错和验证结果的正确性！
		CreateBiTree(&(*T)->rchild);
	}
}

//前序遍历二叉树(递归)
void ProOrderTraversal(BiTree T)
{
	if (T)
	{
		printf("%d ", T->data);
		ProOrderTraversal(T->lchild);
		ProOrderTraversal(T->rchild);
	}
}

测试程序

二叉搜索树的前序扩展序列（即测试数据）：30 15 0 18 0 0 41 33 0 0 50 0 0

void main()
{
	BiTree T;
	int tar;

	printf("请输入数据：");
	CreateBiTree(&T);
	printf("前序遍历结果为：");
	ProOrderTraversal(T);
	
	printf("\n请输入要查找的数据：");
	scanf_s("%d", &tar);
	if (!Find2(tar, T))
		printf("树中没有找到该元素\n");
	else
		printf("%d\n", Find2(tar, T)->data);
	
	printf("树中最小元素为%d\n", FindMin(T)->data);
	printf("树中最大元素为%d\n", FindMax(T)->data);

	printf("请输入要插入的元素：");
	scanf_s("%d", &tar);
	printf("%d\n", Insert(tar, T)->data);
	printf("前序遍历结果为：");
	ProOrderTraversal(T);

	
	printf("\n请输入要删除的元素：");
	scanf_s("%d", &tar);
	printf("%d\n", Delete(tar, T)->data); 
	printf("前序遍历结果为：");
	ProOrderTraversal(T);
		
}