二叉树之二叉查找(搜索)树的查找、插入、删除及遍历(C++实现)

2023-10-18 18:06| 来源: 网络整理| 查看: 265

目录一、认识二叉树查找(搜寻或搜索)树二、二叉查找树的查找算法三、二叉查找树的插入算法四、二叉查找树的删除算法五、二叉查找树的遍历六、二叉查找树的性能优化

一、认识二叉树查找(搜寻或搜索)树

二叉查找树1（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若任意结点的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；任意结点的左、右子树也分别为二叉查找树；

一颗简单的二叉搜索树：

6 4 1 5 10 7 11

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

时间复杂度:

算法平均最坏查找(搜索) O(log n) O(n) 插入 O(log n) O(n) 删除 O(log n) O(n)

空间复杂度：平均O(n), 最坏O(n)

二、二叉查找树的查找算法

在二叉搜索树中查找X的过程为：

查找从根结点开始，若二叉搜索树为空，则返回空，否则将根结点的数据域值与X进行比较，并进行相应的处理：若X等于根结点的数据域值，搜索完成，返回该结点；若X小于根结点的数据域值，则只需在其左子树继续搜索；若X大于根结点的数据域值，则只需在其右子树继续搜索；重复上述过程

查找效率取决于树的高度

定义树结点：

//头文件 #include #incldue

【本文地址】

公司简介

联系我们