欢迎来到军工软件开发人才培养基地——学到牛牛

二叉查找树

时间:2024-05-06 07:01:10 来源:学到牛牛

二叉树的定义

二叉树是树形结构的一个重要类型,许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单的转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得尤为重要。二叉树的特点是每个节点最多只能有两棵子树,且有左右之分。

二叉树是有n个有限元素的集合,该集合或者为空,或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树,当集合为空时,称该二叉树为空二叉树,在二叉树中,一个元素也称为一个节点。

下图为树的示意图

图表 1

 

二叉搜索树(又称二叉排序树、二叉查找树),它或者是一颗空树,又或者是具有如下性质的二叉树:

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

2.若它的右子树不为空,则根节点小于所有的右子树结点的值;

3.它的左右子树叶分别为二叉排序树。

根据节点的值排序就是:左子树<根节点<右子树

中序遍历一颗二叉树可以得到一个结点值递增的有序序列。

如下图二叉树:

图表 2

它的中序遍历是:1、2、3、4、5、6,正好就是排好序的。

二叉搜索树是能够高效地进行如下操作的数据结构。

1.插入一个数值

2.查询是否包含某个数值

3.删除某个数值

本文章整理二叉搜索树的查找。

在二叉排序树中查找目标元素,就是从树根节点出发,先将树根节点和目标元素作比较:

若该节点不存在,则查找失败;若当前节点的值和目标值相等,则查找成功

若当前节点的值比目标值小,那么目标值只可能位于当前节点的左子树中,所以下一步继续进入左子树查找

若当前节点的值比目标值大,那么目标值只可能位于当前节点的右子树中,所以下一步继续进入右子树查找。

以图表2的二叉排序树为例,查找元素3的过程是:

从树根节点出发,4比目标值3大,则3只可能位于4的左子树中,继续进入左子树查找

当前子树根节点的值为2,2比3小,则3只可能位于2的右子树,继续进入右子树查找

当前子树根节点的值为3,和目标值相等,则查找成功​

编码实现二叉排序树中查找目标元素,代码如下:

 

 

struct tree_node *find(struct tree_node *tree, int num)

{

    if(tree == NULL) {//如果当前节点为NULL 则返回NULL

        return NULL;

    }

    if(num == tree->num) {  //如果查找成功 则返回目标值

        return tree;

    }

    if(num > tree->num) {//如果目标值大于当前节点的值,则继续在右子树查找

        return find(tree->rch, num);

    } 

    if(num < tree->num) {//如果目标值小于当前节点的值,则继续在左子树查找

        return find(tree->lch, num);

    }

}