二叉树

二叉树(Binary Tree)的定义和基本术语

定义：是n（n≥0）个结点的有限集合，由一个根结点

以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

逻辑结构：  一对二（1：2）

基本特征  ① 每个结点最多只有两棵子树（不存在度大于2的结点）；

          ② 左子树和右子树次序不能颠倒（有序树）。

树的度：树中结点的度的最大值.二叉树中结点度的最大值为2。

结点的祖先：从根到该结点所经分支上的所有结点。

结点的子孙：以该结点为根的子树中的任一结点。

二叉树的逻辑结构：由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。树中任一结点都可以有0-2个直接后继结点但至多只能有一个直接前趋结点。

二叉树的层数：根所在的层次为1，其孩子的层次为2，依次类推。

二叉树的深度：树中结点的最大层次。

有序树：树中结点的各子树从左至右有次序（最左边为第一个孩子）

无序树：树中结点的各子树无次序。

基本特征:

① 每个结点最多只有两棵子树（不存在度大于2的结点）；

② 左子树和右子树次序不能颠倒。

二叉树的性质：

性质1:在二叉树的第i层上至多有2i-1个结点

性质2:深度为k的二叉树至多有2k-1个结点

性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）

性质4:具有n个结点的完全二叉树的深度必为log2n＋1

性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。

特殊形态的二叉树

满二叉树：一棵深度为k且有2k -1个结点的二叉树。（特点：每层都“充满”了结点）

完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应

满二叉树和完全二叉树的区别

满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。

满二叉树的特点：

◆ 基本特点是每一层上的结点数总是最大结点数。

◆ 满二叉树的所有的支结点都有左、右子树。

◆ 可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。

完全二叉树(Complete Binary Tree)：如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。

或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。

其中  2k-1≦ n≦2k-1。

完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。

完全二叉树的特点：若完全二叉树的深度为k，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。

二叉树遍历

遍历：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。