《数据结构Python 语言描述》 第6章

第6章树和二叉树签到扫码下载文旌课堂APP扫码签到（202X.X.XXXX:00至202X.X.XXXX:10）签到方式教师通过“文旌课堂APP”生成签到二维码，并设置签到时间，学生通过“文旌课堂APP”扫描“签到二维码”进行签到。。树和二叉树本章导读树形结构是一类重要的非线性结构，它在现实生活中的应用非常广泛，如家庭成员关系、企业组织机构等。在计算机领域中，树形结构在文件系统、目录组织、数据库系统等方面的应用更加突出。常用的树形结构有树和二叉树，其中二叉树是一种特殊的树。本章首先介绍树和二叉树的基础知识，然后介绍二叉树的存储结构，以及二叉树的遍历方法和线索二叉树，最后介绍哈夫曼树的构造方法和哈夫曼编码，以及树和森林的相关知识。

第6章树和二叉树知识目标

第6章 理解树的定义、基本术语和基本操作。 理解二叉树的定义、基本操作和性质。 掌握二叉树的两种存储结构。 掌握二叉树的遍历方法，以及线索二叉树的线索化。 掌握哈夫曼树的构造方法及哈夫曼编码。 掌握树的存储结构，以及树、森林和二叉树的转换方法。 掌握树和森林的遍历方法。树和二叉树技能目标

第6章 能根据先序、中序和后序遍历方法快速得到二叉树的遍历序列。 能利用哈夫曼树解决编码问题。树和二叉树素质目标

第6章 增强自主学习、协作学习、探究学习的意识。 培养勇于探索、知难而进、追求卓越的创新精神。Content第6章二叉树概述树概述遍历二叉树和线索二叉树哈夫曼树树和森林6.1树概述第6章树和二叉树6.1树概述6.1.1树的定义树（tree）是n（n≥0）个结点的有限集合，当n=0时称为空树。任意一棵非空树T均满足如下条件。（1）有且只有一个称为根（root）的结点，它无前驱结点。（2）当n＞1时，除根结点外的其余n-1个结点可以分为m（m＞0）个互不相交的有限集合T1、T2、…、Tm，其中每个集合Ti（1≤i≤m）本身又是一棵树，称为根结点的子树（subtree）。6.1.2树的基本术语树的基本术语如表6-1所示。6.1.3树的基本操作树基本操作的定义如表6-2所示。6.1树概述术

语说明示

