网站建设系统开发需要多少钱,wordpress php.ini,蜜雪冰城网络营销方案,wordpress主题php7文章目录 一、树结构简介1.1.简单了解树结构1.2.树结构的表示方式 二、二叉树2.1.二叉树简介2.2.特殊的二叉树2.3.二叉树的数据存储 三、二叉搜索树3.1.认识二叉搜索树3.2.二叉搜索树应用举例 一、树结构简介
1.1.简单了解树结构
什么是树#xff1f;
真实的树#xff1a;… 文章目录 一、树结构简介1.1.简单了解树结构1.2.树结构的表示方式 二、二叉树2.1.二叉树简介2.2.特殊的二叉树2.3.二叉树的数据存储 三、二叉搜索树3.1.认识二叉搜索树3.2.二叉搜索树应用举例 一、树结构简介
1.1.简单了解树结构
什么是树
真实的树 树的特点
树一般都有一个根连接着根的是树干树干会发生分叉形成许多树枝树枝会继续分化成更小的树枝树枝的最后是叶子
现实生活中很多结构都是树的抽象模拟的树结构相当于旋转180°的树。 树结构对比于数组/链表/哈希表有哪些优势呢
数组
优点可以通过下标值访问效率高缺点查找数据时需要先对数据进行排序生成有序数组才能提高查找效率并且在插入和删除元素时需要大量的位移操作
链表
优点数据的插入和删除操作效率都很高缺点查找效率低需要从头开始依次查找直到找到目标数据为止当需要在链表中间位置插入或删除数据时插入或删除的效率都不高。
哈希表
优点哈希表的插入/查询/删除效率都非常高缺点空间利用率不高底层使用的数组中很多单元没有被利用并且哈希表中的元素是无序的不能按照固定顺序遍历哈希表中的元素而且不能快速找出哈希表中最大值或最小值这些特殊值。
树结构
优点树结构综合了上述三种结构的优点同时也弥补了它们存在的缺点虽然效率不一定都比它们高比如树结构中数据都是有序的查找效率高空间利用率高并且可以快速获取最大值和最小值等。
总的来说每种数据结构都有自己特定的应用场景
树结构
树Tree:由 nn ≥ 0个节点构成的有限集合。当 n 0 时称为空树。
对于任一棵非空树n 0它具备以下性质
数中有一个称为**根Root**的特殊节点用 **r **表示其余节点可分为 mm 0个互不相交的有限集合 T1T2…Tm其中每个集合本身又是一棵树称为原来树的子树SubTree。
树的常用术语 节点的度Degree节点的子树个数比如节点B的度为2树的度树的所有节点中最大的度数如上图树的度为2叶节点Leaf度为0的节点也称为叶子节点如上图的HI等父节点Parent度不为0的节点称为父节点如上图节点B是节点D和E的父节点子节点Child若B是D的父节点那么D就是B的子节点兄弟节点Sibling具有同一父节点的各节点彼此是兄弟节点比如上图的B和CD和E互为兄弟节点路径和路径长度路径指的是一个节点到另一节点的通道路径所包含边的个数称为路径长度比如A-H的路径长度为3节点的层次Level规定根节点在1层其他任一节点的层数是其父节点的层数加1。如B和C节点的层次为2树的深度Depth树种所有节点中的最大层次是这棵树的深度如上图树的深度为4
1.2.树结构的表示方式
最普通的表示方法 如图树结构的组成方式类似于链表都是由一个个节点连接构成。不过根据每个父节点子节点数量的不同每一个父节点需要的引用数量也不同。比如节点A需要3个引用分别指向子节点BCDB节点需要2个引用分别指向子节点E和FK节点由于没有子节点所以不需要引用。
这种方法缺点在于我们无法确定某一结点的引用数。
儿子-兄弟表示法 这种表示方法可以完整地记录每个节点的数据比如
//节点A
Node{//存储数据this.data data//统一只记录左边的子节点this.leftChild B//统一只记录右边的第一个兄弟节点this.rightSibling null
}//节点B
Node{this.data datathis.leftChild Ethis.rightSibling C
}//节点F
Node{this.data datathis.leftChild nullthis.rightSibling null
}这种表示法的优点在于每一个节点中引用的数量都是确定的。
儿子-兄弟表示法旋转
以下为儿子-兄弟表示法组成的树结构 将其顺时针旋转45°之后 这样就成为了一棵二叉树由此我们可以得出结论任何树都可以通过二叉树进行模拟。但是这样父节点不是变了吗其实父节点的设置只是为了方便指向子节点在代码实现中谁是父节点并没有关系只要能正确找到对应节点即可。
二、二叉树
2.1.二叉树简介
二叉树的概念如果树中的每一个节点最多只能由两个子节点这样的树就称为二叉树
二叉树十分重要不仅仅是因为简单更是因为几乎所有的树都可以表示成二叉树形式。
二叉树的组成
二叉树可以为空也就是没有节点若二叉树不为空则它由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成
二叉树的五种形态 上图分别表示空的二叉树、只有一个节点的二叉树、只有左子树TL的二叉树、只有右子树TR的二叉树和有左右两个子树的二叉树。
二叉树的特性
一个二叉树的第 i 层的最大节点树为2(i-1)i 1深度为k的二叉树的最大节点总数为2k - 1 k 1对任何非空二叉树若 n0 表示叶子节点的个数n2表示度为2的非叶子节点个数那么两者满足关系n0 n2 1如下图所示HEIJG为叶子节点总数为5ABCF为度为2的非叶子节点总数为4满足n0 n2 1的规律。 2.2.特殊的二叉树
完美二叉树
完美二叉树Perfect Binary Tree也成为满二叉树Full Binary Tree在二叉树中除了最下一层的叶子节点外每层节点都有2个子节点这就构成了完美二叉树。 完全二叉树
完全二叉树Complete Binary Tree:
除了二叉树最后一层外其他各层的节点数都达到了最大值并且最后一层的叶子节点从左向右是连续存在只缺失右侧若干叶子节点完美二叉树是特殊的完全二叉树 在上图中由于H缺失了右子节点所以它不是完全二叉树。
2.3.二叉树的数据存储
常见的二叉树存储方式为数组和链表
使用数组
完全二叉树按从上到下从左到右的方式存储数据。 节点ABCDEFGH序号12345678
使用数组存储时取数据的时候也十分方便左子节点的序号等于父节点序号 * 2右子节点的序号等于父节点序号 * 2 1 。
非完全二叉树非完全二叉树需要转换成完全二叉树才能按照上面的方案存储这样会浪费很大的存储空间。 节点ABC^^F^^^^^^M序号12345678910111213
使用链表
二叉树最常见的存储方式为链表每一个节点封装成一个NodeNode中包含存储的数据、左节点的引用和右节点的引用。 三、二叉搜索树
3.1.认识二叉搜索树
二叉搜索树BSTBinary Search Tree也称为二叉排序树和二叉查找树。
二叉搜索树是一棵二叉树可以为空
如果不为空则满足以下性质
条件1非空左子树的所有键值小于其根节点的键值。比如三中节点6的所有非空左子树的键值都小于6条件2非空右子树的所有键值大于其根节点的键值比如三中节点6的所有非空右子树的键值都大于6条件3左、右子树本身也都是二叉搜索树 如上图所示树二和树三符合3个条件属于二叉树树一不满足条件3所以不是二叉树。
总结二叉搜索树的特点主要是较小的值总是保存在左节点上相对较大的值总是保存在右节点上。这种特点使得二叉搜索树的查询效率非常高这也就是二叉搜索树中搜索的来源。
3.2.二叉搜索树应用举例
下面是一个二叉搜索树 若想在其中查找数据10只需要查找4次查找效率非常高。
第1次将10与根节点9进行比较由于10 9所以10下一步与根节点9的右子节点13比较第2次由于10 13所以10下一步与父节点13的左子节点11比较第3次由于10 11所以10下一步与父节点11的左子节点10比较第4次由于10 10最终查找到数据10 。 同样是15个数据在排序好的数组中查询数据10需要查询10次 其实如果是排序好的数组可以通过二分查找第一次找9第二次找13第三次找15…。我们发现如果把每次二分的数据拿出来以树的形式表示的话就是二叉搜索树。这就是数组二分法查找效率之所以高的原因。
