当前位置:首页 > IT技术

数据结构之二叉排序树(C语言实现)

时间:2019-11-08 00:12:16来源:IT技术作者:SEO探针小编阅读:73次「手机版」
 

排序二叉树

一、基本概念

1.二叉排序树

二叉排序树(binary sort tree,BST),又称为二叉查找树,或者是一棵空树;或者是具有下列性质的二叉树

(1)若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值;

(2)若它的右子树不为空,则右子树上所有节点的值均大于它的根节点的值;

(3)它的左、右子树也分别为二叉排序树。

二、二叉排序树操作

   二叉排序树是一种动态树表。它的特点是树的结构不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的节点时再进行插入。新插入的节点一定是一个新添加的叶子结点,并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子节点,

二叉排序树的操作有插入、删除、查询和遍历等。

注意:二叉排序树中没有值相同的节点

(1)插入

a.插入过程比较简单,首先判断当前要插入的值是否已经存在二叉排序树中,如果已经存在,则直接返回;如果不存在,则转b;

b.当前要插入的值不存在,则应找到适当的位置,将其插入。注意插入的新节点一定是叶子节点;

(2)删除

a.和插入一样,要删除一个给定值的节点,首先要判断这样节点是否存在,如果已经不存在,则直接返回;如果已经存在,则获取给定值节点的位置,根据不同情况进行删除、调整,转b;

b.如果待删节点只有左子树(只有右子树),则直接将待删节点的左子树(右子树)放在待删节点的位置,并释放待删节点的内存,否则转c;

    

c.如果待删节点既有左子树又有右子树,此时的删除可能有点复杂,但是也比较好理解。就是在待删节点的左子树中找到值最大的那个节点,将其放到待删节点的位置。

(3)查询

查询过程比较简单,首先将关键字和根节点的关键字比较,如果相等则返回节点的位置(指针);否则,如果小于根节点的关键字,则去左子树中继续查找;如果大于根节点的关键字,则去右子树中查找;如果找到叶子节点也没找到,则返回NULL。

查询过程的最好情况就是上面的图中那样,节点在左右子树中分布比较均匀,此时查找的时间复杂度为O(logn);最坏的情况就是在建立二叉排序树时,输入的关键字序列正好是有序的,此时形成的二叉排序树是一棵单支二叉树,此时查找退化成了单链表的查找,时间的复杂度为O(n).如下图:

(4)遍历

由上面二排序树的定义可知,左子树的所有值均小于根节点,右子树的所有值均大于根节点,而这个特点正好和二叉树的中序遍历中--左子树->根节点->右子树不谋而合,所以对二叉排序树进行中序遍历得到的正好是一个有序的

