当前位置: 首页 > 科技观察

详细讲解二叉树的遍历和完全二叉树等6种二叉树

时间:2023-03-19 12:47:19 科技观察

树在数据结构中占有非常重要的地位,尤其是二叉树。经常是java面试必问的环节,二叉树的应用场景真的很常见,需要好好掌握。但是长期以来,很多同学并没有完全掌握二叉树。今天要讲的是二叉树。我希望您喜欢Java数据结构和算法的主题。仔细阅读之后,你会对二叉树有一个更完整的认识。本文作者:陈锐|mikechen友智学院创始人将重点关注以下几点:)左撇子和右撇子1.什么是二叉树二叉树:是一种树状结构,每个节点只能有两个子节点,俗称“大裤衩”,形象特殊。通常子树被称为“左子树”和“右子树”。看下图就可以秒懂。2.二叉树的遍历方法2.1二叉树的遍历主要有三种:1)一(根)序遍历(根左右)2)中(根)序遍历(左根右)3)后(根)序遍历序遍历(左右根)2.2先序遍历(左右根)先从第一种先序遍历说起。主要的遍历顺序如下:1)先访问根节点2)然后先序遍历左子树3)再先序遍历右子树子树还是一个例子。如果下图的前序遍历按照前序(根左根右)遍历,结果会是:ABDFECGHI2.3中序遍历(左根右)1)先序遍历左子树2)然后是根节点3)然后中序遍历右子树还是一个例子。同一个二叉树的中序遍历是中序遍历(左根右),结果为:DBEFAGHCI2.4后序遍历1)左子树的后序遍历2)右子树的后序遍历subtree3)然后访问根节点或者举个例子,同一个二叉树按照后序遍历(左右根)后序遍历结果为:DEFBHGICA3。二叉树的种类基本有:满二叉树完全二叉树二叉查找树平衡AVL树红黑树也属于AVL树。让我从完整的二叉树开始。3.1满二叉树1)满二叉树的深度为k,一棵有2^k-1个节点的树就是满二叉树2)满二叉树的形式3)满二叉树的特点All内部节点有两个子节点,最下面一层是叶子节点。若一棵树的深度为h,最大层数为k,深度与最大层数相同,即k=h;第k层节点数为:2^(k-1)汇总点数为:2^k-1(2的k次方减一)节点总数必须为奇数。树高:h=log2(n+1)3.2。完全二叉树1)如果一棵完全二叉树的深度设置为h,除第h层外,每层(1~h-1)的节点数达到最大数,第h层的所有节点连续集中在最左边,就是一棵完全二叉树。2)完全二叉树的形式3)完全二叉树的特征深度是一棵k的完全二叉树,最少有2^(k-1)个节点,最多有2^k-1个节点。树高h=log2n+1满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树3.3.BinarySearch/Search/SortTree-BST1)BinarySearchTreeBinarySearchTreeBST(BinarySearch/SortTree)又名二叉搜索树,二叉排序树备注:下面我统称为二叉搜索树,但是你需要要知道二叉搜索树、二叉查找树和二叉排序树其实是同一棵树。2)二叉搜索树的特点左子树上所有节点的值都小于等于其根节点的值右子树上所有节点的值都大于等于其根节点的值3)二叉查找树的优缺点优点:查找速度快,二叉查找树比普通树查找快缺点:出现平衡问题经过多次插入删除,二叉查找树可能会导致结构如右图:搜索性能已经是线性的,所以在使用二叉搜索树的时候,还要考虑尽可能保持左图上面的结构,避免右图上面的结构,也就是所谓的“平衡”“问题。4)二叉搜索树的时间复杂度二叉搜索树的时间复杂度比普通的树搜索要快,查找、插入和删除的时间复杂度为O(logN)。缺点二叉搜索树有一个极端的情况,就是会变成一个类似线性链表的结构。这时候时间复杂度就会变成O(N)。为了解决这种情况,就有了下面我要讲的二叉平衡树。备注:时间复杂度O(1):时空复杂度最低,即耗时与输入数据大小无关,无论输入数据增加多少倍,耗时/占用空间将保持不变。hash算法是典型的O(1)时间复杂度。无论数据量有多大,都可以通过一次计算找到目标。O(n):表示数据量增加几倍,耗时也增加几倍。比如常见的遍历算法。O(logn):当数据增加n倍时,耗时增加logn倍(这里的log以2为单位,比如当数据增加256倍时,耗时只增加8倍,这不仅仅是线性的,而且时间复杂度更低)。二进制搜索是一种O(logn)算法。每次搜索排除一半的可能性,在256条数据中搜索8次即可找到目标。3.4.平衡二叉树(AVL树)1)BalancedbinarytreeBalancedbinarytree全称balancedbinarysearchtree,也叫AVL树,是一种自平衡树,从上面的二叉搜索树升级而来,重点是改善平衡问题.2)平衡二叉树AVL树的特点也规定了左节点小于根节点,右节点大于根节点。并且还规定了左子树和右子树的高度差不能超过1,这样就保证了不会变成线性链表。3)如何解决AVL树的平衡,主要是通过左旋和右旋来防止特殊情况下出现下面的线性结构。因此,下图中的左右旋转就是用来解决上述平衡问题的。但也存在相应的缺点。为了保持自身的平衡,需要在插入和删除节点时频繁旋转节点。4.结语通过上面的介绍,我已经对二叉树有了初步的了解。希望读者能够掌握本文介绍的基础知识,在脑海中建立二叉树模型,为后续数据结构和算法的学习打下坚实的基础。