例结点包含一个数据元素及若干指向其子树的分支图6-1中的A、B、C、D等结点的度结点的子树个数称为结点的度图6-1中，结点A的度是3，结点B的度是2树的度所有结点的度的最大值称为树的度图6-1中，树的度是3（树中结点A的度是3，是最大的）叶子结点度为0的结点，即无后继结点的结点，也称为终端结点图6-1中，结点J、F、G、K、I均为叶子结点分支结点度不为0的结点（根结点除外），也称为非终端结点或非叶子结点图6-1中，结点B、E、C、D、H均为分支结点孩子结点和双亲结点结点的子树的根结点称为该结点的孩子结点，该结点是其孩子结点的双亲结点图6-1中，结点B、C、D是结点A的孩子结点，结点A是结点B、C、D的双亲结点兄弟结点同一双亲结点的孩子结点之间互称为兄弟结点图6-1中，结点B、C、D之间互称为兄弟结点祖先结点从根结点到该结点所经分支上的所有结点称为该结点的祖先结点图6-1中，结点J的祖先结点是结点A、B、E子孙结点以某个结点为根结点的子树中的任意结点都称为该结点的子孙结点图6-1中，结点B的子孙结点是结点E、F、J结点的层次从根结点开始定义，根结点的层次为1，根结点的孩子结点的层次为2，以此类推（任一结点的层次等于其双亲结点的层次加1）图6-1中，结点H的层次是3，结点K的层次是4树的深度所有结点的层次的最大值称为树的深度，也称为树的高度图6-1中，树的深度（高度）是4有序树和无序树树中结点的各子树从左到右有次序（不能互换）的树称为有序树，否则称为无序树图6-1中，结点B、C、D不能互换，则该树为有序树森林m（m≥0）棵互不相交的树的集合称为森林，将一棵非空树的根结点删除，该树剩余的子树就变成了森林图6-1中，将根结点A删除，剩余的子树就变成了森林表6-1树的基本术语6.1树概述表6-2树基本操作的定义基本操作说明__init__()初始化树，即构造一棵空树createTree()创建树treeEmpty()若树为空，则返回True，否则返回FalsetreeDepth()返回树的深度（高度）root()返回树的根结点parent(e)已知树存在，e是树中的某个结点，若e为非根结点，则返回它的双亲结点，否则返回NoneleftChild(e)已知树存在，e是树中的某个结点，若e为非叶子结点，则返回它的左孩子结点，否则返回NonerightSibling(e)已知树存在，e是树中的某个结点，若e有右兄弟结点，则返回它的右兄弟结点，否则返回NoneinsertChild(p,i,C)已知树存在，将C作为p所指结点的第i棵子树插入树中deleteChild(p,i)已知树存在，删除树中p所指结点的第i棵子树traverseTree()已知树存在，按照某种次序访问树的每个结点，且每个结点仅访问一次6.1树概述例如，李奶奶（用A表示）有3个孩子B、C、D；孩子B有两个孩子E和F；孩子C有一个孩子G；孩子D有两个孩子H和I；孙子E有一个孩子J；孙子H有一个孩子K。那么，该家庭成员关系（各成员的排列顺序有先后次序，即按年龄逐渐递减）可以用一棵树来表示，如下图所示。6.1树概述由上图可以看出，这是一棵具有11个结点的树，即T={A,B,C,…,J,K}。其中，A是根结点，其余10个结点可以分为3个互不相交的集合，分别是T1={B,E,F,J}、T2={C,G}、T3={D,H,I,K}。T1、T2、T3本身也是一棵树，且都称为根结点A的子树。T1的根结点为B，其余3个结点可以分为两个互不相交的集合，分别是T11={E,J}、T12={F}。T11和T12本身也是一棵树（T12只有根结点），且都称为根结点B的子树。T11的根结点为E，其余结点{J}本身是一棵只有根结点的树，称为根结点E的子树。6.1树概述提示T2和T3也是根结点A的子树，其分析方法与T1相同，此处不再赘述。感兴趣的读者可自行分析子树T2和T3。由此可见，树的定义是递归的。树具有如下两个特点。（1）除根结点外，其余结点有且只有一个前驱结点。（2）每个结点都可以有若干后继结点。6.1树概述树的表示方法除了树形表示法（见下图）外，还有文氏图表示法、凹入表示法和广义表表示法等。（1）文氏图表示法是以嵌套集合的形式表示树。每棵树对应一个集合，集合内包含根结点和子树的集合，同一个根结点下的各子树对应的集合是不能相交的。（2）凹入表示法是以类似图书目录的形式表示树。每棵树的根结点对应一个条形，子树的根结点对应较短的条形，且树的根结点在上，子树的根结点在下。同一个根结点下的不同子树的根结点对应的条形长度相同。（3）广义表表示法是将根结点作为由所有子树组成的表的名字写在表的左边。6.2二叉树概述第6章树和二叉树6.2二叉树概述6.2.1二叉树的定义1．二叉树二叉树是n（n≥0）个结点的有限集合，当n=0时称为空二叉树。任意一棵非空二叉树T均满足如下条件。（1）有且只有一个称为根（root）的结点，它无前驱结点。（2）当n＞1时，除根结点外的其余n-1个结点可以分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，其中T1和T2本身也是二叉树。6.2二叉树概述二叉树的基本形态有5种，如下图所示。（1）空二叉树，即二叉树有0个结点。（2）单结点二叉树，即二叉树只有一个根结点。（3）右子树为空的二叉树，即二叉树只有左子树。（4）左子树为空的二叉树，即二叉树只有右子树。（5）左、右子树均不为空的二叉树，即二叉树既有左子树又有右子树。6.2二叉树概述提示二叉树的基本术语，如结点的度、叶子结点、孩子结点、双亲结点等与树中的概念相同，此处不再赘述。非空二叉树中的任意一个结点只可以有0、1或2个孩子结点，即二叉树中不存在度大于2的结点。6.2二叉树概述2．满二叉树在一棵二叉树中，如果所有非叶子结点都有左子树和右子树，并且所有叶子结点都在二叉树的最后一层，则称该二叉树为满二叉树。例如，下图是一棵深度为4的满二叉树，其中的各结点从根结点起，按从上到下、同一层从左到右的顺序进行连续编号。由上图可以看出，深度为4的满二叉树共有24-1=15个结点。由此可知，满二叉树也可以这样定义，即一棵深度为h且有2h-1个结点的二叉树称为满二叉树。6.2二叉树概述3．完全二叉树在一棵二叉树中，如果其所有结点所在位置的编号分别与同深度的满二叉树相应位置的结点编号一一对应，则称该二叉树为完全二叉树，如下图所示。6.2二叉树概述由上图可以看出，深度为4的完全二叉树，前3层共有23-1=7个结点，且第4层的结点从左到右连续排列。由此可知，完全二叉树也可以这样定义，即一棵深度为h的二叉树，除第h层外，其余各层（1～h-1）的结点数都达到最大值，且第h层的结点从左到右连续排列。下图的二叉树不满足完全二叉树的定义，故属于非完全二叉树。综上所述，满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。6.2二叉树概述6.2.2二叉树的性质二叉树具有如下5个性质。（1）性质1：对于任何一棵非空二叉树T，若叶子结点数为n0，度为2的结点数为n2，则

n0=n2+1。

6.2二叉树概述（2）性质2：二叉树的第i（i≥1）层最多有2i－1个结点。证明：该性质可以使用数学归纳法证明。①

当i=1时，二叉树只有一个根结点，显然2i－1=20=1成立。②

假设对所有的k（1≤k＜i）结论成立，即第k层最多有2k－1个结点。③

由归纳假设，由于二叉树的每个结点的度最大为2，故第k+1层的结点数最多为第k层最大结点数的2倍，即2×2k－1=2(k＋1)－1，故结论成立（3）性质3：深度为h（h≥1）的二叉树最多有2h-1个结点。

6.2二叉树概述（4）性质4：具有n个结点的完全二叉树的深度为「log2n」+1。（

「log2n」表示小于等于

的最大整数）

