文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

详解二叉树的遍历以及完全二叉树等6种二叉树

2024-12-24 17:39

关注

[[323923]]

但是一直以来,很多同学对于二叉树的掌握都是不太全面。今天我就来谈谈二叉树,希望你喜欢这个Java数据结构与算法这个专题,认真看完后你会对二叉树会有一个比较完整的了解。

本文作者:陈睿|mikechen 优知学院创始人

重点会谈到以下几点:

1.什么是二叉树

二叉树:就是每个节点都只能有两个子节点的树结构,俗称 “大裤衩”,特别形象。

通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

下图你一看就秒懂了。

 

 

2.二叉树遍历方式

2.1二叉树的遍历主要有三种:

 

 

1)先(根)序遍历(根左右)

2)中(根)序遍历(左根右)

3)后(根)序遍历(左右根)

2.2 先序遍历(根左右)

我先从第一种先序遍历开始谈起,主要的遍历顺序如下:

1)先访问根结点

2)然后先序遍历左子树

3)然后先序遍历右子树

还是举例说明,先序遍历下图

 

 

如果按照先序(根左右)遍历,结果将为: ABDFECGHI

2.3 中序遍历(左根右)

1)先中序遍历左子树

2)然后是根结点

3)然后中序遍历右子树

还是举例说明,中序遍历同一颗二叉树

 

 

按照中序遍历(左根右),结果为: DBEFAGHCI

2.4 后序遍历

1)后序遍历左子树

2)后序遍历右子树

3)然后访问根节点

还是举例说明,后序遍历同一颗二叉树

 

 

按照后序遍历(左右根)结果为:DEFBHGICA

3.二叉树的种类

 

 

基本包含:

我先从满二叉树谈起。

3.1满二叉树

1)满二叉树

一棵树深度为k,2^k-1个节点的树是满二叉树

2)满二叉树的形态

 

 

3)满二叉树的特征

所有内部节点都有两个子节点,最底一层是叶子节点。

如果一颗树深度为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.二叉查找/搜索/排序树-BST

1)二叉搜索树

二叉搜索树BST(Binary Search/ Sort Tree),也称为二叉查找树,二叉排序树

 

 

备注:下面我就以二叉搜索树来统称,但是你要知道二叉搜索树、二叉查找树、二叉排序树,其实是同一种树。

2)二叉搜索树的特点

 

 

左子树上所有结点的值均小于等于它的根结点的值

右子树上所有结点的值均大于等于它的根结点的值

3)二叉搜索树的优缺点

优点:查找速度快,二叉查找树比普通树查找更快

缺点:出现平衡问题

二叉搜索树在经过多次插入与删除后,有可能导致如下右图的结构:

 

 

搜索性能已经是线性的了,所以,使用二叉搜索树还要考虑尽可能保持上面左图的结构,和避免上面右图的结构,也就是所谓的“平衡”问题 。

4)二叉搜索树的时间复杂度

时间复杂度

二叉查找树比普通树查找更快,查找、插入、删除的时间复杂度为O(logN)。

缺点

二叉查找树有一种极端的情况,就是会变成一种线性链表似的结构,此时时间复杂度就变味了O(N),为了解决这种情况,所以出现了下面我即将谈到的二叉平衡树。

备注:时间复杂度

3.4.平衡二叉树(AVL树)

1)平衡二叉树

平衡二叉树全称平衡二叉搜索树,也叫AVL树,是一种自平衡的树,从上面二叉搜索树升级过来的,重点是改进了平衡问题。

2)平衡二叉树的特征

 

 

3)AVL树怎么解决平衡

主要就是通过左旋和右旋来解决,防止特殊情况下出现下面的线性结构。

 

 

所以通过下图的左旋和右旋来解决上面的平衡问题。

 

 

 

 

但也有对应的缺点,由于要维持自身的平衡,所以进行插入和删除结点操作的时候,需要对结点进行频繁的旋转。

4.结语

通过上述的介绍,已经对于二叉树有了初步的认识。本篇文章介绍的基础知识希望读者能够牢牢掌握,并且能够在脑海中建立一棵二叉树的模型,为后续学习数据结构与算法打好基础。

来源:今日头条内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