精华内容
下载资源
问答
  • 一、搜索树的复杂度分析 本文考察二叉搜索树和索引二叉... 虽然在最坏情况下的查找、插入、删除操作,散列表和二叉搜索树的时间性能相同,但是散列表在最好的情况下具有超级性能Θ(1) 不过,对于一个指定的关键...

    一、搜索树的复杂度分析

    • 本文考察二叉搜索树和索引二叉搜索树
    • 二叉搜索树,又名二叉排序树,又名二叉查找树
    • 二叉搜索树的渐进性能可以和跳表媲美:
      • 查找、插入、删除操作所需的平均时间为Θ(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
    展开全文
  • 验证二叉搜索树 题目:给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树...

    leetcode–98.验证二叉搜索树

    题目:给定一个二叉树,判断其是否是一个有效的二叉搜索树。

    假设一个二叉搜索树具有如下特征:

    • 节点的左子树只包含小于当前节点的数。
    • 节点的右子树只包含大于当前节点的数。
    • 所有左子树和右子树自身必须也是二叉搜索树。

    leetcode链接

    代码:

    public boolean isValidBST(TreeNode root) {
        return func(root,null,null);
    }
    public boolean func(TreeNode root, Integer lower,Integer upper){
        if(root ==null )return true;
        int val=root.val;
        if(lower !=null && val<=lower) return false;
        if(upper!=null && val>=upper) return false;
    
        if(!func(root.right,val,upper)) return false;
        if(!func(root.left,lower,val)) return false;
        return true;
    }
    

    leetcode–45.删除二叉搜索树中的节点

    题目:给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

    一般来说,删除节点可分为两个步骤:

    • 首先找到需要删除的节点;
    • 如果找到了,删除它。

    思路:

    1. 如果 key > root.val,说明要删除的节点在右子树,root.right = deleteNode(root.right, key)。
    2. 如果 key < root.val,说明要删除的节点在左子树,root.left = deleteNode(root.left, key)。
    3. 如果 key == root.val,则该节点就是我们要删除的节点,则:
      • 如果该节点是叶子节点,则直接删除它:root = null。
      • 如果该节点不是叶子节点且有右节点,找到该节点右子树中最小的节点(最左下角的节点)
      • 如果该节点不是叶子节点且只有左节点,找到该节点左子树中最大的节点(最右下角的节点)
    4. 返回 root

    代码:

    public int letf(TreeNode root){
        root=root.left;
        while (root.right!=null){
            root=root.right;
        }
        return root.val;
    }
    public int right(TreeNode root){
        root=root.right;
        while (root.left!=null){
            root=root.left;
        }
        return root.val;
    }
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null)
            return null;
        if(key>root.val){
            root.right=deleteNode(root.right,key);
        }else if(key< root.val){
            root.left=deleteNode(root.left,key);
        }else {
            if(root.left==null && root.right==null) root=null;
            else if(root.right!=null){
                root.val=right(root);
                root.right=deleteNode(root.right,root.val);
            }else {
                root.val=letf(root);
                root.left=deleteNode(root.left,root.val);
            }
        }
        return root;
    }
    

    leetcode–701.二叉搜索树中的插入操作

    题目:给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
    leetcode链接
    思路:

    • 若 root == null,则返回 TreeNode(val)。
    • 若 val > root.val,插入到右子树。
    • 若 val < root.val,插入到左子树。
    • 返回 root。

    代码:

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null) return new TreeNode(val);
        if(val>root.val){
            root.right=insertIntoBST(root.right,val);
        }else {
            root.left=insertIntoBST(root.left,val);
        }
        return root;
    }
    
    展开全文
  • 文章目录问题:删除二叉搜索树中的节点解题思路C++代码 问题:删除二叉搜索树中的节点 问题链接 解题思路 通过二叉搜索树的性质对待删除节点进行定位,设待删除节点为x则有一下两种情况 情况一:x有两个孩子 情况...

    问题:删除二叉搜索树中的节点

    问题链接
    在这里插入图片描述
    在这里插入图片描述

    解题思路

    通过二叉搜索树的性质对待删除节点进行定位,设待删除节点为x则有一下两种情况

    • 情况一:x有两个孩子
    • 情况二:x至多只有一个孩子
      当x有两个孩子时我们要用x的前驱节点或者x的后继节点替代x,将其值赋给x,然后删除x的前驱或者后继节点,此时就是情况二,对于情况二,如果x没孩子,直接将x删除,如果x有一个孩子,则将x的那个孩子链接到x的父节点上即可。

    C++代码

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            if(!root) return NULL;
            TreeNode *parent = NULL, *x = root;//parent记录x的父节点,x表示待删除的点
            while(x && x->val != key){//找到待删除的点
                parent = x;//更新x的父节点
                if(x->val < key)//在x的右子树中
                    x = x->right;
                else//在x的左子树中
                    x = x->left;
            }
            if(!x) return root;//没找到,返回根节点
    
    //x是要被删除的点,如果x只有至多一个孩子则可以删除,否则需要用x的前驱或者后继节点替代它,即将x的前驱节点的值赋给x即可
    //x的前驱节点:x的左子树中的最大节点
    //x的后继节点:x的右子树中的最小节点  
    //此次我们用x的前驱节点
            
            TreeNode *y = x;//y表示真正要被删除的节点,初始为x
            if(x->left && x->right){//如果x有两个孩子,则用x的前驱节点替代x
                parent = y;
                y = x->left;
                while(y->right){
                    parent = y;
                    y = y->right;
                }
            }
            //此时y是待删除的节点且之多只有一个孩子
    
            if(!y->left && !y->right){ //情况一:y没有孩子,直接将y删掉
                if(parent){//删除y之前要将parent对应的指针设为NULL
                    if(y->val < parent->val)
                        parent->left = NULL;
                    else
                        parent->right = NULL;
                }
                if(!parent) root = NULL;//如果parent为NULL,说明删除的是root,令root为NULL
            }
            else{ //情况二:y有一个孩子
                TreeNode *child;
                if(y->left) child = y->left;
                if(y->right) child = y->right;
                if(parent){//确定child是parent的哪个孩子
                    if(parent->val < child->val)
                        parent->right = child;//child是parent的右孩子
                    else 
                        parent->left = child;//child是parent的左孩子
                }
                if(!parent) root = child;//parent为NULL,说明删除的是root,那么child成为新的根节点
            }
            if(y != x) x->val = y->val;//如果x和y不是同一个节点,则y是x的前驱节点,将y的值赋给x
            delete y;//释放y所占的空间
            return root;//返回根节点
        }
    };
    
    展开全文
  • 2、map.set特性需要先铺垫二叉搜索树二叉搜索树也是树形结构 3、对二叉搜索树有了了解,可以更好的了解map set的特性 4、二叉树部分面试题较难,前边讲的解题方法不容易理解,所以学习map set 二叉搜索树对解题有...

    为什么会有二叉树进阶

    1、二叉树在数据讲过了,但是又把二叉树提出来,是因为给二叉树又加了新的规则
    2、map.set特性需要先铺垫二叉搜索树,二叉搜索树也是树形结构
    3、对二叉搜索树有了了解,可以更好的了解map set的特性
    4、二叉树部分面试题较难,前边讲的解题方法不容易理解,所以学习map set 二叉搜索树对解题有帮助

    二叉搜索树

    在这里插入图片描述

    1、当然,在实际中也可以是左边大右边小,也是二叉搜索树。
    2、如果是一个完全二叉树或者满二叉树,符合二叉搜索树的性质,那么它的查找复杂度就是一个log(n)

    二叉搜索树操作

    1、二叉搜索树的查找

    在这里插入图片描述

    //查找
       Node* find(const T& val)
       {
         int count = 0;//可以记录找到这个数总共查找了几次
         if(_root == nullptr)
         {
            return _root;
         }
         //根不为空,从根开始找,由于需要向下移动,所以定义一个cur
         Node* cur = _root;
         while(cur)
         {
            count++:
            if(cur->_data == val)
            {
               cout<<"count:"<<count<<endl;
               return cur;
            }
            else if(cur->_data > val)
            {
               cur = cur->left;
            }
            else
            {  
                cur = cur->right;
            }
         }
         //没有找到
          cout<<"count:"<<count<<endl;
          return nullptr;
         }
         
        
    

    2、二叉搜索树的插入

    在这里插入图片描述
    1、二叉搜索树的插入只能插入到叶子结点
    2、插入分为 找位置,然后插入
    3、并且二叉搜索树不会放重复的数据
    4、中序遍历是一个有序序列
    5、二叉树插入的时候应该插入的是val值,然后用val构造结点,然后进行插入

    //插入就是成功与否
    bool Insert(const T& val)
    {
       //根为空
       if(_root == nullptr)
       {
          _root = new Node(val);
          return true;
       }
       //不为空,则进行查找插入,
       //有查找,则需要cur
       Node* cur = _root;
       //因为要进行插入,所以要记录一下该点插入的上一个结点,也就是父节点parent
       Node* parent = nullptr;
       while(cur)
       {
          parent = cur;
          if(cur->_data == val)
          {return false;}
          else if(cur->_data > val)
          {
            cur = cur->_left;
          }
          else
          {
            cur = cur->_right;
          }
       }
       //将val值定义成Node,创建新节点,因为cur为空了,所以可以用来创建新节点
       cur = new Node(val);
       if(parent ->_data > val)
       {
          parent->_left = cur;
       }
       else
          parent->_right = cur;
       return true;
    }
    
    

    1、二叉树的插入其实就是在构造一颗二叉搜索树

    3、二叉搜索树的删除

    在这里插入图片描述
    上图将abcd四种情况 结合三种情况,可以写条件是
    1、左为空–处理右孩子情况
    2、右为空–处理左孩子情况
    3、左右都不为空
    将左右孩子都为空放在1 或者2都可以处理 看徐婧航的代码 比较好
    在这里插入图片描述
    在这里插入图片描述
    上图是当删除结点的时候,该结点有左右孩子的情况。删除左子树的最右结点的四种情况。

    1、因为插入和删除 都是要先进行查找,在进行插入和删除的操作的
    2、插入 查找的是一个合适的叶子结点位置,记录parent结点,根据val与父节点大小对比进行插入
    3、删除 查找的是当前要删除的结点,记录parent结点,然后处理被删除结点 父亲与孩子之间的关系。
    4、因为插入删除之间的查找 需要parent的更新,为了后续的操作,所以不能复用查找的代码
    5、插入删除更新parent什么时候更新,要根据实际情况而定,parent插入可以在while下之后更新,但是删除必须在判断了之后传递的时候更新parent,防止parnet与cur指向相同位置,插入是可以让cur和parent指向相同的位置
    6、删除的时候,一定要注意如果删除的是根节点,是没有parent的,需要_root直接接收被删除结点的左右孩子

    //要进行删除 首先是先找到该结点,由于要进行删除操作,所以需要将parent记录下来
    bool erase(const T& val)//找到值相同 直接delete结点就可以了
    {
       if(_root == nullptr)
       {
         return false;
       }
       //先查找,定义一个cur,还进行删除操作,在定义一个parent
       Node* parent = nullptr;
       Node* cur = _root;
       //因为上边的查找的代码没有parent的更新,所以查找的代码不能够进行复用
     //需要重新写查找代码
       while(cur)
       {
          parent = cur;//parnet更新不能写在这,因为每次一这样,parent与cur指向相同的位置,则无法删除操作
          if(cur->_data == val)
          {
            break;
          }
          else if(cur->_data > val)
          {
             parent = cur;
             cur = cur->_left;
          }
          else
          {
             parent = cur;
             cur = cur->_right;
          }
       }
       //没有找到结点
       if(cur == nullptr)
       {
         return false;
       }
       //1、非叶子结点
            //a、左右孩子都有
            //b、有左孩子
            //c、有右孩子
       if(cur ->_left && cur->_right)//a、左右孩子都有
       {
        //该结点的左子树的最大值也就是向右找  或者  找该节点右子树的最小值也就是向左找 
        //我的方法是将cur位置保存了一下,然后用cur去找左子树的最右结点,用cur替换tmp,删除cur就可以了
        //老师的方法是重新定义一个mostRight结点,让cur待在删除的结点位置,然后mostRight去找,最后替换mostRight 和cur,删除mostRight 
         /* Node* tmp = cur;
          parent = nullptr;
          cur = cur->_left;
          while(cur->_right)
          {
             parent = cur;
             cur = cur ->_right;
          }
          tmp->_data = cur->_data;
          parent->_right = cur->_left;
          delete cur;*/ //我的想法  
          Node* mostRight = cur->_left;
          parent = cur;
          while(mostRight->_right)
          {
             parent = mostRight;
             mostRight = mostRight->_right;
          }
          cur->_data = mostRight->_data;
          //删除最右结点,如果mostRight在parent的左边,或者mostRight在parent的右边,都是有可能的,因为是去左子树找最右结点的。
          if(parent->_left == mostRight)
          {
            parent->_left = mostRight->_left;
          }
          else
            parent->_right = mostRight->_left;
          delete mostRight;
       }
       else if(cur->_left)//b、有左孩子
       {
          if(cur != _root)
          {
             if(parent->_left == cur)
             parent->_left = cur->_left;
             else
             parent ->_right = cur->_left;
          }
          else  
          {
             _root = cur->_left;
          }
          delete cur;
       }
       else if(cur->_right)//c、有右孩子
       {
          if(cur != _root)
          {
             if(parent->_left == cur)
             parent->_left = cur->_right;
             else
             parent ->_right = cur->_right;
          }
          else
          {
            _root = cur->_right;
          }
          delete cur;
       }
       2、叶子结点
       else
       {  
          if(cur != _root)
          {
            if(parent->_left == cur)
            parent->_left = nullptr;
            else
            parent ->_right = nullptr;
          }
          //根结点
          else
            _root = nullptr;
          delete cur;
       }
    return true;
    }
    

    二叉搜索树的实现

    //二叉搜索树首先要有一个结点,结点有数值 左右指针,所以reeee7e体
    //由于结点里边的数据可以多种类型,所以泛型
    template<class T>
    struct BSTNode
    {
      T _data;
      BSTNode<T>* _left;
      BSTNode<T>* _right;
      //构造一个结点
      BSTNode(const T& val = T())
      :_data(val)
      ,_left(nullptr)
      ,_right(nullptr)
      {}
    }
    
    //二叉搜索树 我们需要构建一棵树,然后对其进行操作
    //实现左子树小于根,右子树大于根
    template<class T>
    class BSTree
    {
    public:
       //给树的结点取一个别名
       typedef BSTNode<T> Node;
       
       //1、查找在上边
       //2、插入在上边
       //3、删除在上边
       //为了验证一下这个二叉搜索树的中序遍历是一个递增序列,写一个中序遍历
    //4、中序遍历就是一个动作,没有返回值
    void inorder()//这里是因为中序遍历的时候要访问_root,但是_root是私有的,所以需要外一个接口,内也应该有一个接口。
    {
      _inorder(_root);
      cout<<endl;
    }
    void _inorder(Node* root)//遍历应该是结点 不是BSTree
    {
      if(root == nullptr)
      {
        return;
      }
      _inorder(root->_left);
      cout<<root->_data<<" ";
      _inorder(root->_right);
    }
    //8、构造函数
    BSTree()
    :_root(nullptr)
    {}
    //5、析构
    //用递归进行析构二叉搜索树,先析构左子树再是右子树,然后根节点,由于析构从外界传值,又要访问_root。所以定义一个内接口
    void destory(Node* root)
    {
       destory(root->_left);
       destory(root->_right);
       delete root;
    }
    ~BSTree()//析构函数不传参,但是要递归析构,可以考虑重写一个destory函数,进行递归析构
    {
      destory(_root);  
      _root = nullptr;
    }
    //6、二叉树的拷贝构造---拷贝构造肯定要创建结点
    Node* copyTree(Node* root)
    {
        if(root)
        {
              Node* node = new Node(root->_data);
              node->left = copyTree(root->_left);
              node->_right = copyTree(root->_right);
              return node;
        }
        return nullptr;
    }
    BSTree(const BSTree<T>& bst)//
    {
    //因为在copyTree已经创建好树并且连接起来了,所以呢 最后只返回_root结点就可以了
         _root = copyTree(bst._root);
    }
    //7 二叉树的赋值运算
    BSTree<T>& operator=(const BSTree<T>& bst)
    {
          if(this != &bst)
          {
               destory(_root);
               _root = copyTree(bst._root);
          } 
          return *this;
    }
    //现代写法
    BSTree<T>& operator=(const BSTree<T> bst)//这里要进行交换,如果传&的话,会让原来的bst树发生变化的,所以赋值传值。
    {
        swap(_root,bst._root);
        return *this;
    }
    
    private:
      //给树定义一个_root的结点
      //再给一个缺省值,这样的话在构造_root的时候就不用调用结点的构造函数。
      Node* _root  = nullptr;
    }
    
    
    //插入随机数,然后中序遍历,在查找那个数字 
     void test
         {
           srand(time(nullptr));//让数更加随机
           int num;
           cout<<"i请输入一个num"<<endl;
           cin>> num;
           BSTree<int> b;
           for(int i = 0;i < num;i++)
           {
              b.insert(rand());
           }
           b.inorder();//将随机数打印出来
           cout<<"请输入一个查找的数字"<<endl;
           cin >> num;
           b.find(num);
         }
    
    void test
    {
      BSTree<int> b;
      b.insert(10);
      b.insert(5);
      b.insert(15);
      b.insert(3);
      b.insert(0);
      b.insert(2);
      b.insert(13);
      b.insert(17);
      b.inorder();
      b.inorder();
      b.erase(3);
      b.inorder();
      b.erase(10);
      b.inorder();
    }
    
    void test()
    {
      BSTree<int> b;
      b.insert(10);
      b.insert(5);
      b.insert(15);
      b.insert(3);
      b.insert(0);
      b.insert(2);
      b.insert(13);
      b.insert(17);
      b.inorder();
      BSTree<int> copy(b);
      copy.inorder();
      BSTree<int> b2;
      b2 = b;
      b2.inorder();
    }
    

    1、二叉树的拷贝构造不好理解,代码也不太好想,看图
    在这里插入图片描述
    2、二叉搜索树的拷贝构造和析构一样,都是递归拷贝构造 递归析构的,所以都能重新写个函数实现递归的要求。
    3、析构函数与构造函数必须成对出现。所以在上边方程写了析构函数,也就必须再写一个构造函数。

    二叉搜索树的应用

    1、K模型

    在这里插入图片描述
    1、二叉搜索树就是一个K的模型

    2、KV模型

    在这里插入图片描述
    2、对于KV模型,是需要改变二叉搜索的内部一些东西的

    template<class K,class V>
    struct BSTNode
    {
    //数据的位置
      k _key;
      //数据
      v _data;
      BSTNode<K,V>* _left;
      BSTNode<K,V>* _right;
      //构造一个结点
      BSTNode(const K& key,const V& val)
      :_key(key)
      ,_data(val)
      ,_left(nullptr)
      ,_right(nullptr)
      {}
    }
    
    //二叉搜索树 我们需要构建一棵树,然后对其进行操作
    //实现左子树小于根,右子树大于根
    template<class K,class V>
    class BSTree
    {
    public:
       //给树的结点取一个别名
       typedef BSTNode<K,V> Node;
       
       //1、查找
        Node* find(const K& key)
       {
         int count = 0;//可以记录找到这个数总共查找了几次
         if(_root == nullptr)
         {
            return _root;
         }
         //根不为空,从根开始找,由于需要向下移动,所以定义一个cur
         Node* cur = _root;
         while(cur)
         {
            count++:
            if(cur->_key == key)
            {
               cout<<"count:"<<count<<endl;
               return cur;
            }
            else if(cur->_key > key)
            {
               cur = cur->left;
            }
            else
            {  
                cur = cur->right;
            }
         }
         //没有找到
          cout<<"count:"<<count<<endl;
          return nullptr;
         }
       //2、插入
       bool Insert(const K& key,const V& data)
    {
       //根为空
       if(_root == nullptr)
       {
          _root = new Node(key,data);
          return true;
       }
       //不为空,则进行查找插入,
       //有查找,则需要cur
       Node* cur = _root;
       //因为要进行插入,所以要记录一下该点插入的上一个结点,也就是父节点parent
       Node* parent = nullptr;
       while(cur)
       {
          parent = cur;
          if(cur->_key == key)
          {return false;}
          else if(cur->_key > key)
          {
            cur = cur->_left;
          }
          else
          {
            cur = cur->_right;
          }
       }
       //将val值定义成Node,创建新节点,因为cur为空了,所以可以用来创建新节点
       cur = new Node(key,data);
       if(parent ->_key > key)
       {
          parent->_left = cur;
       }
       else
          parent->_right = cur;
       return true;
    }
    
       //3、删除
       bool erase(const K& key)//找到值相同 直接delete结点就可以了
    {
       if(_root == nullptr)
       {
         return false;
       }
       //先查找,定义一个cur,还进行删除操作,在定义一个parent
       Node* parent = nullptr;
       Node* cur = _root;
       //因为上边的查找的代码没有parent的更新,所以查找的代码不能够进行复用
     //需要重新写查找代码
       while(cur)
       {
          parent = cur;//parnet更新不能写在这,因为每次一这样,parent与cur指向相同的位置,则无法删除操作
          if(cur->_key == key)
          {
            break;
          }
          else if(cur->_key > key)
          {
             parent = cur;
             cur = cur->_left;
          }
          else
          {
             parent = cur;
             cur = cur->_right;
          }
       }
       //没有找到结点
       if(cur == nullptr)
       {
         return false;
       }
       //1、非叶子结点
            //a、左右孩子都有
            //b、有左孩子
            //c、有右孩子
       if(cur ->_left && cur->_right)//a、左右孩子都有
       {
        //该结点的左子树的最大值也就是向右找  或者  找该节点右子树的最小值也就是向左找 
        //我的方法是将cur位置保存了一下,然后用cur去找左子树的最右结点,用cur替换tmp,删除cur就可以了
        //老师的方法是重新定义一个mostRight结点,让cur待在删除的结点位置,然后mostRight去找,最后替换mostRight 和cur,删除mostRight 
         /* Node* tmp = cur;
          parent = nullptr;
          cur = cur->_left;
          while(cur->_right)
          {
             parent = cur;
             cur = cur ->_right;
          }
          tmp->_data = cur->_data;
          parent->_right = cur->_left;
          delete cur;*/ //我的想法  
          Node* mostRight = cur->_left;
          parent = cur;
          while(mostRight->_right)
          {
             parent = mostRight;
             mostRight = mostRight->_right;
          }
          cur->_key = mostRight->_key;***~~//这块替换结点应该也要,老师还没有发现~~ ***
          cur->_data = mostRight->_data;
          //删除最右结点,如果mostRight在parent的左边,或者mostRight在parent的右边,都是有可能的,因为是去左子树找最右结点的。
          if(parent->_left == mostRight)
          {
            parent->_left = mostRight->_left;
          }
          else
            parent->_right = mostRight->_left;
          delete mostRight;
       }
       else if(cur->_left)//b、有左孩子
       {
          if(cur != _root)
          {
             if(parent->_left == cur)
             parent->_left = cur->_left;
             else
             parent ->_right = cur->_left;
          }
          else  
          {
             _root = cur->_left;
          }
          delete cur;
       }
       else if(cur->_right)//c、有右孩子
       {
          if(cur != _root)
          {
             if(parent->_left == cur)
             parent->_left = cur->_right;
             else
             parent ->_right = cur->_right;
          }
          else
          {
            _root = cur->_right;
          }
          delete cur;
       }
       2、叶子结点
       else
       {  
          if(cur != _root)
          {
            if(parent->_left == cur)
            parent->_left = nullptr;
            else
            parent ->_right = nullptr;
          }
          //根结点
          else
            _root = nullptr;
          delete cur;
       }
    return true;
    }
       //为了验证一下这个二叉搜索树的中序遍历是一个递增序列,写一个中序遍历
    //4、中序遍历就是一个动作,没有返回值
    void inorder()//这里是因为中序遍历的时候要访问_root,但是_root是私有的,所以需要外一个接口,内也应该有一个接口。
    {
      _inorder(_root);
      cout<<endl;
    }
    void _inorder(Node* root)//遍历应该是结点 不是BSTree
    {
      if(root == nullptr)
      {
        return;
      }
      _inorder(root->_left);
      cout<<root->_key<<" "<<root->_data<<" ";
      _inorder(root->_right);
    }
    //8、构造函数
    BSTree()
    :_root(nullptr)
    {}
    //5、析构
    //用递归进行析构二叉搜索树,先析构左子树再是右子树,然后根节点,由于析构从外界传值,又要访问_root。所以定义一个内接口
    void destory(Node* root)
    {
       destory(root->_left);
       destory(root->_right);
       delete root;
    }
    ~BSTree()//析构函数不传参,但是要递归析构,可以考虑重写一个destory函数,进行递归析构
    {
      destory(_root);  
      _root = nullptr;
    }
    //6、二叉树的拷贝构造---拷贝构造肯定要创建结点
    Node* copyTree(Node* root)
    {
        if(root)
        {
              Node* node = new Node(root->_key,root->_data);
              node->left = copyTree(root->_left);
              node->_right = copyTree(root->_right);
              return node;
        }
        return nullptr;
    }
    BSTree(const BSTree<K,V>& bst)//
    {
    //因为在copyTree已经创建好树并且连接起来了,所以呢 最后只返回_root结点就可以了
         _root = copyTree(bst._root);
    }
    //7 二叉树的赋值运算
    BSTree<K,V>& operator=(const BSTree<K,V>& bst)
    {
          if(this != &bst)
          {
               destory(_root);
               _root = copyTree(bst._root);
          } 
          return *this;
    }
    //现代写法
    BSTree<T>& operator=(const BSTree<T> bst)//这里要进行交换,如果传&的话,会让原来的bst树发生变化的,所以赋值传值。
    {
        swap(_root,bst._root);
        return *this;
    }
    
    
    private:
      //给树定义一个_root的结点
      //再给一个缺省值,这样的话在构造_root的时候就不用调用结点的构造函数。
      Node* _root  = nullptr;
    }
    
    void test()
    {
      BSTree<int,int> b;
      b.insert(10,10);
      b.insert(5,5);
      b.insert(15,15);
      b.insert(3,3);
      b.insert(0.0);
      b.insert(2.2);
      b.insert(13.13);
      b.insert(17,13);//key不能相同,只能data可以相同
       b.insert(17,17);//这个插入不进去,key不能相同
      b.inorder();
      
      BSTree<intint> copy(b);
      copy.inorder();
      BSTree<int,int> b2;
      b2 = b;
      b2.inorder();
    }
    

    二叉搜索树的性能分析

    在这里插入图片描述
    如何将单支树 进行改进 **不论按照什么次序进行插入,都可以是二叉搜索树呢?**下节课看
    使用了旋转 深度一致相同的方式?应该是在红黑树那一块有解决方法。
    在这里插入图片描述

    展开全文
  • 在5.2中完成了树的遍历,这一节中将对如何从二叉搜索树删除最大元素和最小元素做介绍:我们要想删除二分搜索树的最小值和最大值,就需要先找到二分搜索树的最小值和最大值,其实也还是很容易的,因为根据二叉...
  • 二叉搜索树的和

    2019-09-30 00:38:10
    二叉搜索树的和 #题目描述 二叉搜索树是一种特殊的二叉树(每个节点最多只有两个儿子的树)。 树的每个节点上存有一个唯一的,并且满足:这个节点的左子树内所有点的都比这个节点的小,且右子树内所有点...
  • 二叉搜索树的概念 二叉搜索树,或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的均小于它的根结点的; 若它的右子树不空,则右子树上所有结点的均大于它的根结点的...
  • 你可以在网上找到关于二叉搜索树非常好的文章,我们不会提供二叉搜索树的完整实现,但为了维持一致性,我们而是会举例表明一个简单的二叉搜索树...相比之下,建立一个节点具有多个顺序索引(key)的平衡二叉搜索树...
  • 二叉搜索树简介与使用二叉搜索树实现有序映射
  • 链式二叉搜索树和静态数组二叉搜索树删除一个上的效率比较
  • 二叉搜索树

    2019-03-16 20:48:53
    二叉搜索树 1. 二叉搜索树的概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下...2.二叉搜索树的创建,插入,查找,删除 2.1 创建 二叉搜索树的创建,等同于二叉树的创建过程,区别是,在插入的...
  • 文章目录二叉搜索树/二叉排序树/二叉查找树.1 定义.2 性质二叉搜索树创建二叉搜索树查找.1 查找步骤.2 查找性能分析二叉树插入与删除 二叉搜索树/二叉排序树/二叉查找树 .1 定义 二叉排序树(Binary Sort Tree)...
  • 我们首先介绍一下什么是二叉搜索树和二叉平衡树: 二叉搜索树:一棵二叉树,可以为空;如果不为空,满足以下性质1. 非空左子树的所有键值小于其根结点的键值。2. 非空右子树的所有键值大于其根结点的键值。3. 左、...
  • 一、什么是二叉搜索树 二叉搜索树(Binary Search Tree)又称二叉排序树,它或者是一棵空树,或者是具有以下性质的...二、二叉搜索树的实现(查找、插入、删除) 代码如下: #include<iostream> using namespac
  • 给定一个二叉搜索树的根节点 root 和一个 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 示例: 问题分析 二叉搜索树的特点是左子树的...
  • 1,二叉搜索树定义? (1)每个节点有一个唯一的key,且所有结点互不相同; (2)左子树所有key小于根的key; (3)右子树所有key大于根的key; (4)左右子树都是二叉搜索树。 这就是一棵二叉...
  • 二叉搜索树 特点 操作 1. 二叉搜索树 二叉搜索树又称二叉排序树/二叉查找树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的都小于根节点的。 若它的右子树不为空...
  • BST :二叉搜索树 BST 前序遍历的非递归写法 BST 的广度优先遍历 BST 中的最小值 BST 中的最大值 删除BST 中的最小值 删除BST中的最大值 删除BST中的任意元素(利用5、6) BST的前序遍历非递归写法,利用栈的性质...
  • 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的都小于根节点的 若它的右子树不为空,则右子树上所有节点的都大于根节点的 它的左右...
  • BST树又被称为二叉排序树,二叉搜索树二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 每个结点都有一个作为搜索依据的关键码(key),所有结点的关键码互不相同。(即BST树中所有元素的不允许重复...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,009
精华内容 8,403
关键字:

删除二叉搜索树的最大值