非空二叉树一共有几种基本形态

二叉树是数据结构中非常重要的一种类型，它是由根节点、左子树、右子树三部分组成的数据结构。其中，左右子树也是二叉树。在二叉树中，每个节点最多只能有两个子节点。其中，左子节点的值小于等于根节点的值，右子节点的值大于根节点的值。

在二叉树的构建过程中，有一些基本形态需要重点关注。在本文中，我们将从多个角度分析非空二叉树的基本形态。

一、完全二叉树

完全二叉树是二叉树的一种特殊结构，它除了最后一层，其余的层都是满二叉树。如下图所示为一棵完全二叉树。


完全二叉树的性质：

1. 第i层节点数最多为2^(i-1)个（i>=1）

2. 深度为k的完全二叉树，节点数最多为2^k - 1个

3. 若序号为i的节点有左子树（i≤n），则其左子树的编号为2i，右子树的编号为2i+1；若i≥2，则其父亲节点的编号为i/2。

二、满二叉树

满二叉树是指除了叶子节点外每个非叶子节点都拥有左右两个子节点的二叉树。如下图所示为一棵满二叉树。


满二叉树的性质：

1. n层满二叉树的节点数为2^(n+1) - 1个

2. 满二叉树的深度为log2(n+1)

三、二叉搜索树

二叉搜索树是满足以下性质的二叉树：

1. 左子树上所有节点的值均小于它的根节点的值

2. 右子树上所有节点的值均大于它的根节点的值

3. 左右子树也分别为二叉搜索树

如下图所示为一棵二叉搜索树。


二叉搜索树的性质：

1. 左子树上所有节点的值均小于它的根节点的值

2. 右子树上所有节点的值均大于它的根节点的值

3. 左右子树也分别为二叉搜索树

4. 中序遍历二叉搜索树得到的序列是一个递增序列

四、平衡二叉树

平衡二叉树又称为AVL树，它是一种二叉搜索树，其中任何节点的两个子树的高度差不超过1。如下图所示为一棵平衡二叉树。


平衡二叉树的性质：

1. 任何节点的两个子树的高度差不超过1

2. 它是一棵二叉搜索树

综上所述，非空二叉树可以有多种基本形态，包括完全二叉树、满二叉树、二叉搜索树和平衡二叉树等。每种形态都具有独特的性质和应用场景，在数据结构设计中，我们需要根据实际需求来选择不同的形态。