- 树形结构是一种非线性数据结构
- 树中的每个部分称为结点, 节点间存在分支结构与层次关系
- 每个树形结构都具有一个根结点
- 根据结点之间的关系, 也存在父结点、子结点、兄弟结点的概念
- 不含子结点的结点称为叶节点
- 子树: 对某个结点与其后代结点的整体称呼
- 由于存在父子关系, 树中的结点形成多级结构, 称为层级
- 根结点层级为1, 向下依次递增
- 树中最深结点的层级称为树的高度。
二叉树
- 二叉树是树形结构中的一种, 二叉树中的每个结点最多只能存在2个子结点
- 左子结点、右子结点
- 左子树、右子树
满二叉树
- 除普通二叉树外,还存在一些特殊形式的二叉树
- 如上图, 二叉树的每层结点都达到最大值, 称为满二叉树
完全二叉树
- 二叉树除最后一层外, 每层结点都达到最大值, 且最后一层结点都位于左侧, 这种形式称为完全二叉树
- 满二叉树也属于完全二叉树
二叉树的存储形式
顺序存储
- 由于完全二叉树的结构链接, 有迹可循, 可采用顺序存储方式
-
链式存储
普通二叉树由于结构不规则, 不适合使用顺序存储, 为了记录结点间的关系, 可使用链式存储方式
- 每个结点通过value 表示值, left、right 表示左右子结点
二叉树的遍历
- 二叉树的遍历从根节点开始, 根据数据访问的顺序不同存在三种遍历形式: 前序遍历、中序遍历、后续遍历
- 这里的序表示树根结点的访问顺序
前序遍历
- 按 根结点 -> 左子树 -> 右子树 顺序进行遍历
- 上述二叉树前序遍历结果为: ABDGHECFI
递归解法
力扣
中序遍历
- 按 左子树 -> 根结点 -> 右子树 顺序进行遍历
- 上述二叉树的中序遍历结果为: GDHBEACIF
后序遍历
- 按 左子树 -> 右子树 -> 根结点 顺序进行遍历
- 上述二叉树的后序遍历结果为: GHDEBIFCA
二叉树的最大深度
- 前序遍历操作时使用的算法称为深度优先搜索算法
- 计算二叉树最大深度同样可以采用这种方式
二叉树的层序遍历
二叉搜索树
- 二叉搜索树是一种特殊的二叉树, 简称 BST
- 左子树的结点小于根节点, 右子树的节点大于根节点
- 子树也为二叉搜索树