（5）性质5：对于具有n个结点的完全二叉树，按照从上到下、同一层从左到右的顺序对其所有结点进行连续编号，则结点i（1≤i≤n）具有如下特点。①若i=1，则该结点是根结点，无双亲结点；若i＞1，则该结点的双亲结点为。（表示小于等于i/2的最大整数）②若2i＞n，则该结点无左孩子结点；若2i≤n，则该结点的左孩子结点为2i。③若2i+1＞n，则该结点无右孩子结点；若2i+1≤n，则该结点的右孩子结点为2i+1。6.2二叉树概述6.2.3二叉树的基本操作二叉树基本操作的定义如表6-3所示。基本操作说明__init__()初始化二叉树，即构造一棵空二叉树createBTree()创建二叉树btreeEmpty()若二叉树为空，则返回True，否则返回FalsebtreeDepth()返回二叉树的深度root()返回二叉树的根结点parent(e)已知二叉树存在，e是二叉树中的某个结点，若e为非根结点，则返回它的双亲结点，否则返回NoneleftChild(e)已知二叉树存在，e是二叉树中的某个结点，若e为非叶子结点，则返回它的左孩子结点，否则返回NonerightChild(e)已知二叉树存在，e是二叉树中的某个结点，若e为非叶子结点，则返回它的右孩子结点，否则返回NoneinsertChild(p,LR,C)已知二叉树存在，p指向二叉树中的某个结点，非空二叉树C与该二叉树不相交且右子树为空。根据LR为0或1，将C作为p所指结点的左子树或右子树插入二叉树中，p所指结点的原左子树或右子树将成为C的右子树deleteChild(p,LR)已知二叉树存在，p指向二叉树中的某个结点。根据LR为0或1，删除二叉树中p所指结点的左子树或右子树preOrderTraverse()已知二叉树存在，先序遍历二叉树inOrderTraverse()已知二叉树存在，中序遍历二叉树postOrderTraverse()已知二叉树存在，后序遍历二叉树levelOrderTraverse()已知二叉树存在，层次遍历二叉树表6-3二叉树基本操作的定义6.2二叉树概述6.2.4二叉树的存储结构二叉树是一种非线性结构，其存储结构有顺序存储和链式存储两种。1．二叉树的顺序存储二叉树的顺序存储是指用一组地址连续的存储单元存储二叉树中的结点，通常用一维数组来描述。为了在存储结构中反映出二叉树中各结点之间的逻辑关系，须将二叉树中的结点值按照一定的规律存储到一维数组中。6.2二叉树概述对于满二叉树和完全二叉树，由性质5可知，结点的层序编号可以唯一反映结点之间的逻辑关系。因此，可以按照层序编号将二叉树中的所有结点值顺序存储到一维数组中，即二叉树编号为i的结点值存储到一维数组中下标为i-1的单元中。而对于普通二叉树，如果仍然按照从上到下、同一层从左到右的顺序依次将结点值存储到一维数组中，则无法反映出二叉树中各结点之间的逻辑关系。因此，对于普通二叉树，必须先将其补全为完全二叉树，然后再按照完全二叉树的形式进行存储。也就是说，将普通二叉树中的每个结点与完全二叉树中的结点相对应，同时将普通二叉树中不存在的结点位置用“0”填充。综上所述，满二叉树和完全二叉树更适合采用顺序存储结构，这样既能节省存储空间，又能利用数组下标确定结点在二叉树中的位置及结点之间的逻辑关系。对于普通二叉树，在其形态与完全二叉树非常相似的情况下，也可以采用顺序存储结构，否则建议采用链式存储结构。6.2二叉树概述2．二叉树的链式存储二叉树的链式存储是指用链表存储二叉树。在二叉树的链式存储结构中，每个结点由3个域组成，其结构如下图所示。其中，左子树域（lchild）用于存储左孩子结点的地址；数据域（data）用于存储结点的数据信息；右子树域（rchild）用于存储右孩子结点的地址。二叉树的链式存储结构中结点的定义如下。6.2二叉树概述classBTNode: #二叉树结点类

def__init__(self,data): #构造方法

self.data=data #data域

self.lchild=None #lchild域

self.rchild=None #rchild域采用以上结点结构形成的二叉树的链式存储结构称为二叉链表，链表的头指针指向二叉树的根结点。例如，二叉树对应的二叉链表如下图所示。6.2二叉树概述在二叉链表中，查找结点的孩子结点的操作很容易实现，但要查找其双亲结点必须从根结点开始查找。为了便于找到结点的双亲结点，可以在每个结点中增加一个指向其双亲结点的指针域parent，其结构如下图所示。6.2二叉树概述采用这种结点结构形成的二叉树的链式存储结构称为三叉链表。二叉树对应的三叉链表如下图所示。6.3遍历二叉树和线索二叉树第6章树和二叉树6.3遍历二叉树和线索二叉树遍历二叉树是指按照一定的次序访问二叉树中的所有结点，且每个结点仅被访问一次。由二叉树的定义可知，任意一棵非空二叉树均由根结点、左子树和右子树三部分组成，因此，只要遍历这三部分就能遍历整棵二叉树。二叉树的遍历方法有4种，分别为先序遍历、中序遍历、后序遍历和层次遍历。6.3.1遍历二叉树1．先序遍历对于非空二叉树，先序遍历的递归算法步骤如下。（1）访问根结点。（2）先序遍历根结点的左子树。（3）先序遍历根结点的右子树。6.3遍历二叉树和线索二叉树【算法描述】defpreOrderTraverse(self,node):ifnodeisnotNone: #结点不为空

print(node.data,end='') #访问根结点

self.preOrderTraverse(node.lchild) #先序遍历根结点的左子树

