《Python编程从0到1 视频教学版》_深入Python设计的本质_3.4 二叉树

【摘要】 本书摘自《Python编程从0到1 视频教学版》一书中第3章，第4节，作者是张頔。

3.4 二叉树

本书在2.4.4节中已经初步介绍了二叉树的概念，并给出了以递归方式②对其进行遍历 的方法。本节将进一步深入介绍这种应用广泛的数据结构。

二叉树有两种典型应用： 一是用来维护有序数据集(典型的结构是二叉搜索树和二叉 堆),以实现高效查找和排序；二是用来表示本身便具备二分属性的信息，如哈夫曼编码 (Huffman coding)。

【学习目标】

● 掌握二叉树的定义和属性；

· 了解搜索二叉树的应用；

· 了解二叉堆的应用；

· 了解二叉树相关Python 结构类型；

· 了解哈夫曼编码。

3.4.1 概念和定义

在2.4.4节中已经给出了二叉树的递归定义，要点如下：

· 二叉树根节点的左子树和右子树也是二叉树；

· 空集是二叉树。

二叉树的左子树和右子树顺序往往有特定意义，不能随意调换。比如搜索二叉树中左 子树节点均小于右子树节点的规则。如图3.27所示为一棵4层8个节点的二叉树。

二叉树有以下术语：

· 叶子节点：没有子节点的节点被称为叶子节点；

· 节点层数：根节点算第1层，其他节点的层数是其父节点层数加1;

· 树的层数(又称深度):节点的最大层次。

层数和叶子节点如图3.28所示。

有以下特殊的二叉树：

·满二叉树：每个节点要么有两个子节点，要么没有子节点，如图3.29所示。

·完全二叉树：除最后一层外，其他各层节点全满，最后一层的节点集中在左边，如 图3.30所示。

·完美二叉树：所有叶子节点都在同一层的满二叉树，如图3.31所示。

【思考和扩展练习】

(1)尝试给出满二叉树的递归定义。

(2)如果满二叉树的层数为h, 那么其至少有几个节点，至多有几个节点?

3.4.2 表示和存储

二叉树的典型存储方式是链式法，即在节点结构中包含左子节点和右子节点的引用。 也可以使用数组按照一定规律组织二叉树各节点的位置，常用于二叉堆的存储。

1. 链式法示例

使用三元列表，表示二叉树的一个节点，如图3.32所示。

整数节点构成的二叉树，如图3.33所示。

如下代码构建了图3.33所示的整数节点构成的二叉树。

>>> def tree(root, left=None, right=None):

return [root, left, right]

>>> tree(3,tree(1, tree(2),

tree(4)),

tree(5))

[3,[1,[2,None,None],[4,None,None]], [5,None,None

2. 数组法示例

可以使用数组存储二叉树。尤其是以按层遍历次序存储完全二叉树时，无须任何额外 空间，即可维护二叉树节点的相互关系。索引为i 的节点，左子节点为2i+1, 右子节点为 2i+2, 父节点为(i-1)//2°。 用数组存储完全二叉树，如图3.34所示。②

【思考和扩展练习】

( 1 ) 扩 展tree 函数，使之可以创建一般的树，如图3.35所示。

(2)友好地在文本界面打印二叉树，参考第三方模块 binarytree 的打印格式。用如下 命令安装 binarytree 模块：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 [email protected] 处理，核实后本网站将在24小时内删除侵权内容。