精华内容
下载资源
问答
  • 完全二叉搜索树结构的C++实现

    千次阅读 2016-06-07 14:27:56
    本文想要建立一种数据结构,能够综合二叉搜索树和完全二叉树的特点。首先考虑采用那种存储方式:数组和链表。二叉搜索树多采用链式存储,而完全二叉树多采用的数组存储方式,因为它的数组元素都被利用起来,不存

    二叉搜索树是一种二叉树,且树的所有节点满足其左子树的所有节点小于该节点,其右子树的所有节点大于该节点。若二叉树的深度为H,当前H-1层二叉树的是满二叉树且第H层的所有节点集中在左边,则称该树为完全二叉树。本文想要建立一种数据结构,能够综合二叉搜索树和完全二叉树的特点。首先考虑采用那种存储方式:数组和链表。二叉搜索树多采用链式存储,而完全二叉树多采用的数组存储方式,因为它的数组元素都被利用起来,不存在浪费的问题。当给定一个已排序序列,本文需要通过遍历的方式将序列中的数依次插入进去,需要利用节点总个数和根节点左右子树节点个数的关系,综合考虑采用数组更容易实现。

    采用递归的思想,先确定根节点左子树节点总个数,对应的从已排序序列中选出对应的元素放入根节点,将根节点两侧的两个序列分别按照以上方法继续进行,算法描述如下:

    void solve( int ALeft, int ARight, int TRoot )
    { /* 初始调用为solve(0, N-1, 0) */
    n = ARight – ALeft + 1;
    if (n==0) return;
    L = GetLeftLength(n); /* 计算出n个结点的树其左子树有多少个结点*/
    T[TRoot] = A[ALeft + L];
    LeftTRoot = TRoot * 2 + 1;
    RightTRoot = LeftTRoot + 1;
    solve(ALeft, ALeft+L-1, LeftTRoot);
    solve(ALeft+L+1, ARight, RightTRoot);
    }
    如何计算根节点左子树的节点个数?需要利用完全二叉树的特性,对于一个具有N个节点的完全二叉树,其深度为H,L表示根节点左子树所有节点的个数。

    具体实现的源代码如下所示:

    void CreateCompleteBinarySearchTree(int* a,int length)
    {
    	for(int i=0;i<length;i++)
    		std::cout<<a[i]<<" ";
    	std::cout<<std::endl;
    	std::sort(a,a+length);
    	for(i=0;i<length;i++)
    		std::cout<<a[i]<<" ";
    	InsertTreeNode(a,1,10,1);
    	std::cout<<std::endl<<"Print the tree:"<<std::endl;
    	ComBinSearTree.Print();
    }
    void InsertTreeNode(int *a,int Aleft,int Aright,int Troot)
    {
    	if(Aleft>Aright)
    		return;
    	int temp=GetLeftLength(Aright-Aleft+1);//获得该根节点左子树的节点个数
    	*ComBinSearTree[Troot]=a[Aleft+temp-1];
    	InsertTreeNode(a,Aleft,Aleft+temp-1,Troot*2);
    	InsertTreeNode(a,Aleft+temp+1,Aright,Troot*2+1);	
    }
    int GetLeftLength(int temp)
    {
    	if(temp==1)
    		return 0;
    	int N=temp;
    	int H=(int)(log(N+1)/log(2));
    	int Up=(int)pow(2,H-1)-1;
    	int Down=(N+1-(int)pow(2,H))>(int)pow(2,H-1)?(int)pow(2,H-1):(N+1-(int)pow(2,H));
    	return Up+Down;	
    }


    展开全文
  • 给定 1~n 共 n个 数字,建立一个二叉搜索树,则 n 个节点的有根树的所有结构,都有一个二叉搜索树与之结构相同。 这里用数学归纳法证明: n = 1,没有问题。 n = k,k 个节点的有根树的所有结构,都有一个二叉...

    https://leetcode.com/problems/unique-binary-search-trees/description/

    给定 1~n 共 n个 数字,建立一个二叉搜索树,则 n 个节点的有根树的所有结构,都有一个二叉搜索树与之结构相同。

    这里用数学归纳法证明:

    1. n = 1,没有问题。
    2. n = k,k 个节点的有根树的所有结构,都有一个二叉搜索树与其相同。
      那么,我们只需要证明,对所有这样 k 个节点的树,任何叶子节点都可以在左边或者右边插入一个子节点后,都存在一颗 k + 1 个节点的二叉搜索树,结构与其相同。
      注意到插入的限制条件:当往一个叶子节点添加左子节点,那么节点只需要满足其小于其父节点parent,大于其父节点的父节点grandparent。如果这个 k 个节点的二叉搜索树 grandparent < ·parent -1,显然我们插入是合法的。否则,我们将所有应该大于 grandparent 的节点值加 1 ,这样,我们的插入就变得可能了。

    这也证明了二叉搜索树如果不去平衡它,各种各样的情况都是可能出现的。

    展开全文
  • 本文考察二叉搜索树和索引二叉搜索树 二叉搜索树的渐进性能可以和跳表媲美: 查找、插入、删除操作所需的平均时间为Θ(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
    展开全文
  • 文章目录二叉搜索树/二叉排序树/二叉查找树.1 定义.2 性质二叉搜索树创建二叉搜索树查找.1 查找步骤.2 查找性能分析二叉树插入与删除 二叉搜索树/二叉排序树/二叉查找树 .1 定义 二叉排序树(Binary Sort Tree)...

    概述


    本文介绍数据结构–二叉搜索树

    1. 二叉搜索树基本概念


    1.1 定义

    二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。。设x为二叉查找树中的一个节点,x节点包含关键字key,节点x的key值记为key[x]。如果y是x的左子树中的一个节点,则key[y] <= key[x];如果y是x的右子树的一个节点,则key[y] >= key[x]。

    1.2 性质

    二叉搜索树,可以是一棵空树,或者是具有下列性质的二叉树:

    1. 若左子树不空,则左子树上所有节点的值均小于它的根节点的值;
    2. 若右子树不空,则右子树上所有节点的值均大于它的根节点的值;
    3. 左、右子树也分别为二叉排序树;
    4. 没有键值相等的节点。

    2. 二叉搜索树相关操作

    2.1 二叉搜索树创建

    参考- 数据结构与算法——平衡二叉树
    现有序列:A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。根据此序列构造二叉搜索树过程如下:
      (1)i = 0,A[0] = 61,节点61作为根节点;
      (2)i = 1,A[1] = 87,87 > 61,且节点61右孩子为空,故81为61节点的右孩子;
      (3)i = 2,A[2] = 59,59 < 61,且节点61左孩子为空,故59为61节点的左孩子;
      (4)i = 3,A[3] = 47,47 < 59,且节点59左孩子为空,故47为59节点的左孩子;
      (5)i = 4,A[4] = 35,35 < 47,且节点47左孩子为空,故35为47节点的左孩子;
      (6)i = 5,A[5] = 73,73 < 87,且节点87左孩子为空,故73为87节点的左孩子;
      (7)i = 6,A[6] = 51,47 < 51,且节点47右孩子为空,故51为47节点的右孩子;
      (8)i = 7,A[7] = 98,98 < 87,且节点87右孩子为空,故98为87节点的右孩子;
      (9)i = 8,A[8] = 93,93 < 98,且节点98左孩子为空,故93为98节点的左孩子;
     创建完毕后如图2.4中的二叉搜索树:
      在这里插入图片描述

    2.2 二叉搜索树查找

    2.2.1 查找步骤
    1. 如果树是空的,则查找不成功。
    2. 若根结点的关键字值等于查找的关键字,成功。
    3. 否则:
      2.1 若小于根结点的关键字值,递归查左子树。若子树为空,查找不成功。
      2.2 若大于根结点的关键字值,递归查右子树。若子树为空,查找不成功。
    2.2.2 查找性能分析

    每个结点的C(i)C(i)为该结点的层次数。

    • 最坏情况下,当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树,树的深度为其平均查找长度(n+1)/2^{(n+1)}/_2(和顺序查找相同)
    • 最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log2(n)log_2(n)成正比。

    查找算法代码:其实与二叉树递归遍历算法的思想是非常相似的。

        /* 递归查找二叉排序树T中是否存在key, */
        /* 指针f指向T的双亲,其初始调用值为NULL */
        /* 若查找成功,则指针p指向该数据元素节点,并返回TRUE */
        /* 否则指针p指向查找路径上访问的最后一个节点并返回FALSE */
    
        bool searchBST(BSTNode* T, int key, BSTNode* f, BSTNode **p)
        {  
            if (!T) /*  查找不成功 */
            { 
                *p = f;  
                return false; 
            }
            else if (key == T->key) /*  查找成功 */
            { 
                *p = T;  
                return true; 
            } 
            else if (key < T->key) 
                return searchBST(T->lchild, key, T, p);  /*  在左子树中继续查找 */
            else  
                return searchBST(T->rchild, key, T, p);  /*  在右子树中继续查找 */
        }
    

    使用二叉搜索树可以提高查找效率,其平均时间复杂度为O(log2n)O(log_2n)

    2.3 二叉搜索树插入

    插入过程:

    1. 先检测该元素是否在树中已经存在。如果已经存在,则不进行插入;
    2. 若元素不存在,则进行查找过程,并将元素插入在查找结束的位置
      在这里插入图片描述
      在这里插入图片描述

    插入代码算法

        void insertBST(BSTNode **T,int key) //此处使用二重指针是因为要修改指针的指针
        {
            BSTNode *s;
            if(*T==NULL) //到达查找结束位置,再次位置插入元素
            {
                s = (BSTNode*)malloc(sizeof(BSTNode));
                s->key = key;
                s->lchild = NULL;
                s->rchild = NULL;
                *T=s;
            }
            else if(key<(*T)->key)//要插入的值大于当前节点,往左子树搜
                insertBST(&((*T)->lchild),key);
            else if(key>(*T)->key)//大于当前节点,往右子树搜
                insertBST(&((*T)->rchild),key);
        }
    

    2.4 二叉搜索树的删除

    在删除之前,首先需要找到此节点,针对不同的结点类型,进行删除不同的操作.

    情况
    删除方式
    删除的节点为叶子节点 删除叶子节点的方式最为简单,只需查找到该节点,直接删除即可。
    删除的节点只有左子树 删除的节点若只有左子树,将节点的左子树替代该节点位置。
    删除的节点只有右子树 删除的节点若只有右子树,将节点的右子树替代该节点位置。
    删除的节点既有左子树又有右子树 其流程如下:
      (1)遍历待删除节点的左子树,找到其左子树中的最大key节点(最右下),即删除节点的前驱节点;
      (2)将最大节点代替被删除节点;
      (3)删除左子树中的最大节点;
      (4)左子树中待删除最大节点一定为叶子节点或者仅有左子树。按照之前情形删除即可。

    对于左右子树都有的结点,可以采用中序遍历的方式来得到删除结点的前驱和后继结点。选取前驱结点或者后继结点代替删除结点即可。
    在这里插入图片描述
    例如要删除上图的47结点,删除后:
    在这里插入图片描述

    删除算法代码:

    	// BSTNode* T是,我们通过前面的查找算法找到的结点,它不一定就是要删除的结点。
    	// 因此,我盟在删除之前需要通过key是否相等,来判断,返回的结点,是不是要删除的结点。
    	
        //若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素节点
        //并返回TRUE;否则返回FALSE。
        bool deleteBST(BSTNode* T,int key)
        { 
            if(!*T) /* 不存在关键字等于key的数据元素 */ 
                return false;
            else
            {
                if (key == (*T)->key) /* 找到关键字等于key的数据元素 */ 
                    return deleteBSTNode(T);
                else if (key<(*T)->key)
                    return deleteBST(&(*T)->lchild,key);
                else
                    return deleteBST(&(*T)->rchild,key);
    
            }
        }
        /* 从二叉排序树中删除节点p,并重接它的左或右子树。 */
        bool deleteBSTNode(BSTNode* p)
        {
            BSTNode* q,s;
            if((*p)->rchild==NULL) //右子树空则只需重接它的左子树(待删节点是叶子也走此分支) 
            {
                q=*p;
                *p=(*p)->lchild; 
                free(q);
            }
            else if((*p)->lchild==NULL) //左子树为空,只需重接它的右子树
            {
                q=*p; 
                *p=(*p)->rchild; 
                free(q);
            }
            else //左右子树均不空
            {
                q=*p; 
                s=(*p)->lchild;
                while(s->rchild) // 转到左子树,然后向右到尽头(找待删节点的前驱) */
                {
                    q=s;
                    s=s->rchild;
                }
                (*p)->key=s->key; //s指向被删节点的直接前驱(将被删节点前驱的值取代被删节点的值)
                if(q!=*p)
                    q->rchild=s->lchild; //重接q的右子树
                else
                    q->lchild=s->lchild; //重接q的左子树
                free(s);
            }
            return TRUE;
        }
    
    
    展开全文
  • 二叉搜索树的设计及代码
  • 二叉搜索树(Binary Sort Tree) 二叉搜索树,又称为二叉排序树(二叉查找树),它或许是一棵空树,或许是具有一下性质的二叉树: 1.若它的左子树不为空,则左子树上所有的节点的值小于根节点的值 2.若它的右子...
  • 文章目录二叉搜索树概念二叉搜索树操作二叉搜索树的查找 二叉搜索树 概念   二叉搜索树又叫做二叉排序树或者是一棵空树,具有以下性质: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的...
  • 7-2 二叉搜索树结构 (30 分) 二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它...
  • 给定一个二叉树,判断其是否是一个有效的二叉搜索树。 一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。...
  • 给定一个二叉搜索树,同时给定最小边界L和最大边界R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。 示例 1: 输入:...
  • 二叉搜索树结构

    2019-03-20 20:42:49
    L3-016 二叉搜索树结构 (30 分) 二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的...
  • 主要介绍了javascript数据结构二叉搜索树实现方法,较为详细的分析了二叉搜索树的概念、原理与JavaScript实现二叉搜索树的方法,对于学习JavaScript数据结构具有一定参考借鉴价值,需要的朋友可以参考下
  • 二叉排序 1、二叉排序的介绍
  • 『数据结构二叉搜索树

    千次阅读 2019-07-11 19:02:14
    什么是二叉搜索树二叉搜索树的基本操作。二叉搜索树的查找、插入、删除等。二叉搜索树的性能分析。二叉搜索树的模拟实现(C++和Java)。模拟实现中遇到的问题。
  • 二叉查找树结构和算法以及其简单实现
  • 二叉搜索树

    2019-09-16 19:59:34
    数据结构与算法——二叉搜索树的实现原理 二叉搜索树(又名二叉查找树、二叉排序树):它或者是一棵空树,或者是具有下列性质的二叉树:   若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;   若...
  • 一个高度平衡的二叉搜索树(平衡二叉搜索树)是在插入和删除任何节点之后,可以自动保持其高度最小。 也就是说,有N个节点的平衡二叉搜索树,它的高度是`logN`。并且,每个节点的两个子树的高度不会相差超过1。 根据...
  • 这两种问题有点相似但是是一个进阶,这里就先写第96题,然后写95题。 96 不同的二叉搜索树Ⅱ 给定一个整数 n,求以 1 … ...给定 n = 3, 一共有 5 种不同结构二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / /
  • 使用python实现二叉搜索树

    千次阅读 2019-07-01 17:48:54
    我们想要创建一个二叉搜索树结构来让所有的元数据都按正确的数据存储,同时我们希望这是一个可变的结构,所以主要有以下几点: 设计基本的二叉搜索树结构 使用MutableSet结构作为基类。 具体的介绍可参照python...
  • 给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。 例如: 输入: 二叉搜索树: 5 / \ 2 13 输出: 转换为累加树: ...
  • 接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉...
  • 本篇文章将二叉搜索树和AVL树的相关内容进行复习并以图解。
  • 二叉排序树二叉排序树二叉排序的运算 二叉排序 二叉排序是一种特殊的二叉树,它可以为空,若不空,则具有以下特性。 若左子树非空,则左子树上所有结点的关键字均小于根结点的关键字。 若右子非空,则右子...
  • 数据结构 二叉搜索树

    2011-08-06 12:58:53
    大二《数据结构》课程设计 二叉搜索树实现算法
  • 二叉查找树,又叫二叉搜索树,二叉排序树。他是一种特殊的二叉树,为提高查找效率而诞生的数据结构。 二叉查找树的特征 (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右...
  • 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表: [-10, -3, 0, ...
  • 二叉搜索树最后两层节点数量 Description 二叉搜索树 (BST) 递归定义为具有以下属性的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值 若它的右子树不空,则右子树上所有结点的值均...
  • 数据结构-二叉搜索树

    2017-11-25 21:01:19
    数据结构-二叉搜索树二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;...
  • 解释: 给定 n = 3, 一共有 5 种不同结构二叉搜索树: 要满足是二叉搜索树,以i为root, 左子树的个数为i-1(比i小的数),右子树的个数为n-i(比i大的数)。 此时如果出现个数为0,表示空树,记作1;只有一个节点,...
  • 二叉搜索树中的插入操作 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证,新值和原始二叉搜索树中的任意节点值都不同。 注意,可能存在多种...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,014
精华内容 21,605
关键字:

二叉搜索树的结构