旅游网站定位,招人在哪个网站比较好找,互联网创业项目简介,中企动力科技股份有限公司西安分公司树的概述树是一种非常常用的数据结构#xff0c;树与前面介绍的线性表#xff0c;栈#xff0c;队列等线性结构不同#xff0c;树是一种非线性结构1.树的定义和基本术语计算机世界里的树#xff0c;是从自然界中实际的树抽象而来的#xff0c;它指的是N个有父子关系的节点…树的概述树是一种非常常用的数据结构树与前面介绍的线性表栈队列等线性结构不同树是一种非线性结构1.树的定义和基本术语计算机世界里的树是从自然界中实际的树抽象而来的它指的是N个有父子关系的节点的有限集合。对于这个有限的节点集合而言它满足如下条件当N0时改节点集合为空这课树也被称为空树在任意的非空树中有且仅有一个根(root)节点当N1时除根节点以外的其余节点可分为M个互为相交的有限集合T1,T2,...,Tm其中的每个集合本身又是一棵树并称其为根的子树(subtree)。从上面定义可以发现树的递归特性一棵树由根和若干棵子树组成而每棵子树又由若干棵更小的子树组成。树中任一节点可以有0或多个子节点但只能有一个父节点。根节点是一个特例根节点没有父节点叶子节点没有子节点。树中每个节点既可以是其上一级节点的子节点也可以是下一级节点的父节点因此同一个节点既可以是父节点也可以是子节点(类似于一个人—————他既是他儿子的父亲又是他父亲的儿子)。很显然父子关系是一种非线性关系所以树结构是非线性结构。如果按节点是否包含子节点来分节点可以分成以下两种:普通节点包含子节点的节点叶子节点没有子节点的节点因此叶子节点不可作为父节点如果按节点是否具有唯一的父节点来分节点有可分为如下两种根节点没有父节点的节点根节点不可作为子节点普通节点具有唯一父节点的节点一棵树只能有一个根节点如果一棵树有了多个根节点那么它已经不再是一棵树了而是多棵树的集合有时也被称为森林。示意图如下tree.PNG与树有关的术语有如下一些节点树的最基本组成单元通常包括一个数据元素及若干指针用于指向其他节点。节点的度节点拥有的子树的个数被称为节点的度(degree)树的度树中所有节点的度的最大值就是该树的度叶子节点度为0的节点被称为叶子节点或终端节点分支节点度不为0的节点被称为分支节点或非终端节点子节点,父节点兄弟节点节点的子树的根被称为该节点的子节点而该节点称为子节点的父节点(parent).具有相同父节点的子节点之间互称为兄弟节点。节点的层次(level):节点的层次从根开始算起根的层次值为1其余节点的层次值为父节点层次值加l。树的深度(depth):树中节点的最大层次值称为树的深度或高度。有序树与无序树:如果将树中节点的各棵子树看成从左到右是有序的(即不能互换),则称该树为有序树,否则称为无序树。祖先节点(ancestor)从根到该节点所经分支上的所有节点后代节点(descendant):以某节点为根的子树中任一节点都称为该节点的后代节点。森林(forest):森林是两颗或两颗以上互不相交的树的集合删去一棵树的根就得到一个森林。树的基本操作如果需要实现一棵树程序不仅要以合适的方式保存该树的所有节点还要记录节点与节点之间的父子关系。接下来还应该为树实现如下基本操作。初始化:通常是一个构造器用于创建一棵空树或者以指定节点为根来创建树。为指定节点添加子节点判断树是否为空返回根节点返回指定节点(非根节点)的父节点返回指定节点(非叶子节点)的所有子节点返回指定节点(非叶子节点)的第i个子节点返回该树的深度返回指定节点的位置为了实现树这种数据结构程序必须能记录节点与节点之间的父子关系为此有一下两种选择父节点表示法:每个子节点都记录它的父节点。子节点链表示法:每个非叶子节点通过一个链表来记录它所有的子节点。父节点表示法通过前面的介绍可以发现树中除根节点之外的每个节点都有一个父节点。为了记录树中节点与节点之间的父子关系可以为每个节点增加一个parent域用以记录该节点的父节点。用如下图和如下表来表示tree_show.PNG数组索引dataparent0A-11B02C03D04E15F36G37H48I49J410K6.........由此可见只要用一个节点数组来保存树里的每个节点并让每个节点记录其父节点在数组中的索引即可。子节点链表表示法父节点表示法的思想是让每个节点“记住”它的父节点的索引父节点表示法是从子节点着手的;反过来还有另外一种方式:让父节点“记住”它的所有子节点口在这种方式下由于每个父节点需要记住多个子节点因此必须采用“子节点链”表示法。示意图如下tree_linked.PNG二叉树二叉树的定义和基本概念二叉树指的是每个节点最多只能有两个子树的有序树。通常左边的子树被称作“左子树”(left subtree)右边的子树被称为“右子树”(right subtree).由此可见二叉树依然是树它是一种特殊的树。二叉树的每个节点最多只有来两颗树(不存在度大于2的节点)二叉树的子树有左右之分次序不能颠倒。树和二叉树的两个重要区别如下树中节点的最大度数没有限制而二叉树节点的最大度数为2也就是说二叉树是节点的最大度数为2的树。无序树的节点无左右之分而二叉树的节点有左右之分也就是说二叉树是有序树。一棵深度为k的二叉树如果它包含了2^k-1个节点就把这棵二叉树称为满二叉树。满二叉树的特点是。每一层上的节点数都是最大节点数即各层节点数分别为1,2,4,8, 16,...,满二叉树下图所示two_tree.PNG一颗有n个节点的二叉树按满二叉树的编号方式对它进行编号若树中所有节点和满二叉树1~n编号完全一致则称该树为完全二叉树。也就是说如果一颗二叉树除最后一层外其余层的所有节点都是满的并且最后一层或者是满的或者仅在右边缺少若干连续的节点则此二叉树就是完全二叉树。综上所述二叉树大致有如下几个性质二叉树第i层上的节点数据至多为2的i-1次方深度为k的二叉树至多有2的k次方-1个节点.满二叉树的每层节点的数量依次为1, 2, 4,8,…,因此深度为k的满二叉树包含的节点数为公比为2的等比数列的前k项总和即2的k次方一1。在任何一棵二叉树中如果其叶子节点的数量为n0,度为2的子节点数量为n2则n0n2 1。这是因为:如果为任意叶子节点增加一个子节点则原有叶子节点变成非叶子节点新增节点变成叶子节点上述等式不变;如果为任意叶子节点增加两个子节点则原有叶子节点变成度为2的非叶子lto点新增的两个节点变成叶子节点上述等式依然不变。具有n个节点的完全二叉树的深度为log2(n1)对于一颗具有n个节点的完全二叉树的节点按层自左向右编号则对任一编号为i(ni1)的节点有下列性质。当i1时节点i是二叉树的根若i1则节点的父节点是i/2若2i若2i1n,则节点i有右孩子右孩子的编号是2i1;否则节点无右孩子。1~n/2范围的节点都是有孩子节点的非叶子节点其余的节点全部都是叶子节点。编号为n/2的节点可能只有左子节点也可能即有左子节点又有右子节点。二叉树的基本操作二叉树记录其节点之间的父子关系更加简单因为二叉树中的每个节点最多只能保存两个子节点。接下来程序也需要为二叉树实现如下基本操作。初始化通常是一个构造器用于创建一颗空树或者以指定节点为根来创建二叉树。为指定节点添加子节点判断二叉树是否为空返回根节点返回指定节点(非根节点)的父节点返回指定节点(非叶子节点)的左子节点返回指定节点(非叶子节点)的右子节点返回该二叉树的深度返回指定节点的位置要实现二叉树这种数据结构有以下三种选择。顺序存储:采用数组来记录二叉树的所有节点。二叉链表存储:每个节点保留一个left,right域分别指向其左、右子节点。三叉链表存储:每个节点保留一个left, right,parent域分别指向其左、右子节点和父节点。二叉树的顺序存储顺序存储指的是充分利用满二叉树的特性:每层的节点数分别为1, 2, 4, 8,…,2的(i-1)2的i次方。一棵深度为i的二叉树最多只能包含2的i次方一1个节点因此只要定义一个长度为2的i次方一1的数组即可存储这棵二叉树。对于普通二叉树(不是满二叉树)那些空出来的节点对应的数组元素留空就可以了。由此可见二叉树采用顺序存储会造成一定的空间浪费。对于下图1所示的二叉树(完全二叉树)采用下图2所示的数组来保存即可。图1.PNG图2.PNG对于左图所示的二叉树需使用右图所示的数组来保存。compare_tree.PNG当使用数组来存储二又树的所有节点时可能会产生一定的空间浪费如果该二叉树是完全二叉树就不会有任何空间浪费了;但如果该二叉树的所有节点都只有右子节点那么就会产生相当大的空间浪费.二叉树的二叉链表存储二叉链表存储的思想是让每个节点都能“记住”它的左右两个子节点。为每个节点增加left,right两个指针分别引用改节点的左右两个子节点因此二叉链表存储的每个节点有如下图结构two_fork_tree.PNG二叉链表存储的二叉树的节点大致有如下定义class Node{Object data;Node left;Node right;}对于这种二叉链表存储的二叉树如果程序需要为指定节点添加子节点也非常容易让父节点的left或right引用指向新节点即可。二叉树的三叉链表存储三叉链表存储的思想是让每个节点不仅“记住”它的左右两个子节点还要“记住”它的父节点因此需要为每个节点增加left,right和parent三个指针分别引用该节点的左右两个子节点和父节点。因此三叉链表存储的每个节点有如下图的结构three_tree.PNG因此三叉链表存储的二叉树的节点大致如下class Node{Object data;Node left;Node right;Node parent;}对于这种三叉链表存储的二叉树如果程序需要为指定节点添加子节点也非常容易除了要维护父节点的left,right引用之外还要维护新增节点的parent引用。遍历二叉树遍历二叉树指的是按某种规律依次访问二叉树的每个节点对二叉树的遍历过程就是讲非线性结构的二叉树的节点排列成线性序列的过程。如果采用顺序结构来保存二叉树程序遍历二叉树非常容易无须进行任何思考直接遍历底层数组即可。如果采用链表来保存二叉树的节点则有以下两种遍历方式。深度优先遍历这种遍历算法将先访问到树中最深层次的节点广度优先遍历这种遍历算法将逐层访问每层的节点先访问根(第一层)节点然后访问第二层的节点.....一次类推。因此广度优先遍历方法又被称为按层遍历。先(前)序遍历二叉树中序遍历二叉树后序遍历二叉树如果L,D,W表示左子树、根、右子树习惯上总是必须先遍历左子树后遍历右子树根据遍历根节点的顺序不同上面三种算法可表示如下。DLR:先序遍历LDR:中序遍历LRD:后序遍历深度遍历的先序遥历、中序遍历、后序遍历这三种遍历方式的名称都是针对根节点(D)而言的。先处理根节点(D)时就称为先序遍历。其次处理根节点(D)时就称为中序遍历;最后处理根节点(D)时就称为后序遍历。先序遍历先序遍历指先处理根节点其处理顺序如下(1) 访问根节点(2) 递归遍历左子树(3) 递归遍历右子树中序遍历中序遍历指其次处理根节点.其处理顺序如下。(1) 递归遍历左子树(2) 访问根节点(3) 递归遍历右子树后序遍历后序遍历指最后处理根节点其处理顺序如下。(1) 递归遍历左子树(2) 递归遍历右子树(3) 访问根节点广度优先(按层)遍历广度优先遍历又称为按层遍历整个遍历算法是先遍历几叉树的第一层(根节点)再遍历根节点的两个子’节点(第二层)……依此类推逐层遍历二叉树的所有节点。为了实现广度优先遍历可以借助于具有FIFO特征的队列来实现。如下所示。建一个队列(先进先出)把树的根节点压入队列。从队列中弹出一个节点(第一个弹出的就是根节点)然后把改节点的左右节点压入队列如果没有子节点则说明已经达到叶子节点了。用循环重复执行2步知道队列为空。当队列为空时说明所有的叶子节点(深度最深的层)都已经经过了队列也就完成了遍历。转换方法由于二叉树是一种更“确定”(它的每个节点最多只有两个子节点)的数据结构因此不管是存储、增加、删除节点还是遍历节点程序都可以更简单、方便地实现口反之由于树的每个节点具有个数不确定的节点因此程序实现起来更复杂。为了充分利用二义树的简单易用性可以将普通树转换为二叉树以二叉树的形式来保存柞通树当程序需要树时再将悦义树转换为普通树。森林其实更简单如果将一棵伶通树的根节点去掉这棵树就变成了森林。或者可以转换一下思维森林其实就是有多个根节点的树。森林树和二叉树的转换有序树森林和二叉树之间有一一映射的关系可以进行互相转换。多叉树向二叉树的方法如下(1)加虚线同一个父节点的相邻兄弟节点之间加虚线(2)抹实线每个节点只保留它与最左子节点的连线与其他字节点的连线都被抹掉。(3)虚改实:虚线改为实线如图就是多叉图向二叉树转换的结果forest_tree.PNG图中的虚线就是新增的“父子”关系。这个转换结果来看多叉树1转换为二叉树的方法的关键思想就是所有子节点只保留子节点其他子节点转为左子节点的右子节点链。按照这个转换思路森林也可转换为二叉树————只要把森林当成一颗根节点被删除的多叉树即可。下图示范了将森林转换为二叉树的结果。forest_to_tree.PNG反过来二叉树也可恢复出对应的多叉树森林恢复方法如下-(1)加虚线若某节点I是父节点的左子节点则为该节点I的右孩子链的所有节点分别于节点I的父节点添加连线(2)抹线把有虚线的节点于原父节点的连线抹去(3)整理虚改实并按层排列把二叉树转换为多叉树two_tree_more_tree.PNG如果二叉树的根节点有右子节点————右子节点就代表根节点的兄弟节点这种情况会转换得到森林。把二叉树转换为森林tree_to_forest.PNG树的链表存储根据上面介绍的理论二义树可以和多叉树之间进行自由转换因此可以得到普通树的另外一种保存方式:以二义树的形式保存多叉树实际需要的时候再将二叉树转换为普通树。至于到底以哪种方式来保存二叉树完全是自由的。通常会选择使用三叉链表存储方式来保存二叉树这样得到的二叉树操作起来更方便进行二叉树和多叉树之间转换时也更方便。哈夫曼树哈夫曼树又被称为最优二叉树是一种带权路径最短的二叉树。哈夫曼树是二叉树的一种应用在信息检索中很常用.哈夫曼树的定义和基本概念在介绍哈夫曼树之前先来介绍一些相关的概念。节点之间的路径长度从一个节点到另一个节点之间的分支数量称为两个节点之间的路径长度树的路径长度从根节点到树中的每一个节点的路径长度之和。对于下图所示的而二叉树该树的路径长度为17.即012234517.hafuman.PNG节点的带权路径长度:从该节点到根节点之间的路径长度与节点的权的乘积树的带权路径长度树中所有叶子节点的带权路径长度之和。带权路径如图daiquan.PNG对于哈夫曼树有一个很重要的定理:对于具有对n个叶子节点的哈夫曼树一共需要2乘以n-1个节点。因为对于二叉树来说有三种类型节点即度数为2的节点、度数为1的节点和度数为0的叶子节点而哈夫曼树的非叶子节点都是由两个节点合并产生的所以不会出现度数为1的节点。而生成的非叶子节点的个数为叶子节点个数-1因此n个叶子节点的哈夫曼树一共需要Z乘以n-1个节点。创建哈夫曼树创建哈夫曼树可以按如下步骤进行根据给定的。个权值{wl,w2,...,wn}构造n棵二叉树的集合F{T1,T2,...,Tn} }F集合中每棵二叉树都只有一个根节点。选取F集合中两棵根节点的权值最小的树作为左、右子树以构造一棵新的二叉树且将新的二叉树的根节点的权值设为左、右子树上根节点的权值之和。将新的二叉树加入到F集合中并删除第2步中被选中的两棵树。重复第2和3步直到F集合中只剩下一棵树这棵树就是哈夫曼树。下图显示了创建哈夫曼树的过程。hafuman_tree.PNG哈夫曼编码根据哈夫曼树可以解决报文编码问题。假设需要对一个字符串如“a6cdabcaba”进行编码将它转换为唯一的二进制码但要求转换出来的二进制码的长度最小。假设每个字符在字符串中出现的频率为W}其编码长度为L编码字符有n个则编码后二进制码的总长度为W1L1W2L2W3L3...WnLn这正好符合哈夫曼树的处理原则。因此可采用哈夫曼树的原理构造二进制编码并使电文总长最短。对于“abcdabcaba”字符串总共只有a,b,c,d,这四个字符它们出现的次数是4,3,2,1次__这相当于它们的权值。于是将a,b,c,d四个字符以出现的次数为权值构造哈夫曼树得到如下图结构hanfuman1.PNG从哈夫曼树根节点开始对左子树分配代码“0”对右子树分配代码“1”一直到达叶子节点。然后.将从树根沿每条路径到达叶子节点的代码排列起来便得到了每个叶子节点的哈夫曼编码。下图显示了对a, b, c, d四个字符编码得到的哈夫曼编码。hanfuma2.PNG排序二叉树排序二叉树是一种特殊结构的二叉树通过它可以非常方便地对树中的所有节点进行排序和检索排序二叉树要么是一颗空二叉树要么是具有下列性质的二叉树若它的左子树不空则左子树上所有的节点的值均小于它的根节点的值若它的右子树不空则右子树上所有的节点均大于它的根节点的值它的左右子树分别为排序二叉树。下图显示了一棵排序二叉树.对于排序二叉树若按中序遍历就可以得到由小到大的有序序列。中序遍历得:{2,3,4,8,9,9,10,13,15,18)sort_tree.PNG创建排序二义树的步骤就是不断地向排序二义树添加节点的过程几体如下。以根节点为当前节点开始搜索拿新节点的值和当前节点开始搜索如果新节点的值更大则以当前的右子节点作为新的当前节点的右子节点作为新的当前节点;如果新节点的值更小则以当前节点的右子节点作为新的当前节点。重复第2和3两个步骤直到搜索到合适的叶子节点。将新节点添加为第4步找到的叶子节点的子节点如果新节点更大则添加为右子节点;否则,添加为左子节点。当程序从排序二叉树中删除一个节点之后为了让它依然保持为排序哭叉树必须对该排序二叉树进行维护。维护可分为如下几种情况。被删除节点是叶子节点只需将它从其父节点中删除。被删除转点p只有左子树或只有右子树如果p是它的父节点的左子节点则将p的左子树或右子树添加成p一节点的父节点的左子节点即可;如果p是它的父节点的右子节点则将p的左子树或右子树添加成P节点的父节点的右子节点即可。简单来说如果要侧除的节点只有一个子节点即可用它的子节点来代替要侧除的节点。被删除的节点只有左子树的情况delete_only_left_tree.PNG被删除节点只有右子树的情况delete_only_right_tree.PNG若被删除节点p的左、右子树均非空则有以下两种做法。将pL设为P的父节点q的左或右子节点(取决于P是其节父点q的左、右子节点)将pR设为P节点的中序前趋节点s的右子节点(s是pL最右下的节点也就是pL子树中最大的节点)。采用这种方式删除节点的示意图如下delete_left_right.PNG以P节点的中序前趋或后继替代P所指节点然后从原排序二叉树中删除中序前趋或后继节点。简单来说就是用大于p的最小节点或小于P的最大节点代替P节点点,采用这种方式删除节点的示意图如下图delete_left_right_center.PNG红黑树排序二叉树虽然可以快速检索但在最坏的情况下如果插入的节点集本身就是有序的要么是由小到大排列要么是由大到小排列那么最后得到的排序二义树将变成链表:所有节点只有左节点(如果插入节点集合本身是由大到小排列的)或者所有节点只有右节点(如果插入节点集合本身是由小到大排列的)。在这种情况下排序二叉树就变成了普通链表其检索效率就会很低。为了改变排序二叉树存在的不足对二叉树进行改进————红黑树他将这种排序二叉树称为“对称二叉B树”。红黑树是一个更高效的检索二叉树因此常常用来实现关联数组。典型的JDK提供的集合类TreeMap本身就是一颗红黑树的实现。红黑树在原有的排序二叉树上增加如下几个要求性质l:每个节点要么是红色要么是黑色。性质2:根节点永远是黑色的。除质3:所有的叶子节点都是空节点(即null)并且是黑色的。性质4:每个红色节点的两个子节点都是黑色的。(从每个叶子到根的路径上不会有两个连续的红色节点。)性质5:从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。java实现的红黑树结构如下图red_black_tree.PNG根据性质5红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度(black-height).性质4则保证了从根节点到叶子节点的最长路径的一长度不会超过任何其他路径的2倍。假如有一棵黑色高度为3的红黑树从根节点到叶子节点的最短路径长度是2,该路径上全是黑色节点〔黑色节点-黑色节点-黑色节点)。最长路径也只可能为4,在每个黑色节点之间插入一个红色节点〔黑色节点-红色节点-黑色书点-红色节点-黑色节点)性质4保证绝不可能插入更多的红色节点。由此可见红黑树中最长的路径就是一条红黑交替的路径。由此可以得出结论对于给定的黑色高度为N的红黑树从根到叶子节点的最短路径长度为N-1最长路径长度为2*(N-1).红黑树通过上面这种限制来保证它大致是平衡的—因为红黑树的高度不会无限增高这样能保证红黑树在最坏的情况下都是高效的不会出现普通排序二叉树的情况。由于红黑树只是一棵特殊的排序二叉树因此对红黑树上的只读操作与普通排序二叉树上的只读操作完全相同只是红黑树保持了大致平衡因此检索性能更好.但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征因此插入操作和删除操作都需要进行一定的维护以保证插入节点、删除节点后的树依然是红黑树。插入操作插入操作按如下步骤进行:以排序二叉树的方法插入新节点并将它设为红色。进行颜色调换和树旋转这种颜色调换和树旋转就比较复杂了下面将分情况进行介绍。在介绍中把新插入的节点定义为N节点把N节点的父节点定义为P节点把P节点的兄弟节点定义为U节点把P节点的父节点定义为G节点。情形1新节点N是树的根节点没有父节点。在这种情形下直接将它设置为黑色以满足性质2。情形2新节点的父节点P是黑色的在这种情形下新插入的节点是红色的因此依然满足性质4。而且因为新节点N有两个黑色叶子节点但是由于新节点N是红色的通过它的每个子节点的路径依然保持相同的黑色节点数因此依然满足性质53.情形3父节点P和父节点的兄弟节点U都是红色的在这种情形下程序应该将P节点、U节点都设置为黑色并将P节点的父节点设置为红色(用来保持性质5)。现在新节点N有了一个黑色的父节点P。由于从P节点、U节点到根节点的任何路径都必须通过G节点这些路径上的黑色节点数目没有改变(原来有叶子和G节点两个黑色节点现在有叶子和P节点两个黑色节点)。经过上面处理后红色的G节点的父节点也有可能是红色的这就违反了性质4因此还需要对G节点递归地进行整个过程〔把G节点当成新插入的节点进行处理)。下图显示了处理过程red_black_tree_1.PNG情形4:父节点P是红色的而其兄弟节点U是黑色的或缺少;且新节点N是父节点P的右子节点而父节点P又是其父节点G的左子节点。在这种情形下对新节点和其父节点进行一次左旋转。接着按情形5处理以前的父节点P(也就是把P当成新插入的节点)。这将导致某些路径通过它们以前不通过的新节点N或父节点P其中之一但是这两个节点都是红色的因此不会影响性质5。red_black_tree_2.PNG情形5:父节点F是红色的而其兄弟节点U是黑色的或缺少:且新节点N是其父节点的左子节点而父节点F父是其父节点G的左子节点。在这种情形下需要对节点G进行一次右旋转口在旋转产生的树中以前的父节点P现在是新节点N和节点G的父节点。由于以前的节点G是黑色的(否则父节点P就不可能是红色的)切换以前的父节点P和节点G的颜色使之满足性质4。性质5也仍然保持满足因为通过这三个节点中任何一个的所有路径以前都通过节点G,现在它们都通过以前的父节点P。在各自的情形下这都是三个节点中唯一的黑色节点。red_black_tree_3.PNG删除操作红黑树的删除操作比插入操作要稍微复杂一些实际上也可按如下步骤进行以排序二叉树的方法删除指定节点。进行颜色调换和树旋转使之满足红黑树特征。
相关文章：
