二叉树概念基础

1 树的介绍

1.1 树的定义

树是一种数据结构，定义树的一种自然方式是递归法。一颗树是由一些节点组成的具有层次关系的集合。若集合为空集，则称为空树；若不是空集，则树由一个称作 根(root) 的节点r与零个或多个非空子树组成；每个子树的根都与根节点r由一条有向 边(edge) 相连接。子树的根称为根节点r的“儿子(child)**”，而根节点r称为子树的根的“父亲(parent)**”。

1.2 树的基本术语

• **叶子节点(leaf node)**：度为零的结点。
• **分支结点(branch node)**：度不为零的结点。
• **结点的度(degree of node)**：结点拥有的子树的数目。
• **树的度(degree of tree)**：树中结点的最大的度。
• **节点的层次(level of node)**：根结点的层次为1，其余结点的层次等于父结点的层次加1。
• **路径(path)**：节点n₁,n₂,…,n_k的一个序列，其中对于1<=i<=k,节点n_i是n_i+1的的父亲，则该序列成为节点n₁到n_k的路径。
• **路径的长(length of path)**：路径上边的条数。
• **节点的深度(depth of node)**：从根节点到节点n_i的路径的长。因此，根节点深度为0。
• **树的深度(depth of tree)**：最深的树叶的深度。
• **节点的高度(height of node)**：从节点n_i到一片叶子的最长路径长。因此，叶子节点的高度为0。
• **树的高度(height of tree)**：根节点的高度。因此，一棵树的深度和高度总是相等。

2 二叉树介绍

2.1 二叉树的定义

二叉树是每个节点最多有两个子树的树。从定义可知，二叉树是度等于2的树。
二叉树有五种基本形态：空集；仅有根；仅有根和左子树；仅有根右子树；有根和左右子树。

2.2 二叉树的性质

二叉树有以下几个性质：

1. 二叉树第i层上的结点数目最多为 2^i-1 (i≥1)。
2. 深度为k的二叉树至多有2^k-1个结点(k≥1)。
3. 包含n个结点的二叉树的高度至少为log₂ (n+1)。
4. 在任意一棵二叉树中，若叶子结点的个数为n₀，度为2的结点数为n₂，则n₀=n₂+1。

2.3 满二叉树

定义：高度为h，并且由2^h –1个结点的二叉树，被称为满二叉树。即节点数达到了二叉树能够拥有的最大数的二叉树。

2.4 完全二叉树

定义：深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，且第h层所有的结点都连续集中在最左边，被称为完全二叉树。
完全二叉树是对满二叉树的补充，所有满二叉树都是完全二叉树。