树:二叉树几种形态(满二叉,完全二叉,线索二叉,二叉排序,平衡二叉,哈夫曼) |
您所在的位置:网站首页 › 所罗门的阵法有哪几种形态 › 树:二叉树几种形态(满二叉,完全二叉,线索二叉,二叉排序,平衡二叉,哈夫曼) |
二叉树的几种形态
除最后一层无任何子节点外,每一层上的所有结点都有两个子结点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上. 二,完全二叉树若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。 完全二叉树是由满二叉树而引出来的。对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树。 三:线索二叉树 1,概念对于n个结点的二叉树,则它有2n个链域,其中有n-1个链域表示有n-1个分支,其余n+1个空链域用来存储线索。如果利用二叉链表存储,一定有n+1哥空指针。另一方面,在每次遍历完后下次还想得到这个线性序列有两种方案,一种是保存该序列,另一种是重新遍历。因此,可以利用在二叉链存储结构中有n+1个空链域,利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为线索,加上线索的二叉树称为线索二叉树。 2,线索二叉树的结构二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构,使每个结点都有了唯一前驱和后继(第一个结点无前驱,最后一个结点无后继)。对于二叉树的一个结点,查找其左右子女是方便的,其前驱后继只有在遍历中得到。为了容易找到前驱和后继,有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd,这种方法增加了存储开销,不可取;二是利用二叉树的空链指针。现将二叉树的结点结构重新定义如下: | lchild | ltag | data |rtag |rchild| | ————- |:————-:| —–:| 其中:ltag=0 时lchild指向左子女; ltag=1 时lchild指向前驱; rtag=0 时rchild指向右子女; rtag=1 时rchild指向后继; 四,二叉排序数二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;(左小) (2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;(右大) (3)左、右子树也分别为二叉排序树; 五,平衡二叉树 1,概念当且仅当两个子树的高度差不超过1时,这个树是平衡二叉树。(同时是排序二叉树) 我们知道,对于一般的二叉搜索树,其期望高度(即为一棵平衡树时)为log2n,其各操作的时间复杂度(O(log2n))同时也由此而决定。但是,在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况,但是在进行了多次的操作之后,由于在删除时,我们总是选择将待删除节点的后继代替它本身,这样就会造成总是右边的节点数目减少,以至于树向左偏沉。这同时也会造成树的平衡性受到破坏,提高它的操作的时间复杂度。 2,平衡定义平衡二叉树,又称AVL树。其每个节点(不一定为根节点)的左子树和右子树的高度最多差1的二叉查找树。 常用算法有:红黑树、AVL树、Treap等。 平衡二叉树的调整方法: 1,LL型(右旋): 在最小平衡子树根节点平衡因子>=2且在根节点的左孩子的左孩子插入元素,进行右旋
哈夫曼树,英文名 Huffman Tree, 又称最优二叉树(程序运行效率最优解)。 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |