树与二叉树

树的基本概念

树（tree）是一种非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特点。

每一个结点只有一个前件，称为父结点。

没有前件的结点称为根节点。

每一个结点都可以有多个后件，它们都称为该结点的子结点。

没有后件的结点称为叶子结点。

一个结点所拥有的后件的个数称为该结点的度。

所有结点中的最大的度称为树的度

以某结点的一个子结点为根构成的树称为该结点的一棵子树。

叶子结点没有子树。

二叉树

二叉树的基本概念

二叉树的特点：

1. 非空二叉树只有一个根结点
2. 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

满二叉树与完全二叉树

满二叉树与完全二叉树是两种特殊的二叉树。

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。

完全二叉树

完全二叉树是指最后一层外，每一层上的结点数均达到最大值，而在最后一层上只缺少右边的若干结点。

满二叉树也是完全二叉树，而完全二叉树不一定是满二叉树

二叉树的基本性质

性质1：在二叉树中，第i层的结点数最多为2^i-1个（i≥1）

性质2：在深度为k的二叉树中，结点总数最多为2^k-1个（k≥1）。

性质3：对任意一棵二叉树，度为0的结点（既叶子结点）总是比度为2的结点多一个。

性质4：

1. 具有n个结点的二叉树，其深度至少为[ log₂n ] + 1，其中[log₂n]表示取log₂n的整数部分。
2. 具有n个结点的完全二叉树的深度为[log₂n]+1。

二叉树的存储结构

二叉树通常采用链式存储结构。

用于存储二叉树中各元素的存储结点。

由两部分组成：数据域与指针域。

二叉树遍历

按一定的次序访问二叉树中的每一个结点,使每个结点被访问一次且只被访问一次。

二叉树的遍历分为三种：

1. 前序遍历
2. 中序遍历
3. 后序遍历

D，L，R

D代表访问根结点

L代表遍历根节点的左子树

R代表遍历根节点的右子树

前序遍历：D L R

中序遍历：L D R

后序遍历：L R D

前序遍历(DLR)

先访问根节点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

前序遍历结果：ABDGCEHIF

中序遍历（LDR）：

首先遍历左子树，然后访问根节点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

中序遍历结果:DGBAHEICF

后序遍历(LRD)

首先遍历左子树，然后遍历右子树，最后访问根节点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

后序遍历结果:GDBHIEFCA

考题

扇入代表前件

扇出代表后件