self.preOrderTraverse(node.rchild) #先序遍历根结点的右子树例如，若按照先序遍历方法进行遍历，二叉树遍历顺序如下图所示。6.3遍历二叉树和线索二叉树下面具体分析上图中先序遍历二叉树的具体过程。（1）先访问根结点A，再遍历其左子树和右子树。（2）遍历根结点A的左子树，也就是遍历以B为根结点的二叉树。因此，按照先序遍历步骤，先访问根结点B，再遍历其左子树和右子树。（3）遍历根结点B的左子树，也就是遍历以D为根结点的二叉树。因此，按照先序遍历步骤，先访问根结点D，再遍历其左子树和右子树。6.3遍历二叉树和线索二叉树（4）由于根结点D的左子树为空，因此根结点D的左子树遍历结束，返回到根结点D。（5）遍历根结点D的右子树，也就是遍历以G为根结点的二叉树。因此，按照先序遍历步骤，先访问根结点G，再遍历其左子树和右子树。（6）由于根结点G的左子树和右子树均为空，因此以G为根结点的二叉树遍历结束，返回到根结点D。（7）至此，以D为根结点的二叉树遍历结束，即根结点B的左子树遍历结束，返回到根结点B。（8）遍历根结点B的右子树，也就是遍历以E为根结点的二叉树。因此，按照先序遍历步骤，先访问根结点E，再遍历其左子树和右子树。（9）遍历根结点E的左子树，也就是遍历以H为根结点的二叉树。因此，按照先序遍历步骤，先访问根结点H，再遍历其左子树和右子树。（10）由于根结点H的左子树和右子树均为空，因此以H为根结点的二叉树遍历结束，即根结点E的左子树遍历结束，返回到根结点E。6.3遍历二叉树和线索二叉树（11）由于根结点E的右子树为空，因此以E为根结点的二叉树遍历结束。（12）至此，以B为根结点的二叉树遍历结束，即根结点A的左子树遍历结束，返回到根结点A。（13）遍历根结点A的右子树，也就是遍历以C为根结点的二叉树。因此，按照先序遍历步骤，先访问根结点C，再遍历其左子树和右子树。（14）由于根结点C的左子树为空，因此根结点C的左子树遍历结束，返回到根结点C。（15）遍历根结点C的右子树，也就是遍历以F为根结点的二叉树。因此，按照先序遍历步骤，先访问根结点F，再遍历其左子树和右子树。（16）由于根结点F的左子树和右子树均为空，因此以F为根结点的二叉树遍历结束，返回到根结点C。（17）至此，以C为根结点的二叉树遍历结束，即根结点A的右子树遍历结束，返回到根结点A。（18）至此，以A为根结点的二叉树遍历结束，可得二叉树的先序遍历序列为A、B、D、G、E、H、C、F。6.3遍历二叉树和线索二叉树2．中序遍历对于非空二叉树，中序遍历的递归算法步骤如下。（1）中序遍历根结点的左子树。（2）访问根结点。（3）中序遍历根结点的右子树。【算法描述】definOrderTraverse(self,node):ifnodeisnotNone: #结点不为空

self.inOrderTraverse(node.lchild) #中序遍历根结点的左子树

print(node.data,end='') #访问根结点

self.inOrderTraverse(node.rchild) #中序遍历根结点的右子树6.3遍历二叉树和线索二叉树例如，若按照中序遍历方法进行遍历，二叉树的中序遍历序列为D、G、B、H、E、A、C、F，如下图所示。6.3遍历二叉树和线索二叉树3．后序遍历对于非空二叉树，后序遍历的递归算法步骤如下。（1）后序遍历根结点的左子树。（2）后序遍历根结点的右子树。（3）访问根结点。【算法描述】defpostOrderTraverse(self,node):ifnodeisnotNone: #结点不为空

self.postOrderTraverse(node.lchild) #后序遍历根结点的左子树

self.postOrderTraverse(node.rchild) #后序遍历根结点的右子树

print(node.data,end='') #访问根结点6.3遍历二叉树和线索二叉树例如，若按照中序遍历方法进行遍历，二叉树的中序遍历序列为G、D、H、E、B、F、C、A，如下图所示。6.3遍历二叉树和线索二叉树4．层次遍历对于非空二叉树，层次遍历的算法步骤如下。（1）访问根结点（第1层）。（2）从左到右依次访问第2层的所有结点。（3）从左到右依次访问第3层的所有结点、……、第h层的所有结点。【算法描述】deflevelOrderTraverse(self):ifself.rootisnotNone: #结点不为空

queue=[self.root] #当前层结点

whilequeue: #当前层存在结点时6.3遍历二叉树和线索二叉树

cur_node=queue.pop(0) #处理每一层结点

print(cur_node.elem,end='')ifcur_node.lchildisnotNone: #左孩子结点不为空

queue.append(cur_node.lchild) #访问左孩子结点

ifcur_node.rchildisnotNone: #右孩子结点不为空

