专栏原创出处:github-源笔记文件 github-源码 ,欢迎 Star,转载请附上原文出处链接和本声明。

# 1. 树的概念

具有 n(n0)n(n\ge 0) 个节点的有限集称为树。

n=0n = 0 时称为空树;

n1n\ge 1 时,仅有一个特定的称为根的结点,其余结点可分为 m(m0)m(m\ge 0) 个互不相交的有限集。每一个集合本身又是一棵树,称为根的子树。

特点:树是非线性结构,数据元素具有"一对多"的逻辑关系;树中的每个元素最多有一个前驱结点,有多个后继结点。

# 2. 二叉树

二叉树是一种更为典型的树树状结构。如它名字所描述的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。

二叉树示例图

# 2.1 二叉树的遍历

  • 前序遍历:首先访问根节点,然后遍历左子树,最后遍历右子树。
  • 中序遍历:先遍历左子树,然后访问根节点,然后遍历右子树。
  • 后序遍历:先遍历左子树,然后遍历右子树,最后访问树的根节点。
  • 层级遍历:逐层遍历,二叉树的最大深度也就是层级树。

对于上述三种遍历,我们简化为,前中后只是表明遍历时「根节点的位置」,不管根在哪儿都是从左向右。每次遍历到节点时把它看做时一棵新树按刚刚的方式继续遍历。

我们可以简化为一个不需要记忆的方法:

  • 前序遍历: 左 右
  • 中序遍历:左
  • 后序遍历:左 右

常见算法题:

前序遍历、中序遍历、后序遍历、层级遍历、计算二叉树的最大深度。

从前序与中序遍历序列构造二叉树、从中序与后序遍历序列构造二叉树、二叉树的最近公共祖先

# 2.2 二叉树的类型

满二叉树:又叫完美二叉树,除叶子节点所有子节点都有左右子节点。

完全二叉树:除叶子节点所有子节点都有左右子节点。

# 二叉树相关算法

推荐 力扣-卡片-二叉树

# 参考

本内容随着对数据结构算法的深入,持续更新。

更多相关专栏内容汇总:

最后修改时间: 2/22/2020, 4:51:12 PM