Python 二叉树的概念案例详解

二叉树简介

关于树的介绍，请参考：https://www.jb51.net/article/222488.htm

一、二叉树简介

二叉树是一种特殊的树形结构，其核心特征是每个节点最多只能拥有两个子树。如图所示，这是一棵典型的二叉树结构。

二叉树由 n 个节点组成（n>=0）。当 n=0 时，称为空二叉树；当 n=1 时，仅包含一个根节点；当 n>1 时，每个节点最多拥有两个子树，通过递归方式构建出完整的二叉树结构。

二叉树的两个子树分别称为左子树（left subtree）和右子树（right subtree）。若节点无子树，则左右子树均为空；若仅有一个子树，需明确区分其为左子树或右子树；若有两个子树，则左右子树均存在。

若树中存在任一节点的子树数量超过两个，则该树不属于二叉树。例如，图中节点 C 拥有三个子树，因此该结构不是二叉树。

二、几种特殊的二叉树

普通二叉树要求所有节点的子树数量不超过两个（0、1 或 2 个）。在此基础上，满足特定规则的二叉树被称为特殊二叉树，主要包括以下几种类型。

1. 完全二叉树：假设二叉树深度为 d（d>1），若除第 d 层外，其他各层节点数均达到最大值，且第 d 层所有节点从左至右连续紧密排列，则称为完全二叉树。

完全二叉树的叶节点仅能出现在最下层和次下层。最下层的叶节点必须靠左紧密排列，若次下层存在叶节点，则需靠右紧密排列。

如图所示，该树深度为 4，除第 4 层外节点数已达最大（即“挂满”），且第 4 层节点紧密靠左排列（无空位），因此这是一棵完全二叉树。

如图所示，该树深度同样为 4，除第 4 层外节点数也达最大，但第 4 层节点未紧靠左侧（节点 E 无子节点，导致中间出现空位），因此这不是完全二叉树，仅为普通二叉树。

2. 满二叉树：所有叶节点均位于最底层的完全二叉树称为满二叉树。它是完全二叉树的特例，除满足完全二叉树特征外，还要求所有叶节点位于最底层。在相同深度的二叉树中，满二叉树的叶节点数量最多。

如图所示，该树首先是一棵完全二叉树，且所有叶节点均位于最底层，因此属于满二叉树。另一种定义方式是：若二叉树的所有层节点数均达到最大值，则称为满二叉树。

3. 平衡二叉树（AVL 树）：若二叉树中所有节点的左右子树高度差不大于 1，则该树被称为平衡二叉树。

如前文满二叉树示例，任意节点的左右子树高度差均为 0（高度相等，满足不大于 1 的条件），因此这是一棵平衡二叉树。

如图所示的二叉树，根节点 A 的左子树（以 B 为根）高度为 4，右子树（以 C 为根）高度为 2。A 节点左右子树高度差为 2（大于 1），因此这不是平衡二叉树。

AVL 树得名于其发明者 G. M. Adelson-Velsky 和 E. M. Landis 的姓氏缩写。AVL 树中任何节点的左右子树高度差不超过 1，通过高度判断平衡性，故又称高度平衡树。

4. 排序二叉树（二叉查找树，Binary Search Tree）：也称为二叉搜索树或有序二叉树。

排序二叉树需满足以下性质：

4.1 若左子树不为空，则左子树上所有节点的值均小于根节点的值。

4.2 若右子树不为空，则右子树上所有节点的值均大于根节点的值。

4.3 若独立观察，左子树和右子树本身也必须是排序二叉树。通过递归思想，直至处理到树的叶节点。

如图所示，根节点 8 的左子树中所有节点值均小于根节点，右子树中所有节点值均大于根节点，且左右子树本身也是排序二叉树，因此这是一棵排序二叉树。

5. 斜树：除叶节点外，所有节点仅拥有左子树的二叉树称为左斜树；除叶节点外，所有节点仅拥有右子树的二叉树称为右斜树。二者统称为斜树。判断斜树主要依据树的结构，对节点值无特定要求。

如图所示，左侧树中除叶节点 D 外，所有节点仅拥有左子树，为左斜树；右侧树同理为右斜树。

三、二叉树的特点和性质

基于对二叉树及其特殊类型的介绍，可总结出以下特点：

1. 每个节点最多有两颗子树，因此二叉树中节点的度不大于 2，二叉树的度也不会超过 2。

2. 左子树和右子树的次序不可颠倒，具有明确的左右之分。

3. 即使某节点仅有一棵子树，也必须根据左右位置区分其为左子树还是右子树。

此外，二叉树还具有以下数学性质：

1. 在二叉树的第 i 层，至多有 2^(i-1) 个节点（i>0）。

此处指最大可能数量。满二叉树的每一层节点均“挂满”，可通过满二叉树验证：第 1 层节点数为 2^(1-1)=1 个，... 第 4 层节点数最多为 2^(4-1)=8 个。

2. 深度为 i 的二叉树至多有 2^i - 1 个节点（k>0，此处指深度 i）。

同样指最大可能数量。以满二叉树验证，深度为 4 时，节点数最多为 2^4 - 1 = 16 - 1 = 15 个。

3. 对于任意一棵二叉树，若其叶节点数为 M，度为 2 的节点总数为 N，则满足关系式 M = N + 1。

为不失一般性，图中普通二叉树的叶节点为 F, H, I, J, K, L，共 6 个；度为 2 的节点为 A, B, C, D, G，共 5 个。验证可知 6 = 5 + 1，符合性质。

4. 具有 n 个节点的满二叉树的深度必为 log2(n+1)。此性质是上述第 2 点的逆运算。

5. 对于一棵完全二叉树，若从上至下、从左至右进行编号，则编号为 i 的节点（叶节点除外），其左子节点编号必为 2i，右子节点编号必为 2i+1；其父节点编号必为 i/2（取整除，根节点除外）。

如图所示，这是一棵已按规则编号的完全二叉树。任意选取一个节点进行验证，均符合上述性质。

到此这篇关于二叉树的概念案例详解的文章就介绍到这了，更多相关二叉树的概念内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！