queue.append(cur_node.rchild) #访问右孩子结点例如，若按照中序遍历方法进行遍历，二叉树的中序遍历序列为A、B、C、D、E、F、G、H，如下图所示。6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树假设一棵二叉树的结点值均不相同，则可以根据不同的遍历方法得到不同的遍历序列；相反，若已知二叉树的遍历序列，也可以唯一确定一棵二叉树。由二叉树的先序遍历序列和中序遍历序列，或由二叉树的后序遍历序列和中序遍历序列，均可以唯一确定一棵二叉树。6.3.2确定二叉树1．由先序和中序遍历序列确定二叉树由先序和中序遍历序列确定二叉树的过程如下。6.3遍历二叉树和线索二叉树（1）根据二叉树的先序遍历步骤可知，在先序遍历序列中，第一个结点一定是二叉树的根结点。（2）根据二叉树的中序遍历步骤可知，根结点（先序遍历序列的第一个结点）会将中序遍历序列分为两个子序列，第一个子序列（左中序）是根结点的左子树的中序遍历序列，第二个子序列（右中序）是根结点的右子树的中序遍历序列。根据这两个子序列，可以在先序遍历序列中找到对应的左子序列（左先序）和右子序列（右先序）。（3）在先序遍历序列中，左子序列（左先序）的第一个结点是左子树的根结点，右子序列（右先序）的第一个结点是右子树的根结点。至此，就确定了根结点、左子树根结点和右子树根结点。（4）根据得到的左子树和右子树的根结点，重复上述步骤。按照这样的方式进行递归，当所有结点都取完时，即可确定二叉树。例如，已知二叉树的先序遍历序列为C、A、B、G、H、E、D、F，中序遍历序列为G、H、B、A、C、D、E、F，后序遍历序列为H、G、B、A、D、F、E、C。6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树2．由后序和中序遍历序列确定二叉树由后序和中序遍历序列确定二叉树的过程如下。（1）根据二叉树的后序遍历步骤可知，在后序遍历序列中，最后一个结点一定是二叉树的根结点。（2）根据二叉树的中序遍历步骤可知，根结点（后序遍历序列的最后一个结点）会将中序遍历序列分为两个子序列，第一个子序列（左中序）是根结点的左子树的中序遍历序列，第二个子序列（右中序）是根结点的右子树的中序遍历序列。根据这两个子序列，可以在后序遍历序列中找到对应的左子序列（左后序）和右子序列（右后序）。（3）在后序遍历序列中，左子序列（左后序）的最后一个结点是左子树的根结点，右子序列（右后序）的最后一个结点是右子树的根结点。这样，就确定了根结点、左子树根结点和右子树根结点。（4）根据得到的左子树根结点和右子树根结点，重复上述步骤。按照这样的方式进行递归，当所有结点都取完时，即可确定二叉树。6.3遍历二叉树和线索二叉树例如，已知二叉树的后序遍历序列为H、G、B、A、D、F、E、C，中序遍历序列为G、H、B、A、C、D、E、F，则确定二叉树的过程如下图所示，该二叉树的先序遍历序列为C、A、B、G、H、E、D、F。6.3遍历二叉树和线索二叉树6.3.3线索二叉树1．线索二叉树的定义遍历二叉树是将二叉树中的结点按一定规律线性化的过程，它可以使得每个结点（除第一个结点和最后一个结点外）在线性序列中有且只有一个前驱结点和后继结点。但是，在二叉树的二叉链表存储结构中，只存储了结点的数据信息和其左、右孩子结点信息，并不能直接从中得到结点在线性序列中的前驱结点和后继结点信息。为此，可采用的方法是利用二叉链表中的空指针域来存放遍历过程中结点的前驱结点和后继结点信息。6.3遍历二叉树和线索二叉树对于具有n个结点的二叉树，其二叉链表中有2n个指针域，由于只有n-1个结点被指针所指向（n个结点中只有根结点无指针指向），则必有2n

-(n-1)=n+1个空指针域。因此，可利用这n+1个空指针域存放该结点的前驱结点和后继结点信息，其余n-1个指针域仍然存放该结点的左孩子结点和右孩子结点信息。为区分指针域中是孩子结点还是前驱结点或后继结点，须在每个结点中增加两个标志域（ltag和rtag），其结构如下图所示。6.3遍历二叉树和线索二叉树其中，ltag和rtag的具体含义如下。（1）ltag为0时，表示lchild域指向结点的左孩子结点；ltag为1时，表示lchild域指向结点的前驱结点。（2）rtag为0时，表示rchild域指向结点的右孩子结点；rtag为1时，表示rchild域指向结点的后继结点。在这种存储结构中，指向前驱结点和后继结点的指针称为线索，加了线索的二叉树称为线索二叉树，对二叉树按照某种方法进行遍历并加上线索的过程称为线索化。线索二叉树的链式存储中结点的定义如下。6.3遍历二叉树和线索二叉树classTHNode: def__init__(self,data): #构造方法

self.data=data #data域

self.lchild=None #lchild域

self.rchild=None #rchild域

self.ltag=0 #ltag域

self.rtag=0 #rtag域6.3遍历二叉树和线索二叉树2．二叉树的线索化二叉树的线索化实际上就是在进行某种遍历时，将二叉链表中的空指针域修改为指向相应结点的前驱结点或后继结点的过程。对二叉树按照不同的遍历方法进行线索化，可以得到不同的线索二叉树。提示二叉树在进行线索化时，须注意3点：一是确定二叉树的遍历次序；二是确定需要前驱线索化、后继线索化还是两者皆有；三是只有空指针才能加线索。6.3遍历二叉树和线索二叉树为方便操作，须在线索二叉树中增加一个头结点，头结点的data域为空，lchild域指向二叉树的根结点，ltag为0；rchild域指向遍历序列的尾结点，rtag为1。同时，令二叉树遍历序列中第一个结点的lchild域和最后一个结点的rchild域均指向头结点。下面以中序线索二叉树为例，画出与其对应的中序线索链表，如下图所示。6.3遍历二叉树和线索二叉树3．遍历线索二叉树在线索二叉树中，查找结点的前驱结点或后继结点非常简单。以中序线索二叉树为例，遍历线索二叉树的过程如下。（1）求中序遍历序列的开始结点，即根结点的最左下结点。（2）如果一个结点p的rchild指针为线索，则rchild所指向的就是该结点的后继结点，否则该结点的后继结点就是其右子树的最左下结点。【算法描述】defin_OrderThread(self,node): #遍历中序线索二叉树

ifnodeisnotNone:p=nodewhilep:whilep.ltag==0: #找中序遍历序列的开始结点

p=p.lchild print(p.data,end='') #访问结点

whilep.rchildisnotself.rootandp.rtag==1: #如果是线索，则rchild所指向的就是其后继结点

p=p.rchild print(p.data,end='') #访问结点

