【漫画】什么是二叉树？（上）

4

很多新手可能刚接触到数据结构，下面先给出一张关于树的一些基本概念。

二叉树的定义

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。下图展示了一棵普通二叉树：

二叉树的特点

由二叉树定义以及图示分析得出二叉树有以下特点：

1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。

2）左子树和右子树是有顺序的，次序不能任意颠倒。

3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树的性质

1）在二叉树的第i层上最多有2^i-1 个节点 。（i>=1）

2）二叉树中如果深度为k,那么最多有2^k-1个节点。(k>=1）

3）n₀=n₂+1  n₀表示度数为0的节点数，n₂表示度数为2的节点数。

4）在完全二叉树中，具有n个节点的完全二叉树的深度为[log₂n]+1，其中[log₂n]是向下取整。