三、源码实现(C语言代码

#include <stdio.h>
#include <stdlib.h>
//二叉排序树

typedef struct BSTNode
{
	int data;
	BSTNode *lchild;  //左孩子
	BSTNode *rchild;  //右孩子
}BSTNode, *BSTree;

bool Search(BSTree bst, int key, BSTree f, BSTree *p);

void InOderTraverse(BSTree bst)   //中序递归遍历二叉树
{
	if (NULL != bst)
	{
		InOderTraverse(bst->lchild);
		printf("%d ", bst->data);
		InOderTraverse(bst->rchild);
	}
}

static BSTNode* BuyNode(int data)   //生成一个节点并进行初始化
{
	BSTNode *pTmp = (BSTNode*)malloc(sizeof(BSTNode));
	if (NULL == pTmp)
	{
		exit(0);
	}
	pTmp->data = data;
	pTmp->lchild = NULL;
	pTmp->rchild = NULL;
	return pTmp;
}

bool Insert(BSTree *bst, int key)
{
	if (NULL == *bst)  //空树
	{
		*bst = BuyNode(key);   //插入根节点
		return true;
	}
	BSTNode *p;
	//先在二叉排序树中查找要插入的值是否已经存在
	if (!Search(*bst, key, NULL, &p))  //如果查找失败,则插入;此时p指向遍历的最后一个节点
	{
		BSTNode *pNew = BuyNode(key);
		if (key < p->data)  //将s作为p的左孩子
		{
			p->lchild = pNew;
		}
		else if (key > p->data)  //将s作为p的右孩子
		{
			p->rchild = pNew;
		}
		return true;  //插入成功
	}
	else
	{
		printf("\nThe node(%d) already exists.\n", key);
	}
	return false;
}

/*
删除分三种情况:
(1)被删除的节点无孩子,说明该节点是叶子节点,直接删
(2)被删除的节点只有左孩子或者右孩子,直接删,并将其左孩子或者右孩子放在被删节点的位置
(3)被删除的节点既有右孩子又有右孩子
*/

BSTNode* Findparent(BSTree bst, BSTNode *child)
{
	if (NULL == bst)
	{
		return NULL;
	}

	if (bst->lchild == child || bst->rchild == child)
	{
		return bst;
	}
	else if(NULL != bst->lchild)
	{
		FindParent(bst->lchild, child);
	}
	else if (NULL != bst->rchild)
	{
		FindParent(bst->rchild, child);
	}
}

void Delete(BSTree *bst, int key)
{
	if (NULL == *bst)
	{
		exit(1);  //空树直接报错
	}
	BSTNode *p;
	BSTNode *f = NULL;
	BSTNode *q, *s;
	if (Search(*bst, key, NULL, &p)) //确实存在值为key的节点,则p指向该节点
	{

		if (NULL == p->lchild && NULL != p->rchild)  //无左孩子,有右孩子
		{
			q = p->rchild;
			p->data = q->data;    //因为两个节点之间本质的不同在于数据域的不同,而与放在哪个地址没有关系
			p->rchild = q->rchild;
			p->lchild = q->lchild;
			free(q);
		}
		else if (NULL == p->rchild && NULL != p->lchild)  //无右孩子,有左孩子
		{
			q = p->lchild;
			p->data = q->data;
			p->rchild = q->rchild;
			p->lchild = q->lchild;
			free(q);
		}
		else if (NULL != p->rchild && NULL != p->lchild) //既有左孩子,又有右孩子
		{
			q = p;
			s = p->lchild;   //找左孩子的最右孩子
			while (s->rchild)
			{
				q = s;
				s = s->rchild;
			}
			p->data = s->data;

			if (q != p)
			{
				q->rchild = p->lchild;
			}
			else
			{
				q->lchild = s->lchild;
			}
			free(s);
		}
		else
		{
			if (*bst == p)   //只有一个根节点
			{
				free(*bst);
				*bst = NULL;
				return;
			}

			BSTNode* parent = FindParent(*bst, p);
			if (parent->lchild == p)
			{
				parent->lchild = NULL;
			}
			else
			{
				parent->rchild = NULL;
			}
			free(p);
		}
	}
}

bool Search(BSTree bst, int key, BSTree f, BSTree *p)  //查找成功时,p指向值为key的节点。如果查找失败,则p指向遍历的最后一个节点
{
	if (!bst)
	{
		*p = f;
		return false;
	}
	if (bst->data == key)  //查找成功,直接返回
	{
		*p = bst;
		return true;
	}
	else if (bst->data < key)
	{
		return Search(bst->rchild, key, bst, p);
	}
	return Search(bst->lchild, key, bst, p);
}

int main(void)
{
	BSTNode *root = NULL;
	Insert(&root, 45);
	Insert(&root, 24);
	Insert(&root, 53);
	Insert(&root, 12);
	Insert(&root, 90);
	InOderTraverse(root);
	printf("\n%d ", Insert(&root, 45));   //输出0表示插入失败,输出1表示插入成功
	printf("%d\n", Insert(&root, 4));
	InOderTraverse(root);
	printf("\n");
	Delete(&root, 4);      //删除节点45
	Delete(&root, 45);      //删除节点45
	Delete(&root, 24);      //删除节点45
	Delete(&root, 53);      //删除节点45
	Delete(&root, 12);      //删除节点45
	Delete(&root, 90);      //删除节点45
	InOderTraverse(root);
	return 0;
}

运行结果:

文章最后发布于: 2018-05-21 23:35:10

相关阅读

快速学习COSMIC方法之十一:如何识别输入?

在COSMIC方法中,功能处理可拆分为四种数据移动:输入,输出,读,写。数据移动是最小的、不可再拆分的、软件内部的动作。在数据移动中包含

C语言:lseek函数-----改变文件偏移量

1.文件偏移 通常调用read或write每读写一个文件,就会改变文件的读写位置。在linux中同样可以使用lseek函数来修改文件偏移量,即读

VITAL: Visual Tracking via Adversarial Learning 阅

本文概览 本文是一篇很不错的关于目标跟踪算法的文章,收录于CVPR2018。 论文链接:https://arxiv.org/pdf/1804.04273.pdf 本文主要

CableModem原理

Cable Modem的一些参数321物理层 下行通道的频率范围为88~860MHz,每个通道的带宽为6MHz(NTSC 6 G-MHz,PAL 8MHz),采用64QAM或2

数据结构与算法(一)---重点复习知识

吐槽 国庆假期第二天,去实验室开门,给猫猫铲丑丑,然后给她换猫粮,换水,喂这货吃的emmmmmm,然后今天就把之前在极客时间上买的数据结构与

分享到:

栏目导航

推荐阅读

热门阅读