p=p.rchild #如果不是线索，则查找其右子树最左下结点同步训练利用二叉树求解表达式的值【问题描述】给定一个四则运算表达式，设计算法求解它的值。【问题分析】一般情况下，一个四则运算表达式由一个操作符和两个操作数构成，两个操作数之间有先后次序，并且操作数本身也可以是四则运算表达式。该结构与二叉树类似，因此可以利用二叉树表示四则运算表达式，即创建表达式解析树，然后再计算它的值。表达式解析树的递归定义如下。（1）若四则运算表达式只有数值，那么相应二叉树中仅有一个根结点，且根结点的数据域存放四则运算表达式的值。（2）若四则运算表达式的形式为“第一操作数—操作符—第二操作数”，则相应二叉树中以左子树表示第一操作数，以右子树表示第二操作数，根结点的数据域存放操作符。若操作数本身又是四则运算表达式，则以同样的规则继续划分子树。同步训练利用二叉树求解表达式的值创建表达式解析树应遵循如下规则。（1）如果当前字符是“(”，则为当前结点添加一个新结点作为其左孩子结点，且将当前结点下降为该新结点。（2）如果当前字符是操作符“+”“-”“*”“/”之一，则将当前结点的值设置为该操作符，并为当前结点添加一个新结点作为其右孩子结点，且将当前结点下降为该新结点。（3）如果当前字符是操作数，则将当前结点的值设置为该操作数，且将当前结点上升为双亲结点。（4）如果当前字符是“)”，则将当前结点上升为双亲结点。综上所述，四则运算表达式“(((15-3)*(18+9))/4)”的解析树如右图所示。同步训练利用二叉树求解表达式的值【代码实现】importoperator #Python中内置的操作符函数接口

classStack: #栈

def__init__(self):self.items=[]defpush(self,item): #进栈

self.items.append(item)defpop(self): #出栈根据创建的表达式解析树，可以从二叉树的最后一层开始，逐步向上层计算，最终即可得到四则运算表达式的值。同步训练利用二叉树求解表达式的值returnself.items.pop()classBinaryTree: #二叉树

def__init__(self,data): #构造方法

self.data=data #data域

self.lchild=None #lchild域

self.rchild=None #rchild域

definsertLeft(self,newNode):'''插入左孩子结点'''ifself.lchildisNone:self.lchild=BinaryTree(newNode)同步训练利用二叉树求解表达式的值else:t=BinaryTree(newNode)t.lchild=self.lchildself.lchild=tdefinsertRight(self,newNode):'''插入右孩子结点'''ifself.rchildisNone:self.rchild=BinaryTree(newNode)else:t=BinaryTree(newNode)t.rchild=self.rchild同步训练利用二叉树求解表达式的值self.rchild=tdefleftChild(self): #返回当前结点的左孩子结点

returnself.lchilddefrightChild(self): #返回当前结点的右孩子结点

returnself.rchilddefsetRootVal(self,obj): #设置根结点的值

self.data=objdefgetRootVal(self): #获取当前结点的值

returnself.datadefbuildParseTree(fpexp): #创建表达式解析树

fplist=fpexp.split() #创建单词列表同步训练利用二叉树求解表达式的值pStack=Stack() #使用栈保存双亲结点

eTree=BinaryTree('')pStack.push(eTree) #将根结点进栈

currentTree=eTree #当前结点下降为新创建的结点

foriinfplist: #从左到右扫描表达式的各个字符

ifi=='(': #左括号

currentTree.insertLeft('') #创建当前结点的左孩子结点

pStack.push(currentTree) #进栈

#当前结点下降为左孩子结点

currentTree=currentTree.leftChild()elifinotin'+-*/)': #操作数同步训练利用二叉树求解表达式的值

#将当前结点的值设置为该操作数

currentTree.setRootVal(eval(i)) parent=pStack.pop() #出栈

currentTree=parent #当前结点上升为双亲结点

elifiin'+-*/': #操作符

#将当前结点的值设置为该操作符

currentTree.setRootVal(i)currentTree.insertRight('') #创建当前结点的右孩子结点

pStack.push(currentTree) #进栈

#当前结点下降为右孩子结点

currentTree=currentTree.rightChild()同步训练利用二叉树求解表达式的值elifi==')': #右括号

#出栈，当前结点上升为双亲结点

currentTree=pStack.pop()returneTree #返回解析树

defevaluate(parseTree): #计算四则运算表达式的值

'''构建运算操作字典'''opers={'+':operator.add,'-':operator.sub,'*':operator.mul,同步训练利用二叉树求解表达式的值'/':operator.truediv}leftC=parseTree.leftChild() #左孩子结点

rightC=parseTree.rightChild() #右孩子结点

#如果左孩子结点和右孩子结点存在，则没有到达解析树的最后一层，须继续递归

ifleftCandrightC:fn=opers[parseTree.getRootVal()] #获取操作符

returnfn(evaluate(leftC),evaluate(rightC)) #递归调用

#如果左孩子结点和右孩子结点不存在，说明到达了解析树的最后一层，结束递归同步训练利用二叉树求解表达式的值else:returnparseTree.getRootVal()'''四则运算表达式'''formulas='(((15-3)*(18+9))/4)'formulas1='((9+((3-1)*3)))+(10/2)''''调用创建表达式解析树的函数'''eTree=buildParseTree(formulas)eTree1=buildParseTree(formulas1)'''调用计算四则运算表达式值的函数'''value=evaluate(eTree)同步训练利用二叉树求解表达式的值value1=evaluate(eTree1)'''输出四则运算表达式的值'''print('四则运算表达式%s的值为'%formulas,value)print('四则运算表达式%s的值为'%formulas1,value1)【程序测试】程序运行结果如下图所示。6.4哈夫曼树第6章树和二叉树6.4哈夫曼树哈夫曼树是一种特殊的二叉树。在介绍它的定义之前，首先了解如下基本术语。6.4.1哈夫曼树的定义（1）路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。（2）路径长度：从树中一个结点到另一个结点所经过的分支数目。（3）树的路径长度：从树的根结点到树中所有结点的路径长度之和。（4）结点的权：在实际应用中，人们为树的每个结点赋予的一个具有某种实际意义的数值称为该结点的权。（5）结点的带权路径长度：从树的根结点到该结点之间的路径长度与该结点的权的乘积。

