植树节,种个二叉树吧?

3 月 12 号,是全国的重大节日:植树节,记得小时候就跟随老师一起植过树。现在参加工作了,虽然没有植过树,但是学到过很多树的结构,比如二叉树、B+ 树,红黑树。每次面试必问,恰逢植树节,这里给大家做个二叉树的总结,也方便自己复习。

大白话讲解二叉树

比如现在有个数组,存放了很多用户的名字,需要从这个数组中找到包含指定的用户名,最快的方式是什么?

我们会想到二分查找,虽然这种方式很快,但要达到最快还需要有个条件:数组有序。

如果我们能把插入用户名的时候直接给他排序,那最后的结构就是有序结构。

因此有人设计了一种数据结构:二叉查找树,也叫做二叉树。

如下图所示:这是一种二叉树结构。

  • 只有一个根节点的二叉树。

  • 只有左子树

  • 只有右子树。

  • 完全二叉树。

节点的度

定义:节点拥有的子树数目称为节点的

我们来看下图就一目乐然了。

二叉树的特点

  • 每个节点最多有颗子树,所以二叉树中不存在度大于 2 的节点。
  • 左右子树是有顺序的,次序不能任意颠倒。
  • 即使某个节点只有一颗子树,也是需要区分它是左子树还是右子树。

二叉树的遍历

二叉树的遍历:从二叉树的根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点都能被访问一次,且仅被访问一次。

二叉树的访问次序可以分为四种:

  • 前序遍历。
  • 中序遍历。
  • 后续遍历。
  • 层序遍历。

**前序遍历**:通俗的说就是从二叉树的根结点出发,当第一次到达结点时就输出结点数据,按照先向左在向右的方向访问。

**中序遍历**:就是从二叉树的根结点出发,当第二次到达结点时就输出结点数据,按照先向左再向右的方向访问。

**后序遍历**:就是从二叉树的根结点出发,当第三次到达结点时就输出结点数据,按照先向左再向右的方向访问。

**层次遍历**:就是按照树的层次自上而下的遍历二叉树。

mark

按照前序遍历的结果就是 BADCE。

按照中序遍历的结果就是 ABCDE。

按照后续遍历的结果就是 ACEDB。

按照层次遍历的结果就是 BADCE。

巨人的肩膀:

《算法图解》

https://www.jianshu.com/p/bf73c8d50dc2

本站内容大部分转载于网络,并由站长进行整理后发布,文章版权属于原作者。
如遇版权问题,请查看 本站版权声明
THE END
分享
二维码
海报
植树节,种个二叉树吧?
3 月 12 号,是全国的重大节日:植树节,记得小时候就跟随老师一起植过树。现在参加工作了,虽然没有植过树,但是学到过很多树的结构,比如二叉树、B+ 树,红黑树...
<<上一篇
下一篇>>