• 树形结构是一种非线性数据结构
• 树中的每个部分称为结点， 节点间存在分支结构与层次关系
• 每个树形结构都具有一个根结点
• 根据结点之间的关系， 也存在父结点、子结点、兄弟结点的概念
• 不含子结点的结点称为叶节点
• 子树： 对某个结点与其后代结点的整体称呼
• 由于存在父子关系， 树中的结点形成多级结构， 称为层级
• 根结点层级为1， 向下依次递增
• 树中最深结点的层级称为树的高度。

二叉树

• 二叉树是树形结构中的一种， 二叉树中的每个结点最多只能存在2个子结点
• 左子结点、右子结点
• 左子树、右子树

满二叉树

• 除普通二叉树外，还存在一些特殊形式的二叉树
• 如上图， 二叉树的每层结点都达到最大值， 称为满二叉树

完全二叉树

• 二叉树除最后一层外， 每层结点都达到最大值， 且最后一层结点都位于左侧， 这种形式称为完全二叉树
• 满二叉树也属于完全二叉树

二叉树的存储形式

顺序存储

• 由于完全二叉树的结构链接， 有迹可循， 可采用顺序存储方式

• 如按照从左往右， 从上到下的顺序将结点存储在数组中

  链式存储

• 普通二叉树由于结构不规则， 不适合使用顺序存储， 为了记录结点间的关系， 可使用链式存储方式

• 每个结点通过value 表示值， left、right 表示左右子结点

二叉树的遍历

• 二叉树的遍历从根节点开始， 根据数据访问的顺序不同存在三种遍历形式： 前序遍历、中序遍历、后续遍历
• 这里的序表示树根结点的访问顺序

前序遍历

• 按 根结点 -> 左子树 -> 右子树 顺序进行遍历
• 
• 上述二叉树前序遍历结果为： ABDGHECFI

递归解法
力扣

中序遍历

• 按 左子树 -> 根结点 -> 右子树 顺序进行遍历
• 
• 上述二叉树的中序遍历结果为： GDHBEACIF

力扣

后序遍历

• 按 左子树 -> 右子树 -> 根结点 顺序进行遍历
• 
• 上述二叉树的后序遍历结果为： GHDEBIFCA

力扣

二叉树的最大深度

• 前序遍历操作时使用的算法称为深度优先搜索算法
• 计算二叉树最大深度同样可以采用这种方式

力扣

二叉树的层序遍历

力扣

二叉搜索树

• 二叉搜索树是一种特殊的二叉树， 简称 BST
• 左子树的结点小于根节点， 右子树的节点大于根节点
• 子树也为二叉搜索树

力扣