您申请加入课程:数据结构与算法(C++描述)
需要验证您的身份,请输入课程密码:
您的学号:
班级选择:
课程密码:
  • 创建者

    Creator

    潘家辉
  • 活跃度

    Activeness

  • 访问量

    Visits

    211997

教学公告

22软工 第7周安排
[作者: 杨桂芝  发布时间:2023-10-18 10:02:37  浏览次数:326次]

22软件工程《数据结构与算法》第7周教学安排

讲解第5章的内容131134-146

重点

1、树的遍历

2、二叉树的逻辑结构

3、二叉树的性质与练习

4、二叉树的遍历操作

(由中序遍历和前(后)序遍历推断出一颗唯一的二叉树)

3、二叉树的存储结构和递归算法

(链式存储结构的程序实现)

大家可以根据自己的情况进行相应的预习

师说

为什么要有树

一百个数字,无序排列,我们要根据已知的某个数字a,找到a在这一百个数字中的位置(也就是下标),如何寻找?遍历。假设100个数字可以每次遍历,1万个可以每次遍历,100万个还可以么?再计算遍历的频率,不好好掌握,简单的遍历就可以把负责遍历的人给忙死。

这时候人们开始思考,怎么样可以快速定位呢?很简单,如果插入的时候有顺序,那么这样的遍历就变得非常简单。我们都知道1-100中间如果要找某个数字,我们肯定第一个判断的是50这个数值与要定位的数字a的大小对比(因为有序了,所以大小对比才有意义)。如果小于50,那么我们下一次会先判断25,如果大于50,那么我们会判断75……这就是常见的二分法,我们判断出来要找的数字小于50时,我们就不需要去判断50-100中间的这一堆数字,对比遍历,我们就相当于少了一半多工作量,一直循环下去,对比遍历,遍历的数据越多,效率越高。具体研究请自行百度 二分法 时间/空间复杂度,去得出结论。

编程中遇到这样的问题就有更多,因为查找的效率严重影响我们系统反应的时间。计算机中如何体现上文所述的二分法呢?聪明的人根据二分法的判断顺序,设计了一个有左子树,右子树的树形结构,命名为二叉树。二叉树必须有序,否则无序的二叉树,数据来了都不知道要放在什么地方。

二叉树(Binary Tree)的知识点是程序员面试的常考点,所以平时更应该注重这方面知识的积累。这篇文章主要涉及二叉树的基础知识和基础操作,对初学者相当于是一个引导。若想进一步理解二叉树相关的知识,可以找找相关的技术书籍参考学习。

数据来源:https://blog.csdn.net/chuogangrong4739/article/details/101053059

https://zhuanlan.zhihu.com/p/121602717

二叉树常见面试题https://www.cnblogs.com/33debug/p/7252371.html

1. 求两个节点的最近公共祖先;

2. 求二叉树中最远的两个结点的距离;

3. 由前序遍历和中序遍历重建二叉树(如:前序序列:1 2 3 4 5 6 - 中序序列 :3 2 4 1 6 5);

4. 判断一棵树是否是完全二叉树

5. 将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向;

6.求二叉树的宽度;

7. 判断一棵二叉树是否是平衡二叉树;

8.判断一颗二叉树是否是另一颗树的子树。

推荐阅读

  1. 二叉树算法应用案例

https://blog.csdn.net/luyaran/article/details/53992796

2. 算法——二叉树 - 说故事的五公子

https://www.cnblogs.com/wugongzi/p/11216814.html

3. 二叉树的前世今生

https://zhuanlan.zhihu.com/p/121602717


相关课程

扫一扫二维码,快速加入本课程!

放大二维码 查看使用方法
关闭