树的四种分类.pdf

《树的四种分类.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Searchtrees：实例--二叉搜索树什么是二叉搜索树二叉搜索树(BinarySearchTree)是一棵有序的二叉树，所以我们也可以称它为二叉排序树（不知道二叉树的童鞋，先看看二叉树：传送门）。具有以下性质的二叉树我们称之为二叉搜索树：若它的左子树不为空，那么左子树上的所有值均小于它的根节点；若它的右子树不为空，那么右子树上所有值均大于它的根节点。它的左子树和右子树分别也为二叉搜索树。2、二叉搜索树的结构二叉搜索树能够高效的进行一下操作：①插入一个数值②查询是否包含某个数值③删除某个数值根据实现的不同，还可以实现其他各种操作，这是一种使用性很高的数据结构。我们来

2、看一个例子：这就是二叉搜索树的存储结构，所有的节点，都满足左子树上的比自己小，而右子树上的所有节点比自己大。二叉搜索树因为其有序性，所以它能够高效的管理数的集合(1)查询我们查找是否存在17：<1>根节点是7，因为小于17，所以去右子树查找<2>走到节点12，还是小于17，所以继续往右子树找<3>走到节点17，此时找到17。(2)插入我们使用查找的方式进行插入，以数字6为例，如图所示：(3)删除删除操作相对之前的其他两种操作，就略显复杂一些。一般来说我们可以分为三种情况：<1>需要删除的节点没有左儿子，那么就把右儿子提上去<2>需要删除的节点的左儿子没有右儿子，那么就

3、把左儿子提上去<3>不满足上述的两种情况的话，就把左子树中最大的节点放到要删除的节点上。3、二叉搜索树的复杂度无论我们执行哪一个操作，其所花的时间都和树的高度成正比。我们不难得知，二叉搜索树的平均复杂度为O(logn)。4、二叉搜索树的实现通过上述的了解，我们大致已经知道二叉搜索树的工作原理。所以现在我们就来简单的实现二叉搜索树基本的增删查的功能，代码如下：[cpp]viewplaincopy1.//表示节点的结构体2.structnode{3.intval;4.node*lch,*rch;5.};6.//插入整数x7.node*insert(node*p,intx)

4、{8.if(p==NULL){9.node*newNode=newnode;10.newNode->val=x;11.newNode->lch=newNode->rch=NULL;12.p=newNode;13.}else{14.if(xval)p->lch=insert(p->lch,x);15.elsep->rch=insert(p->rch,x);16.}17.returnp;18.}19.//查找整数x20.boolfind(node*p,intx){21.if(p==NULL)returnfalse;22.elseif(p->val==x)retur

5、ntrue;23.elseif(p->val>x)returnfind(p->lch,x);24.elsereturnfind(p->rch,x);25.}26.//删除整数x27.node*remove(node*p,intx){28.if(p==NULL)returnNULL;29.elseif(xval)p->lch=remove(p->lch,x);30.elseif(x>p->val)p->rch=remove(p->rch,x);31.//情况<1>32.elseif(p->lch==NULL){33.node*q=p->rch;34.delete

6、p;35.returnq;36.}37.//情况<2>38.elseif(p->lch->rch==NULL){39.node*q=p->lch;40.q->rch=p->rch;41.deletep;42.returnq;43.}44.//情况<3>45.else{46.node*q;47.for(q=p->lch;q->rch->rch!=NULL;q=q->rch);48.node*r=q->rch;49.q->rch=r->lch;50.r->lch=p->lch;51.r->rch=p->rch;52.deletep;53.returnr;54.}55.re

7、turnp;56.}Heaps；实例--斐波那契堆斐波纳契堆（FibonacciHeap）于1984年由MichaelL.Fredman与RobertE.Tarjan提出，1987年公开发表，名字来源于运行时分析所使用的斐波那契数。斐波那契堆同二项堆（BinomialHeap）一样，也是一种可合并堆（MergeableHeap）。与二项堆一样，斐波那契堆是由一组最小堆有序树构成，但堆中的树并不一定是二项树。与二项堆中树都是有序的不同，斐波那契堆中的树都是有根而无序的。特点：不涉及删除元素的操作有O(1)的平摊时间。Extract-Min和Delete