6.4哈夫曼树哈夫曼树的构造方法如下。6.4.2哈夫曼树的构造（1）用给定的n个权值{w1,w2,…,wn}对应n个结点，构成具有n棵二叉树的森林F={T1,T2,…,Tn}，其中每棵二叉树Tn只有一个权为wn的根结点，其左、右子树均为空。（2）从森林中选取两棵根结点权值最小的二叉树，分别作为左、右子树构造一棵新的二叉树，且新的二叉树的根结点的权值为其左、右子树根结点的权值之和。（3）从森林中删除（2）中选取的两棵二叉树，并把新构成的二叉树加入森林中。（4）重复（2）和（3）的操作，直到森林中只含有一棵二叉树，这棵二叉树即为哈夫曼树。6.4哈夫曼树提示在构造哈夫曼树的过程中，两棵二叉树作为根结点的左、右子树是任意的，因此构造出来的哈夫曼树可能不是唯一的，但是其带权路径长度一定是相同的。6.4哈夫曼树哈夫曼树被广泛地应用在各种技术中，其中最典型的就是在编码技术上的应用。利用哈夫曼树，可以在保证数据量不变的情况下，得到平均长度最短的编码。因此，哈夫曼编码技术在数据压缩技术中具有重要作用。为防止编码有二义性，要求每一个字符的编码都不能是另一个字符编码的前缀，这种编码称为前缀编码。利用哈夫曼树可以设计出最优的前缀编码，具体方法如下。6.4.3哈夫曼编码（1）以每个字符的出现频率为权值构造一棵哈夫曼树。（2）将哈夫曼树中的每一条左分支标记为0，每一条右分支标记为1。（3）从根结点到每个叶子结点所经过的路径分支组成的0和1的序列构成了该结点对应字符的编码，这个编码称为哈夫曼编码。6.4哈夫曼树例如，不同字符及其出现频率所对应的哈夫曼编码如下图所示。

6.5树和森林第6章树和二叉树6.5树和森林树的存储结构有3种，包括双亲表示法、孩子表示法和孩子兄弟表示法。6.5.1树的存储结构1．双亲表示法双亲表示法是用一组连续的存储空间来存储树中的结点，结点的存储顺序为从上到下、同一层从左到右。在每个结点中设置一个指针parent，用于指示其双亲结点的位置，其结构如下图所示。6.5树和森林其中，data域用于存储结点的数据信息；parent域用于存储其双亲结点的地址。由于根结点没有双亲结点，故将其parent域设置为-1。双亲表示法结点的定义如下。classNode: def__init__(self,data,parent): self.data=data #data域

self.parent=parent #parent域6.5树和森林例如，下图为一棵树及其双亲表示的存储结构。双亲表示法利用了树的每个结点（根结点除外）只有唯一双亲结点的性质，在这种存储结构中，求某个结点的双亲结点非常容易，但是求某个结点的孩子结点则需要遍历整棵树。高手点拨2.2线性表的顺序存储——顺序表6.5树和森林2．孩子表示法孩子表示法是将树中每个结点的孩子结点排列起来，构成一个线性表。由于每个结点的孩子结点个数不确定，所以通常采用单链表作为存储结构，称为孩子链表。n个结点即有n个孩子链表（叶子结点的孩子链表为空表）。孩子表示法中包含两种结点，一种是表头数组的表头结点，也就是双亲结点，另一种是孩子链表的孩子结点。6.5树和森林其中，表头结点的data域用于存储结点的数据信息；firstchild域用于存储该结点的孩子链表的头指针。孩子结点的child域用于存储结点在表头数组中的位置；next域用于存储指向表头结点的下一个孩子结点的地址。孩子表示法表头结点的定义如下。classPNode:

def__init__(self,data): self.data=data #data域

self.firstchild=None #firstchild域6.5树和森林孩子表示法孩子结点的定义如下。classCNode:

def__init__(self,child): self.child=child #child域

self.next=None #next域提示孩子表示法便于查找树中结点的孩子结点。若将双亲表示法和孩子表示法结合起来，那么实现树的各种操作都将变得非常容易。6.5树和森林3．孩子兄弟表示法孩子兄弟表示法又称二叉链表表示法，即以二叉链表作为树的存储结构。二叉链表中的每个结点由3个域组成，其结构如下图所示。其中，firstchild域用于存储结点的第一个孩子结点的地址；data域用于存储结点的数据信息；rightsib域用于存储结点的右兄弟结点。孩子兄弟表示法结点的定义如下。6.5树和森林孩子兄弟表示法结点的定义如下。classNode: def__init__(self,data): self.data=data #data域

self.firstchild=None #firstchild域

