切换导航
首页
技术问答
编程语言
前端开发
移动开发
开发工具
程序设计
行业应用
CMS系统
服务器
频道导航
▸ PHP
▸ Java
▸ Java SE
▸ Python
▸ C#
▸ C&C++
▸ Ruby
▸ VB
▸ asp.Net
▸ Go
▸ Perl
▸ netty
▸ Django
▸ Delphi
▸ Jsp
▸ .NET Core
▸ Spring
▸ Flask
▸ Springboot
▸ SpringMVC
▸ Lua
▸ Laravel
▸ Mybatis
▸ Asp
▸ Groovy
▸ ThinkPHP
▸ Yii
▸ swoole
▸ HTML
▸ HTML5
▸ JavaScript
▸ CSS
▸ jQuery
▸ Bootstrap
▸ Angularjs
▸ TypeScript
▸ Vue
▸ Dojo
▸ Json
▸ Electron
▸ Node.js
▸ extjs
▸ Express
▸ XML
▸ ES6
▸ Ajax
▸ Flash
▸ Unity
▸ React
▸ Flex
▸ Ant Design
▸ Web前端
▸ 微信小程序
▸ 微信公众号
▸ iOS
▸ Android
▸ Swift
▸ Hybrid
▸ Cocos2d-x
▸ Flutter
▸ Xcode
▸ Silverlight
▸ cocoa
▸ Cordova
前端之家
数据结构
【数据结构】树的基本内容总结
【数据结构】树的基本内容总结
2019-05-17
数据结构
前端之家
前端之家
收集整理的这篇文章主要介绍了
【数据结构】树的基本内容总结
,
前端之家
小编觉得挺不错的,现在分享给大家,也给大家做个参考。
课程正式开始了。因为有些课感觉好没意思。恰好,背着数据结构(c语言版)去上算法课,于是从那次开始看。慢慢的看的还挺有意思,于是把树这章基本看完了,做个小结。、
@H_
301
_2@
@H_
301
_2@ 因为普通的树应用价值不大而且不用以表示,所以现在只讨论二叉树。
@H_
301
_2@ 1.内存中的表示
方法
:
@H_
301
_2@ (1)数组。主要用来表示完全二叉树,这样对于寻找父节点和子节点很容易。某个节点i,它的父节点是i/2 取下整。左子节点是2i,右节点的2i+1.如果存在的话。
@H_
301
_2@ (2)链表。这个更常用一些吧。一个节点有三个域,data,leftChild,rightChild.当然了,为了便于寻找父节点方便,可以
增加
一个域,用于指向父节点的位置所在。
@H_
301
_2@
@H_
301
_2@ 2二叉树的抽象数据结构:
@H_
301
_2@ ********************************************************************************* @H_
301
_2@ structure BinaryTree; @H_
301
_2@ objects:节点的有限集合。 @H_
301
_2@ functions: @H_
301
_2@ (1)BinTree Create() //创建一个树 @H_
301
_2@ (2)Boolean IsEmpty(bt) //是否是空 @H_
301
_2@ (3)BinTree MakeBT(btleft,item,btright)//
生成
一个树,左子树为btleft,右子树为btright,item作为跟节点 @H_
301
_2@ (4)BinTree Lchild(bt) //返回左子树或者NULL @H_
301
_2@ (5)BinTree Rchild(bt)//返回右子树或者NULL @H_
301
_2@ (6)element Data(bt)//返回根节点的数据 @H_
301
_2@ ********************************************************************************* @H_
301
_2@
@H_
301
_2@ 3二叉树的若干性质。这个比较偏理论,基本不怎么用吧,先不写了 @H_
301
_2@ 4二叉树的遍历 @H_
301
_2@ 以前总是觉得这个有点难,发现也没有什么。顶多是非递归的要复杂一点,递归的很容易啊。 @H_
301
_2@ (1)中序遍历 前序遍历和后序遍历的递归版本。 @H_
301
_2@ ******************************** @H_
301
_2@ 中序遍历 @H_
301
_2@ void inorder(tree ptr) @H_
301
_2@ { @H_
301
_2@ if(ptr) @H_
301
_2@
{ @H_
301
_2@
inorder(ptr->left) @H_
301
_2@ visit(ptr->data) @H_
301
_2@
inorder(ptr->right) @H_
301
_2@
} @H_
301
_2@ } @H_
301
_2@ ******************************** @H_
301
_2@
@H_
301
_2@ (2)使用栈的迭代的中序遍历参考P129的程序。很简单。 @H_
301
_2@ (3)层次遍历。也就是说广度优先
搜索
,使用队列实现。至于是循环队列还是其他队列,可以自己考虑。
效果
是:使树中的节点按照层次依次
输出
。 @H_
301
_2@ (4)其他操作:二叉树的复制,二叉树的判断相等。 @H_
301
_2@ 复制是一个递归的实现过程。分配内存,然后左子树递归复制,右子树递归进行复制。 @H_
301
_2@ 判断是否相等主要是先检查空树条件。然后递归的判断左右子树是否分别相等。如果有任何一个地方不同,即可返回False。程序结束。 @H_
301
_2@
@H_
301
_2@ 5线索二叉树 @H_
301
_2@ 在二叉树中,叶子节点基本都是指向空的,而我们如果把这些点都弄起来,发现共有n+1个空闲的指针。那么,就可以用这些空闲的指针来进行一些使用,从而方便我们的一些操作。在中序遍历中,主要是用这些指针来指向某个节点的前驱节点和后继节点。这样的话,我们就不用递归的进行遍历了,而是可以跟据这个线索,一步一步的完成遍历。为了便于区分某个节点的左右指针是指向了自己的孩子节点还是指向了自己的前驱和后继节点,需要对数据结构中的表示
方法
进行一些更改,以便区分。新的结构如下所示: @H_
301
_2@ **************************** @H_
301
_2@ struct threadedTree @H_
301
_2@ { @H_
301
_2@ short int leftThread; @H_
301
_2@ threadTree * leftChild; @H_
301
_2@ char data; @H_
301
_2@ short int rightThread; @H_
301
_2@ threadTree * rightChild; @H_
301
_2@ } @H_
301
_2@ **************************** @H_
301
_2@ (1)向线索二叉树中插入新的节点。分为两类:插入左儿子和插入右儿子 @H_
301
_2@ 插入右儿子:有个节点p,其右子树为空,想要插入节点child,步骤如下: @H_
301
_2@ 1把parent->rightThread 置为false @H_
301
_2@ 2把child的leftThread 和rightthread置为true @H_
301
_2@ 3把child的leftthread指向p @H_
301
_2@ 4把child的rightChild指向p的rightChild @H_
301
_2@ 5
修改
parten的rightChild,使他指向child @H_
301
_2@ 插入右儿子,有个节点p,它的右子树不为空,想要插入child节点: @H_
301
_2@ 插入后,child变成原来p节点的右子树。原来p节点的右子树成为新的child节点的右子树。另外需要对线索进行更改。因为原来parent节点的的后继节点的中序前驱节点变成了child。 @H_
301
_2@
@H_
301
_2@ 但是上面两种空与非空的情况都可以用同一个程序进行统一的处理。程序就不在这里列出了。后者主要是比前者多一个找后续节点直到为空的语句,别的基本按照上面的五步走。 @H_
301
_2@
@H_
301
_2@ 6 堆 @H_
301
_2@ (1)定义:最大堆就是跟节点为整个树的最大值的完全二叉树,对,是完全二叉树。 @H_
301
_2@ (2)为什么用堆? @H_
301
_2@ 因为与数组和链表相比,堆进行插入和
删除
的操作可能更方便一些。插入和
删除
,堆的复杂度都是lgn,而数组和链表(不管是有序的还是无序的)基本一个复杂度是O1,另外一个复杂对是On的。 @H_
301
_2@ (3)最大堆的插入 @H_
301
_2@ 可以用一个数组来表示这个最大堆。先将新的节点插入到末尾,然后只管树中的这个分支,领用i/2找到父节点,进行比较,然后换位,最终可以讲该id按插入到合适的位置。 @H_
301
_2@
@H_
301
_2@ (4)最大堆的
删除
操作 @H_
301
_2@
删除
最顶的最大元素。保存在一个新的节点中,方便
函数
返回 @H_
301
_2@ 将末尾的最小元素放到顶层,并从尾部
删除
该元素。 @H_
301
_2@ 然后重建堆,比较跟节点和其孩子节点的大小(+1即右节点了),然后进行位置的交换。直到顶端的这个元素找到自己合适的位置了,即可跳出循环了。(在此期间,可将末尾那个东西保存在一个节点中,模拟将其放入到头节点中,然后parent从1开始算,child从2开始算。不断的进行迭代,注意,parent每次都换成下一个child的值,child每次都换成新的parent的child的值(即乘以2就可),注意,最后的迭代中,child的计数不能超过堆中数据的总个数)。 @H_
301
_2@
@H_
301
_2@ 7二叉查找树 @H_
301
_2@ (1)二叉查找树特点: @H_
301
_2@ 可以为空 @H_
301
_2@ 没有重复的元素 @H_
301
_2@ 左子树一定小于根节点 @H_
301
_2@ 右子树一定大于跟节点 @H_
301
_2@ (2)二叉查找树的查找 @H_
301
_2@ 两种方式:递归和非递归。递归就是三句话。==返回根。< 递归
查询
左子树,>递归
查询
右子树。 @H_
301
_2@ 非递归
查询
:就是不同按着树杈走。走到头即可知道是否找到。 @H_
301
_2@ (3)二叉查找树的插入 @H_
301
_2@ 在插入之前,首先要在树中查找这个节点,看是否已经存在,如果已经存在,返回错我。如果没有存在,会指向一个树中的某个叶子节点。然后将新的节点插入到这个被指向的叶子节点的尾部就好了。 @H_
301
_2@ (4)二叉查找树的
删除
@H_
301
_2@ 分为三种情况讨论:1
删除
叶子节点,容易。2
删除
仅有单个子节点的,容易,令其子节点取代被
删除
的及诶单即可。3
删除
有两个儿子的节点,稍微麻烦。用左子树中的最大节点或者右子树中的最小节点代替这个节点,然后将这个节点
删除
。然后,如果用左中的最大和右中的最小进行替代时,也需要
删除
这个节点,此时就需要再继续对该节点子节点进行调整。但是可以证明,一个树中的最大节点或者最小节点一定是度为0或者1的节点。 @H_
301
_2@
@H_
301
_2@ 8选择树 @H_
301
_2@ 对多路进行归并的排序时,可以使用这个。如果不用,多路归并的复杂度应该是n*n,而如果用了这个,复杂度应该是n*logn。能够有一定的提高。 @H_
301
_2@ 总体的思想就是:先从各路归并K中选出分别一个元素,从而形成k个节点,然后两两进行锦标赛,得到k/2个优胜的节点,迭代进行锦标赛,最终得到了一个节点,就是将要在归并中选择的节点。然后,从该节点的出生地队列中再拿下一个树,重建选择树,重建过程和ilogn。这个是优胜树,也有失败树的,我不是太明白这个。 @H_
301
_2@
@H_
301
_2@ 二叉树的基本
内容
就
包括
上面这些
内容
。深入的
内容
,应该是在以后的章节中继续深入探讨。这个部分就到此为止。 @H_
301
_2@
@H_
301
_2@ 下面再简单说一下森林,这个也不太常用。森林主要是可以用来表示集合。其中,表示方式有所改变,之前是父指子,现在是子指父,对于查找操作比较方便。集合中主要涉及到并查操作。这个,等以后用到的时候再看吧。
上一篇:《数据结构》学习笔记--第一章 绪论
下一篇:【数据结构】折半查找(二分查找)
猜你在找的数据结构相关文章
【数据结构】键树
键树的基本概念 键树又称数字查找树(Digital Search Tree)。 它是一棵度大于等于2的树,...
作者:前端之家 时间:2021-02-09
【数据结构】绪论
[TOC] 基本概念 数据: 数据 是对客观事物的符号表示,在计算机科学中指所有能输入到计算机...
作者:前端之家 时间:2021-02-09
【数据结构】证明法
[TOC] 反证法 基本概念: 一般地,假设原命题不成立(即 在原命题的条件下,结论不成立),...
作者:前端之家 时间:2021-02-09
数据结构与算法系列之目录
最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数...
作者:前端之家 时间:2021-02-09
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
作者:前端之家 时间:2021-02-09
[操作系统]操作系统中断机制
1.当中断发生时,cpu立即进入核心态 2.当中断发生后,当前进程进入暂停状态,操作系统内核...
作者:前端之家 时间:2021-02-06
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
作者:前端之家 时间:2021-02-06
[算法] 开放寻址法解决哈希冲突方式
开放寻址法:又称开放定址法,当哈希冲突发生时,从发生冲突的那个单元起,按照一定的次序...
作者:前端之家 时间:2021-02-06
二叉树的基本概念介绍与代码实现(多图+代码)
@ 树的基本概念 图1 树的结点 结点:使用树结构存储的每一个数据元素都被称为“结点”。例...
作者:前端之家 时间:2021-01-30
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件,定义链表结构体,产生随即链表的范围,定义全局头尾节点。 #i...
作者:前端之家 时间:2021-01-30
编程分类
Linux
Windows
CentOS
Ubuntu
Nginx
WebService
Scala
Memcache
Apache
Redis
Docker
Bash
Azure
Tomcat
LNMP
Shell
数据结构
服务器运维
网络安全
最新文章
• 【数据结构】键树
• 【数据结构】绪论
• 【数据结构】证明法
• 数据结构与算法系列之目录
• 【数据结构】数组
• 【数据结构】时间复杂度
• [操作系统]操作系统中断机
• [日常] 浏览器前进后退与数
• [算法] 开放寻址法解决哈希
• 二叉树的基本概念介绍与代
热门标签
更多 ►
xebug
nodemon
docker-copy
dcos
elasticsearc
windows-cont
docker-windo
docker-aws
amazon-cloud
envoyproxy
hashicorp-va
swisscomdev
kafka-python
zscaler
photon-os
docker-swarm
kamon
google-cloud
concourse
wso2-am
persistent-v
api-manager
process-mana
manjaro
jenkins-work
hypriot
remoteapi
keystonejs
bitcoind
bitcoin-test