二叉搜索树 订阅
二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。 [1] 展开全文
二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。 [1]
信息
概    述
一种经典的数据结构
特    点
链表的快速插入与删除操作,数组快速查找
分    类
二叉树
中文名
二叉搜索树
学    科
计算机
外文名
Binary Search Tree
二叉搜索树原理
二叉搜索树(BST)又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的,可以使用一个链表数据结构来表示,其中每一个结点就是一个对象。一般地,除了key和卫星数据之外,每个结点还包含属性lchild、rchild和parent,分别指向结点的左孩子、右孩子和双亲(父结点)。如果某个孩子结点或父结点不存在,则相应属性的值为空(NIL)。根结点是树中唯一父指针为NIL的结点,而叶子结点的孩子结点指针也为NIL。 [2] 
收起全文
精华内容
下载资源
问答
  • Python实现二叉搜索树的删除功能 二叉搜索树(二叉查找树,Binary Search Tree)又称为排序二叉树、有序二叉树。 二叉搜索树的实现可以参考:https://blog.csdn.net/weixin_43790276/article/details/105753543 本文...
  • 本文实例讲述了C语言判定一棵二叉树是否为二叉搜索树的方法。分享给大家供大家参考,具体如下: 问题 给定一棵二叉树,判定该二叉树是否是二叉搜索树(Binary Search Tree)? 解法1:暴力搜索 首先说明一下二叉树和...
  • 本文实例讲述了Python二叉搜索树与双向链表转换算法。分享给大家供大家参考,具体如下: 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的...
  • 剑指Offer(Python多种思路实现):二叉搜索树的后序遍历序列 面试33题: 题:二叉搜索树的后序遍历序列 题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设...
  • 英汉词典 基于二叉搜索树的英汉词典
  • 使用C#实现的动态规划算法 关键字序列:0.15,0.1,0.05,0.1,0.2 非关键字序列:0.05,0.1,0.05,0.05,0.05,0.1 以上的测试数据,输入数据可以得到结果
  • 二叉搜索树C++代码

    2016-07-30 19:33:48
    本文主要讨论二叉搜索树的基本性质以及基本操作,并用C++代码实现,每个成员操作以成员函数的形式出现,并附有适当的说明。 包括: 普通二叉树的遍历(先序,中序,后序,分层),二叉搜索树的建立,插值,删值,求...
  • 难度:中等 一、题目描述: 二、解题分析: class Solution: def __init__(self): ... # 二叉搜索树的中序遍历是递增的,因此把标准中序遍历中 改变每个父节点的左右指向即可 # head, pre, tail = None,None,None #
  • 0020 算法笔记动态规划最优二叉搜索树问题 1问题描速 设 S={x 1, x2, ,xn} 是一个有序集合且 x1, x2, ,xn 表示有序集 合的二叉搜索 利用二叉 的 点存 有序集中的元素而且具有性 存 于每个 点中的元素 x 大于其左子 ...
  • 给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的...
  • 主要介绍了Java删除二叉搜索树最大元素和最小元素的方法,结合实例形式详细分析了java针对二叉搜索树的基本遍历、查找、判断、删除等相关操作技巧,需要的朋友可以参考下
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
  • 添加结点其实很容易,我们只需要找到结点所行对应的位置就可以了,而且没有要求是平衡的二叉搜索树,因此每次添加结点都是在叶子结点上操作,不需要修改二叉搜索树整体的结构
  • 使用C++类模板实现的二叉搜索树。 拥有极快的插入删除、查找能力,是折半查找的高级应用。 使用std::list双向链表实现可重复存储元素。 对于学习二叉树有很大的帮助。
  • 给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。...
  • Python实现二叉搜索树

    2020-09-21 18:29:35
    二叉搜索树(二叉排序树)它的每个节点的数据结构为1个父节点指针,1个左孩子指针,1个有孩子指针,还有就是自己的数据部分了,因为只有左右两孩子,所以才叫二叉树,在此基础上,该二叉树还满足另外一个条件:每个结点的左...
  • 本文实例讲述了Python实现查找二叉搜索树第k大的节点功能。分享给大家供大家参考,具体如下: 题目描述 给定一个二叉搜索树,找出其中第k大的节点 就是一个中序遍历的过程,不需要额外的数组,便利到节点之后,k减...
  • 本文实例讲述了Python二叉搜索树与双向链表实现方法。分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点,...
  • 二叉搜索树实例练习

    2020-09-05 17:25:34
    一棵二叉查找是按二叉树结构来组织的。这样的可以用链表结构表示,其中每一个结点都是一个对象
  • 剑指Offer(Python多种思路实现):二叉搜索树的第K大节点 面试54题: 题目:二叉搜索树的第K大节点 题:给定一颗二叉搜索树,请找出其中的第k小的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个...
  • 本文考察二叉搜索树和索引二叉搜索树 二叉搜索树的渐进性能可以和跳表媲美: 查找、插入、删除操作所需的平均时间为Θ(logn) 查找、插入、删除操作的最坏情况的时间为Θ(n) 元素按升序输出时所需时间为Θ(n) ...
    
    

    一、搜索树的复杂度分析

    • 本文考察二叉搜索树和索引二叉搜索树
    • 二叉搜索树,又名二叉排序树,又名二叉查找树
    • 二叉搜索树的渐进性能可以和跳表媲美:
      • 查找、插入、删除操作所需的平均时间为Θ(logn)
      • 查找、插入、删除操作的最坏情况的时间为Θ(n)
      • 元素按升序输出时所需时间为Θ(n)
      • 虽然在最坏情况下的查找、插入、删除操作,散列表和二叉搜索树的时间性能相同,但是散列表在最好的情况下具有超级性能Θ(1)
      • 不过,对于一个指定的关键字,使用二叉搜索树,你可以在Θ(n)时间内,找到最接近它的关键字。例如,给定关键字是k,你可以在Θ(n)时间内,找到最接近k的关键字(即小于等于k的最大关键字,或大于等于k的最小关键字)。而对于散列表来说,这种操作的时间是Θ(n+D)(其中D是散列表除数);对跳表来说,这种操作的时间是Θ(logn) 
    • 索引二叉搜索树:
      • 使用索引二叉搜索树,你可以按关键字和按名次进行字典操作,例如读取关键字从小打到排名第10的元素,删除关键字从小打到第100的元素。按名次的操作和按关键字的操作,其时间性能一样
      • 索引二叉树可以用来表示线性表;其中的元素具有名次(即索引),没有关键字。在这种线性表的表示中,get、erase、insert操作的时间性能为O(logn),但是前面实现的线性表,这些操作的时间为Θ(n)(不过get操作在用数组实现时,其性能是Θ(1))
    • 总结,对于二叉搜索树和跳表来说,在最坏和最好情况下的渐近时间复杂性是相同的。但是,我们可以对二叉搜索树加以平衡限制,使上述的每一个操作耗时都是Θ(logn)

    二、搜索树的高效性

    • 在一篇文章中我们引入了抽象数据类型dictionary:https://blog.csdn.net/qq_41453285/article/details/103449056
    • 在另一篇文章中(https://blog.csdn.net/qq_41453285/article/details/103533372https://blog.csdn.net/qq_41453285/article/details/103534526)我们有散列表来描述字典,字典操作(查找、插入、删除)所需要的平均时间为Θ(1)。而这些操作在最坏情况下的时间与字典的元素个数n呈线性关系
    • 如果给dictionaty增加以下操作,那么散列不再具有较好的平均性能:
      • 1.按关键字的升序输出字典元素
      • 2.按升序找到第k个元素
      • 3.删除第k个元素
    • 如果使用平衡搜索树,那么对字典的基本操作(查找、插入、删除)能够在O(logn)的时间内完成,上述1操作能在Θ(n)时间内完成。使用索引平衡搜索树,我们也能在O(logn)的时间内完成上述操作2和3

    三、二叉搜索树

    • 概述:二叉搜索树是一棵二叉树,可能为空
    • 一棵非空的二叉搜索树满足以下特征:
      • 1.每个元素都有一个关键字,并且任意两个元素的关键字都不同;因此,所有的关键字都是唯一的(其实也可以不唯一,见下)
      • 2.在根节点的左子树中,元素的关键字(如果有的话)都小于根节点的关键字
      • 3.在根节点的右子树中,元素的关键字(如果有的话)都大于根节点的关键字
      • 4.根节点的左、右子树也都是二叉搜索树
    • 例如下面图a)不是二叉搜索树,图b)和c)都是二叉搜索树

    • 如果关键字不唯一,那么这样的二叉树称为“有重复值的二叉搜索树”

    二叉搜索树的查找

    • 二叉搜索树的查找步骤如下:
      • 1.从根开始,如果根节点为空,就停止搜索;如果不为空,进行第2步
      • 2.将要查找的元素与根节点进行比较,如果比根节点值小,就向左孩子查找;如果比根节点值大,就向右孩子查找
      • 3.重复2步骤,只要比某个节点值小就向左孩子查找;只要比某个节点值大,就向右孩子查找
      • 4.查找到之后返回查找的节点,如果没查找就返回空

    二叉搜索树的插入

    • 二叉搜索树的插入步骤如下:
      • 1.从根开始,如果根节点为空,就将新节点作为根节点;如果不为空进行第二步
      • 2.将要插入的节点与根节点相比较,遇键值较大者就向左,遇键值较小者就向右
      • 3.如果遇到节点的值与插入节点的值相同就退出停止插入(或做其他处理)
      • 4.一直到尾端,即为插入点
    • 例如:

    二叉搜索树的删除

    • 删除节点p,要考虑3种情况:
      • 1.p是树叶
      • 2.p只有一棵非空子树
      • 3.p有两颗非空子树
    • ①如果删除的是树叶:
      • 1.如果删除的节点是叶节点:就释放该叶节点。例如,下面删除图a中的节点35,直接将其父节点40的左孩子域置为NULL即可,结果如图b所示
      • 2.如果删除的节点是根节点(说明树总共只有一个节点):直接令根为NULL

    • ②如果删除的节点只有一棵非空子树:
      • 1.如果删除的节点是根节点:就另其唯一的子节点作为新的根节点
      • 2.如果删除的节点不是根节点:直接将其子节点连至其父节点即可。例如下图想要删除节点5,直接将其子节点2作为父节点30的子节点即可

    • ②如果删除的节点有两棵非空子树:
      • 那么就将删除的节点替换为它的左子树中的最大元素或者替换为它的右子树中的最小元素
        • 查找左子树的最大元素:先指向于左子树,然后一直向左子树的右子树进行查找,直到右孩子指针为NULL为止
        • 查找右子树的最小元素:先指向于右子树,然后一直向右子树的左子树进行查找,直到左孩子指针为NULL为止
      • 例如下面我们想删除图a中关键字为40的节点,既可以用右子树中的最小元素60来代替(如下图b所示),也可以用其左子树中的最大元素35来代替(如下图c所示)

    四、索引二叉搜索树

    • 概述:源于普通的二叉搜索树,只是在每个节点中添加一个leftSize域。这个域的值是该节点左子树的元素个数
    • 下图是两棵索引二叉搜索树。节点内部的数字是元素的关键字,节点外的数组是leftSize的值

    leftSize域索引的作用:

    • leftSize同时给出了一个元素的索引(该元素的左子树的元素排在该元素之前)
    • 例如在上图中:
      • 元素按顺序分别为:12、15、18、20、25、30。按照线性表的形式(e0、e1、...e4)
      • 根的索引时3,它等于根元素的leftSize域的值
      • 在根为25的子树中,元素按顺序排列为25/30,根元素25的索引时0,而leftSize的值也是0

    索引二叉搜索树的查找

    • 带有索引的搜索方法与搜索偶对(一个偶对被定义为关键字域key和值域value)的方法是类似的
    • 假设我们要查找索引为2的元素:
      • 跟的leftSize域的值是3,因此,我们要查找的元素在根的左子树中(进一步说,我们要查找的元素在左子树的索引为2)
      • 因为左子树的根(即15)的leftSize域的值为1,所以我们要查找的元素在15的右子树中
      • 然而,在15的右子树中,待查元素的索引不再是2,因为15的右子树元素都排在15的左子树元素和15之后
      • 为了确定待查元素在15的右子树中的索引,我们要用2减去leftSize+1(其中leftSize是15的leftSize值(1)),结果为2-(1+1)
      • 15的右子树的根是18,它的leftSize域的值是0,因此待查元素便是18
    • 所需时间为O(h),其中h是索引搜索树的高

    索引二叉搜索树的插入

    • 把一个元素插入索引二叉搜索树中,使用的过程类似于下面我们实现的二叉搜索树的find()函数(见下面代码)
    • 不过要在根至新插入节点的路径上修改leftSize域的值
    • 所需时间为O(h),其中h是索引搜索树的高

    索引二叉搜索树的删除

    • 通过索引实施删除的过程是:
      • 首先按索引进行搜索,确定要删除的元素的位置
      • 然后按照上面介绍的二叉搜索树的删除操作进行删除
      • 接下来,如果需要,在从根节点到删除节点的路径上更新leftSize域
    • 所需时间为O(h),其中h是索引搜索树的高

    五、搜索树的抽象数据类型(ADT)

    二叉搜索树的抽象数据模型

    索引二叉搜索树的抽象数据类型

    • 支持所有二叉搜索树的方法,另外索引二叉搜索树还支持按名次进行查找和删除操作

    六、搜索树的抽象类

    二叉搜索树的抽象类

    template<class K,class E>
    class bsTree:public dictionary<K,E>
    {
    public:
        //按关键字升序输出
        virtual void ascend()=0;
    };

    索引二叉搜索树

    • 索引二叉搜索树具有二叉搜索树的全部方法(所以继承于bsTree就好),并且另外还支持按名次进行查找和删除操作
    template<class K,class E>
    class indexedBSTree:public bsTree<K,E>
    {
    public:
        //根据给定的索引,返回其数对的指针
        virtual pair<const K,E>* get(int)const=0;
    
        //根据给定的索引,删除其数对
        virtual void delete(int)=0;
    };

    七、二叉搜索树的编码实现

    • 下面我们来实现二叉搜索树,其中每个节点都是一个字典(pair数据类型)
    • 我们在前面文章(https://blog.csdn.net/qq_41453285/article/details/103638694)介绍二叉树时,并用linkedBinaryTree类实现了二叉树的链表形式,现在我们的二叉搜索树类binarySearchTree从linkedBinaryTree直接继承而来,然后将元素节点类型改为pair<K,E>即可(K为关键字类型,E为关键字所对应的元素的数据类型)

    头文件定义

    #include <iostream>
    #include <utility>
    #include <queue>
    
    using std::cin;
    using std::cout;
    using std::endl;
    using std::pair;
    using std::queue;

    字典类定义

    template<typename K,typename E>
    class dictionary
    {
    public:
    	virtual ~dictionary() = default;
    
    	virtual bool empty()const = 0; //判断字典是否为空
    	virtual int size()const = 0;   //返回字典中数对的数目
    	virtual std::pair<K, E> *find(const K& theKey)const = 0; //返回匹配数对的指针
    	virtual void erase(const K& theKeys) = 0; //删除匹配的数对
    	virtual void insert(const std::pair<K, E>& theElement) = 0;//向字典中插入一个新的数对
    };

    二叉搜索树抽象类定义

    • 二叉搜索树用来实现字典,所以从字典继承而来
    template<typename K,typename E>
    class bsTree :public dictionary<K, E>
    {
    public:
    	virtual void ascend()= 0;//按关键字升序输出搜索二叉树
    };

    二叉搜索树实现(binarySearchTree)

    按关键字升序输出二叉树(ascend)

    • 按关键字升序输出搜索二叉树,又由于binarySearchTree继承于linkedBinaryTree,所以直接调用linkedBinaryTree中的后续打印函数inOrderOutput()即可
    template<typename K,typename E>
    class binarySearchTree :public bsTree<K, E>, 
    			public linkedBinaryTree<std::pair<const K,E>>
    {
    public:
    	//按关键字升序输出搜索二叉树(直接调用linkedBinaryTree中的中序遍历打印函数即可)
    	virtual void ascend() override {
    		inOrderOutput();
    	}
    };

    linkedBinaryTree中的__output函数需要改动一下

    • 因为现在节点的数据类型为pair了,所以打印时不能直接打印pair数据类型,而是pair.first
    static void __output(binaryTreeNode<T>* theNode) { std::cout << theNode->element.second << " "; }

    判断是否为空(empty())、返回大小(size())

    • empty():判断树是否为空
    • size():判断树的大小
    template<typename K,typename E>
    class binarySearchTree :public bsTree<K, E>, 
                            public linkedBinaryTree<std::pair<K,E>>
    {
    public:
    	virtual bool empty()const override{ //判断树是否为空
    		return (this->treeSize == 0);
    	}
    	virtual int size()const override {  //返回树的大小
    		return this->treeSize;
    	}
    };

    查找节点函数(find)

    • 根据上面二叉搜索树的查找规则,根据关键字进行查找
    /*根据关键字查找指定的节点,方法在上面有过介绍
    	如果关键字大于某节点,就向右子树中找;如果关键字小于某节点,就向左子树中找
    */
    template<typename K,typename E>
    std::pair<const K, E> *binarySearchTree<K,E>::find(const K& theKey)const
    {
    	binaryTreeNode<std::pair<const K, E>> *tempNode = this->root;
    	while (tempNode != NULL) 
    	{
    		if (theKey > tempNode->element.first)
    			tempNode = tempNode->rightChild;
    		else if (theKey < tempNode->element.first)
    			tempNode = tempNode->leftChild;
    		else
    			return &tempNode->element;
    	}
    	return NULL;
    }

    插入节点函数(insert)

    •  根据上面二叉搜索树的插入规则,先遍历到搜索树的最后一个节点,然后进行插入
    template<typename K, typename E>
    void binarySearchTree<K, E>::insert(const std::pair<K, E>& theElement)
    {
    	binaryTreeNode<std::pair<const K, E>> *tempNode = this->root,
    									*insertNode = NULL;
    
    	//遍历循环一直到树的叶子节点处即为插入点(或者找到一个有相同关键字的节点,更换值之后退出)
    	while (tempNode != NULL)
    	{
    		insertNode = tempNode;
    		
    		if (tempNode->element.first > theElement.first)
    			tempNode = tempNode->leftChild;
    		else if (tempNode->element.first < theElement.first)
    			tempNode = tempNode->rightChild;
    		else {
    			tempNode->element.second = theElement.second;
    			return;
    		}
    	}
    
    	//新建立一个节点
    	binaryTreeNode<std::pair<const K, E>> *newNode =
    					new binaryTreeNode<std::pair<const K, E>>(theElement);
    	//如果根节点不为空
    	if (this->root != NULL) {
    		if (insertNode->element.first > newNode->element.first)
    			insertNode->leftChild = newNode;
    		else
    			insertNode->rightChild = newNode;
    	}
    	else//如果根节点为空,作为根节点
    		this->root = newNode;
    
    	this->treeSize++;
    }

    节点的删除函数(erase)

    • 通过上面的删除规则,我们定义了如下函数,在函数中,如果要删除的节点有两颗非空子树,我们统一用左子树中的最大元素来进行替换
    • 因为元素的数据类型为paie<const K,E>,这种删除操作时复杂的,而且改变关键字也是可能的,所以该算法的复杂性为O(h)
    template<typename K, typename E>
    void binarySearchTree<K, E>::erase(const K& theKey)
    {
    	binaryTreeNode<std::pair<const K, E>> *eraseNode = this->root,
    									*beforeEraseNode = NULL;
    
    	//如果没遍历到默认,或者已经找到要删除的节点了(终止循环)
    	while (eraseNode != NULL&&eraseNode->element.first != theKey)
    	{
    		beforeEraseNode = eraseNode;
    		if (eraseNode->element.first>theKey)
    			eraseNode = eraseNode->leftChild;
    		else
    			eraseNode = eraseNode->rightChild;
    	}
    
    	//如果while循环完之后没有找到该节点,直接退出
    	if (eraseNode == NULL)
    		return;
    
    	//如果要删除的节点,左右子树都不为空(就将左子树中最大的节点移到删除节点处)
    	if ((eraseNode->leftChild != NULL) && (eraseNode->rightChild != NULL))
    	{
    		binaryTreeNode<std::pair<const K, E>> *p = eraseNode->leftChild,
    												*pp = eraseNode;
    		//一直遍历到左子树中的最右边的节点(即为左子树中的最大节点)
    		while (p->rightChild != NULL)
    		{
    			pp = p;
    			p = p->rightChild;
    		}
    		
    		//然后将p移动到eraseNode处,并删除eraseNode
    		/*先创建一个指新节点,其值为要删除的节点左子树中最大节点的值,
    		  但是左右子树指针为要删除的节点的左右子树指针,待会就用这个节点去填补删除节点
    		*/
    		binaryTreeNode<std::pair<const K, E>> *q =
    			new binaryTreeNode<std::pair<const K, E>>(p->element, eraseNode->leftChild, eraseNode->rightChild);
    
    		//如果删除的是根节点,直接把最大节点q赋值给根节点即可
    		if (beforeEraseNode == NULL)
    			this->root = q;
    		//如果删除的节点是其父节点的左子树,就其替换的节点作为其原父节点的左子树
    		else if (eraseNode == beforeEraseNode->leftChild)
    			beforeEraseNode->leftChild = q;
    		//同上,如果删除的节点使其父节点的右子树
    		else
    			beforeEraseNode->rightChild = q;
    
    		if (pp == eraseNode)
    			beforeEraseNode = q;
    		else
    			beforeEraseNode = pp;
    
    		//删除这个要删除的节点,然后将p赋值给它
    		delete eraseNode;
    		eraseNode = p;
    	}
    }

    主函数

    int main()
    {
    	binarySearchTree<int, char> y;
    	y.insert(pair<int, char>(1, 'a'));
    	y.insert(pair<int, char>(6, 'c'));
    	y.insert(pair<int, char>(4, 'b'));
    	y.insert(pair<int, char>(8, 'd'));
    	cout << "Tree size is " << y.size() << endl;
    	cout << "Elements in ascending order are" << endl;
    	y.ascend();
    
    	cout << endl << endl;
    	pair<const int, char> *s = y.find(4);
    	cout << "Search for 4 succeeds " << endl;
    	cout << s->first << ' ' << s->second << endl;
    	y.erase(4);
    	cout << "4 deleted " << endl;
    	cout << "Tree size is " << y.size() << endl;
    	cout << "Elements in ascending order are" << endl;
    	y.ascend();
    
    	cout << endl << endl;
    	s = y.find(8);
    	cout << "Search for 8 succeeds " << endl;
    	cout << s->first << ' ' << s->second << endl;
    	y.erase(8);
    	cout << "8 deleted " << endl;
    	cout << "Tree size is " << y.size() << endl;
    	cout << "Elements in ascending order are" << endl;
    	y.ascend();
    
    	cout << endl << endl;
    	s = y.find(6);
    	cout << "Search for 6 succeeds " << endl;
    	cout << s->first << ' ' << s->second << endl;
    	y.erase(6);
    	cout << "6 deleted " << endl;
    	cout << "Tree size is " << y.size() << endl;
    	cout << "Elements in ascending order are" << endl;
    	y.ascend();
    
    	cout << endl << endl;
    	s = y.find(1);
    	cout << "Search for 1 succeeds " << endl;
    	cout << s->first << ' ' << s->second << endl;
    	y.erase(1);
    	cout << "1 deleted " << endl;
    	cout << "Tree size is " << y.size() << endl;
    	cout << "Elements in ascending order are" << endl;
    	y.ascend();
    
    	return 0;
    }

    八、带有相同关键字元素的二叉搜索树

    • 如果二叉搜索树可以带有相同的关键字,只需要把上面程序中的insert函数的while循环中的语句的else if中的<改为<=即可
    while (tempNode != NULL)
    {
        insertNode = tempNode;
    		
        if (tempNode->element.first > theElement.first)
            tempNode = tempNode->leftChild;
        else if (tempNode->element.first <= theElement.first)
            tempNode = tempNode->rightChild;
        else {
            tempNode->element.second = theElement.second;
            return;
        }
    }

    九、索引二叉搜索树编码实现

    • 如果用编码实现索引二叉搜索树(indexedBinartSearchTree),一个节点的数值域是三元的:leftSize、key、value
    展开全文
  • 查看测试用例二叉搜索树项目 该项目包含一个框架,供您实现二叉搜索树。 这是一个测试驱动的项目。 运行测试并读取最上面的错误。 如果不清楚什么失败了,请打开test/test.js文件以找出测试预期的内容。 使最上面的...
  • 二叉搜索树

    2017-01-18 16:59:54
    在clion中,二叉搜索树的完全实现。可以拷贝.c和.h文件,移植到其它ide中去执行。
  • 二叉搜索树的结构如下: // Binary Search Tree type BST struct { // Data interface{} 替换为interface可以支持多种数据类型 Val int Left *BST Right *BST } 实现如下操作: 查找(递归/非递归) 删除 插入 ...
  • c代码-查找二叉搜索树的最大和最小元素
  • 在这里,我使用 Python Tkinter 制作了二叉搜索树可视化工具 :light_bulb: 我在这里提供的功能----> :right_arrow: 1.二叉搜索树中的插入 :right_arrow: 2.二叉搜索树中的删除 :right_arrow: 3. 二叉搜索树...
  • c语言实现二叉搜索树

    2014-03-23 21:06:15
    1.实现二叉搜索树的基本操作 2.包括建立,查找,删除,显示 3.得到最长路径和最短路径,并能分别计算长度

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 99,761
精华内容 39,904
关键字:

二叉搜索树