二叉树有哪些基本形态

二叉树是数据结构中常见的非线性结构。它由节点和边组成，每个节点最多有两个子节点，称为左子节点和右子节点。二叉树具有多种基本形态，下面将从多个角度分析这些基本形态。

一、按节点度数分类

二叉树的节点度数指的是每个节点拥有的子节点数目。按照节点度数的不同，可以将二叉树分为以下三类：

1. 叶节点二叉树：所有节点度数都为0，即没有子节点的情况。这种情况下，树的高度等于叶节点深度，叶节点深度为0，高度为n-1。

2. 度为2节点二叉树：所有节点度数都为2。即每个节点都有两个子节点，除了叶节点之外的所有节点都是度为2的节点。

3. 斜二叉树：每个节点的度数为1或2，即每个节点都只有一个子节点或者两个子节点。

二、按照形状分类

按照二叉树的形状不同，可以将二叉树分为以下几类：

1. 满二叉树：所有非叶子节点都有两个子节点，且所有叶子节点的深度相同，形成的树称为满二叉树。满二叉树的节点数n为2^h-1，其中h为树的高度。

2. 完全二叉树：对于一棵深度为h的二叉树，如果除了最后一层节点之外，其他层的节点数都满足2^(i-1)个，最后一层节点从左至右排列，形成的树称为完全二叉树。

3. 平衡二叉树：对于一个节点，它的左子树和右子树的高度差不超过1的二叉树称为平衡二叉树。平衡二叉树的插入和查找操作的时间复杂度都是O(log n)。

4. 霍夫曼树：霍夫曼树也是一种特殊的二叉树，不同之处在于霍夫曼树是一种带权路径最短的二叉树。在霍夫曼编码中，为了尽可能地减少编码的长度，常常使用霍夫曼树来进行编码。

三、按照遍历方式分类

前序遍历、中序遍历、后序遍历是二叉树常见的遍历方式。按照遍历方式的不同，二叉树可以分为以下几类：

1. 前序遍历：按照根节点-左子节点-右子节点的顺序遍历。可以得到前序遍历序列。

2. 中序遍历：按照左子节点-根节点-右子节点的顺序遍历。可以得到中序遍历序列。

3. 后序遍历：按照左子节点-右子节点-根节点的顺序遍历。可以得到后序遍历序列。