self.rightsib=None #rightsib域例如，下图为一棵树及其孩子兄弟表示的存储结构。6.5树和森林6.5树和森林6.5.2树、森林和二叉树的转换1．树转换为二叉树将一棵树转换为二叉树的步骤如下。（1）加线：在树中的兄弟结点之间加一条连线。（2）抹线：对树中的每个结点，除了其最左孩子结点外，抹掉其与其他孩子结点之间的“双亲—孩子”关系的连线。（3）旋转：以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。将一棵树转换为二叉树的加线过程，就是将树中的兄弟关系转换为二叉树中的“双亲—右孩子”关系。通过以上转换可以看出，树中任意一个结点都对应于二叉树中的一个结点。树中某个结点的第一个孩子结点在二叉树中是相应结点的左孩子结点，树中某个结点的右兄弟结点在二叉树中是相应结点的右孩子结点。也就是说，在二叉树中，左分支上的各结点在原来的树中是双亲关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟结点，所以转换后的二叉树的根结点的右孩子结点必然为空。高手点拨2.2线性表的顺序存储——顺序表6.5树和森林2．森林转换为二叉树森林转换为二叉树，实际上就是将森林中的若干棵树转换为相应的二叉树，然后再将这若干棵二叉树转换为一棵二叉树。将森林转换为二叉树的步骤如下。（1）转换：将森林中的每一棵树转换为相应的二叉树。（2）调整：第一棵树不动，从第二棵树开始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子结点，直到所有的二叉树连在一起成为一棵二叉树。提示通过以上转换可以看出，当有m（m≥1）棵树的森林转换为二叉树时，除第一棵树外，其余各树均变为二叉树中根结点的右子树。6.5树和森林3．二叉树转换为树或森林将一棵二叉树转换为树或森林的步骤如下。（1）加线：若某个结点是其双亲结点的左孩子结点，则把该结点的右孩子结点、右孩子的右孩子结点、……都与该结点的双亲结点用线连接起来。（2）抹线：抹掉原二叉树中所有双亲结点与右孩子结点的连线。（3）整理：整理得到的树或森林，使之结构层次分明。例如，将二叉树转换为树的过程如下图所示。6.5树和森林6.5树和森林6.5.3树和森林的遍历1．树的遍历树的遍历方法有两种，一种是先根遍历；另一种是后根遍历。对于非空树，先根遍历的步骤如下。（1）访问根结点。（2）依次先根遍历根结点的每一棵子树。对于非空树，后根遍历的步骤如下。（1）依次后根遍历根结点的每一棵子树。（2）访问根结点。6.5树和森林2．森林的遍历森林的遍历方法有两种，一种是先序遍历；另一种是中序遍历。对于非空森林，先序遍历的步骤如下。（1）访问森林中第一棵树的根结点。（2）先根遍历第一棵树的根结点的子树森林。（3）先根遍历除第一棵树之外的其余树构成的森林。对于非空森林，中序遍历的步骤如下。（1）后根遍历森林中第一棵树的根结点的子树森林。（2）访问第一棵树的根结点。（3）后根遍历除第一棵树之外的其余树构成的森林。6.5树和森林提示森林的先序遍历和中序遍历分别与其对应二叉树的先序遍历和中序遍历相同，因此可以用相应二叉树的遍历序列来验证森林的遍历序列。另外，树可以看作只有一棵树的森林，所以树的先根遍历和后根遍历与森林的先序遍历和中序遍历相同。同步训练利用树解决8枚硬币的真假判定问题【问题描述】有8枚硬币，其中有1枚是假币，假币的外观与真币完全相同，但重量不同，可能轻，也可能重。若以天平为称量工具，如何用最少的称量次数挑选出假币，并确定假币的重量比真币轻还是重。【问题分析】解决这个问题需要经过一系列的判断，这些判断构成了树结构，这样的树称为判定树。将8枚硬币分别用a、b、c、d、e、f、g、h表示。从8枚硬币中任取6枚（假设是a、b、c、d、e和f），在天平两端各放3枚进行比较。假设a、b、c这3枚硬币放在天平的一端，d、e、f这3枚硬币放在天平的另一端，可能出现如下3种比较结果。（1）a+b+c＞d+e+f。（2）a+b+c=d+e+f。（3）a+b+c＜d+e+f。同步训练利用树解决8枚硬币的真假判定问题下面以第一种情况为例进行讨论。若a+b+c＞d+e+f，则可以肯定这6枚硬币中必有一枚为假币，同时也说明g和h为真币。这时将天平两端各去掉一枚硬币（假设去掉c和f），同时将天平两端的硬币交换一枚（假设b和e进行互换），然后进行第二次比较，比较的结果同样可能有3种，分别是a+e＞d+b、a+e=d+b和a+e＜d+b。（1）若a+e＞d+b，说明天平两端去掉c和f且b和e互换后，天平两端的轻重关系保持不变，那么a和d中必有一枚为假币。这时只要用一枚真币（b、c、e、f、g或h）与a或d进行比较就能找出假币。例如，用h和a进行比较，若a＞h，则a是较重的假币；若a=h，则d是较轻的假币；不可能出现a＜h的情况。同步训练利用树解决8枚硬币的真假判定问题（2）若a+e=d+b，说明天平两端去掉c和f且b和e互换后，天平两端由不平衡变为平衡，那么c和f中必有一枚为假币。同样的，用一枚真币（a、b、d、e、g或h）与c或f进行比较。例如，用h和c进行比较，若c＞h，则c是较重的假币；若c=h，则f是较轻的假币；不可能出现c＜h的情况。（3）若a+e＜d+b，说明由于天平两端b和e互换，使得天平两端的轻重关系发生了变化，那么b和e中必有一枚假币。同样的，用一枚真币（a、c、d、f、g或h）与b或e进行比较。例如，用h和b进行比较，若b＞h，则b是较重的假币；若b=h，则e是较轻的假币；不可能出现b＜h的情况。对于第一次比较中出现的结果（2）和（3）的各种情况，可按照上述方法做类似的分析。整个判定过程如下图所示，图中给出了天平所有可能的状态。8枚硬币中的每一枚硬币都可能是或轻或重的假币，因此，共有16种可能的结果。而这些结果反映在树中，就是16个叶子结点。由下图可以看出，每种结果都需要经过3次比较才能得到。同步训练利用树解决8枚硬币的真假判定问题同步训练利用树解决8枚硬币的真假判定问题【代码实现】importrandom #导入random库

deffalseCoin(coin):sum1=coin[0]+coin[1]+coin[2]sum2=coin[3]+coin[4]+coin[5]