树与二叉树

• 树形结构是一种非线性数据结构。

• 树中的每个部分称为结点，结点间存在分支结构与层次关系。

• 每个树形结构都具有一个根结点。

• 根据结点之间的关系，也存在父结点、子结点、兄弟结点的概念。

• 不含子结点的结点称为叶节点。

• 子树：对某个结点与其后代结点的整体称呼。

• 由于存在父子关系，树中的结点形成多级结构，称为层级。

• 根节点层级为 1，向下依次递增。

• 树中最深结点的层级称为树的高度。

二叉树

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

• 左子结点、右子结点

• 左子树、右子树

• 除普通二叉树外，还存在一些特殊形式的二叉树。

• 如上图，二叉树的每层结点都达到最大值，称为满二叉树。

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

• 满二叉树也属于完全二叉树。

二叉树的存储形式

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

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

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

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