第7章 树和二叉树

第7章树和二叉树本章讲解树和二叉树。要求理解树和二叉树的性质、存储结构；学会创建二叉树；掌握二叉树的遍历；理解线索二叉树的存储结构和构造；掌握遍历线索二叉树；理解哈夫曼树的概念和构造；掌握哈夫曼编码；了解二叉树与树、森林之间的转换；灵活应用树及二叉树。你可以成绩不好，但不可以中国菜做不好！你看锅里的莲藕片，从上到下一层一层还可以再分层，变换出许多层次样式。这不就像树的分支分支再分支吗？若最多有2个分支，则成了二叉树。提纲7.1树7.2二叉树7.3二叉树遍历7.4二叉树构造7.5线索二叉树7.6哈夫曼树7.7二叉树与树、森林之间的转换7.8树及二叉树应用7.9树和二叉树学习总结7.1树树是一种1对多的非线性结构，每1个节点可以有零个或多个后继节点，但有且只有1个前驱节点（根节点除外），元素节点之间是1种层次关系。7.1.1树基本概念

7.1.1树基本概念2.术语7.1.1树基本概念7.1.1树基本概念7.1.1树基本概念3.表示树的表示是指树的逻辑结构中元素之间的层次关系的展示。7.1.1树基本概念

7.1.1树基本概念【思考与练习7.1】若1棵3次树中度为3的节点为2个，度为2的节点为1个，度为1的节点为2个，则该3次树中总的节点个数和度为0的节点个数分别是多少？答：设该3次树中总节点个数、度为0的节点个数、度为1的节点个数、度为2的节点个数和度为3的节点个数分别为n、n0、n1、n2和n3。

n=所有节点的度数之和+1

=0×n0+1×n1+2×n2+3×n3+1

=1×2+2×1+3×2+1=11又因为n=n0+n1+n2+n3即：n0=n-n1-n2-n3=11-2-1-2=6所以该三次树中总的节点个数和度为0的节点个数分别是11和6。7.1.1树基本概念节点数、度数、分支数它们之间的常用关系要理清楚：总度数=总分支数总节点数=总度数/总分支数+1总度数=0×n0+1×n1+2×n2+3×n3+...+m×nm7.1.2树存储结构顺序存储树的顺序存储分为双亲表示法、孩子表示法和双亲孩子表示法。7.1.2树存储结构2.链式存储树的链式存储分为孩子链表示法和孩子兄弟表示法。7.2二叉树定义二叉树也称为二分树，它是有限的节点集合，这个集合或者是空，或者由一个根节点和两棵互不相交的称为左子树和右子树的二叉树组成。7.2二叉树留意：二叉树的左右子树不可以互换；二叉树与度为2的树是不同的，前者度可以为0即空树，后者必须有度为2的节点即至少有3个节点且不区分左右子树。7.2二叉树

7.2二叉树【思考与练习7.2】判断下面的二叉树，哪些是满二叉树？答：只有(4)为满二叉树，因为只有(4)满足满二叉树的定义。7.2二叉树3.完全二叉树叶子节点只可能出现在最下面两层中；对于最大层次中的叶子节点，都依次排列在该层最左边的位置上；如果有度为1的节点，只可能有一个，且该节点只有左孩子而无右孩子；按层序编号后，一旦出现某节点（其编号为i）为叶子节点或只有左孩子，则编号大于i的节点均为叶子节点。7.2二叉树【思考与练习7.3】判断下面的二叉树，哪些是完全二叉树？答：(2)和(4)为完全二叉树，因为(2)和(4)满足完全二叉树的定义。留意：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。7.2.1二叉树性质

7.2.1二叉树性质

7.2.2二叉树存储结构顺序存储7.2.2二叉树存储结构2.链式存储7.2.3二叉树递归算法设计二叉树本身是一种递归结构，因此左右子树常用于被递归调用。对于二叉树b，设f(b)是求解的“大问题”。f(b->lchild)和f(b->rchild)为“小问题”。7.2.3二叉树递归算法设计

7.2.4二叉树基本操作二叉链节点类BTNode描述二叉树类BTree描述7.2.4二叉树基本操作创建二叉树【算法7.2】将括号表示法的字符串str创建为以b为根节点的二叉链存储结构。（代码见算法7.2）思路:扫描str，处理如下。(1)若ch是单个字符，创建新节点p，当b为空则p代替b；当栈不为空且flag=true时，p节点作为栈顶节点的左孩子节点；当栈不为空且flag=false时，p节点作为栈顶节点的右孩子节点。(2)若ch=‘(‘：将刚创建的p节点进栈，置flag=true。(3)若ch=‘)‘：将栈顶节点出栈。(4)若ch=','：置flag=false。(5)直到扫描完str。7.2.4二叉树基本操作2.返回二叉链括号表示返回二叉链括号表示操作是指将1棵以二叉链存储的二叉树转换为括号表示法。【算法7.3】求1棵用二叉链存储的二叉树的字符串括号表示法。思路:(1)若二叉树非空，先输出根节点t的值；(2)当t有左孩子或右孩子时，输出“（”；(3)递归处理左子树；(4)当存在右孩子时，输出“,”；(5)递归处理右子树；(6)最后输出“）”。代码见算法7.37.2.4二叉树基本操作

7.3二叉树遍历二叉树遍历是指按照一定次序访问二叉树中所有节点，并且每个节点仅被访问一次的过程。设D为根节点，L、R分别为左、右子树，我们可以组合为6种遍历方式：DLR、LDR、LRD、DRL、RDL、RLD），若再规定先遍历左子树，后遍历右子树，则对于非空二叉树，可得到如下3种遍历方式：DLR、LDR和LRD。7.3.1层次遍历从上往下、从左往右层层遍历。7.3.1层次遍历【算法7.5】设计1个算法实现二叉树层次遍历。思路:(1)若二叉树非空，先将根节点b进队；(2)在队不空时循环：从队列中出队一个节点p，访问它；(3)若它有左孩子节点，将左孩子节点进队；若它有右孩子节点，将右孩子节点进队；(4)重复（2）、（3），直到队列为空。代码见算法7.57.3.2先序遍历①访问根节点。②先序遍历左子树。③先序遍历右子树。7.3.2先序遍历【思考与练习7.4】写出下图二叉树先序遍历序列。答：ABDECFG。7.3.2先序遍历

7.3.3中序遍历①中序遍历左子树。②访问根节点。③中序遍历右子树。7.3.3中序遍历【思考与练习7.5】写出下图二叉树中序遍历序列。答：DBEAFGC。7.3.3中序遍历

7.3.4后序遍历后序遍历左子树。后序遍历右子树。③访问根节点。7.3.4后序遍历【思考与练习7.6】写出下图二叉树后序遍历序列。答：DEBGFCA。7.3.4后序遍历

7.3二叉树遍历二叉树的先序、中序、后序遍历非递归算法，了解它们的思路即可。见教材相关章节。7.4二叉树构造概念二叉树的构造就是给定某些遍历序列来唯一地确定该二叉树。7.4二叉树构造已知先序/中序/后序序列中的1种，能否唯一确定1棵二叉树呢？No！二叉树遍历序列图7.19(1)的二叉树图7.19(2)的二叉树图7.19(3)的二叉树图7.19(4)的二叉树图7.19(5)的二叉树先序序列ABCABCABCABCABC中序序列BACBCAACBCBAABC后序序列BCACBACBACBACBA7.4二叉树构造2.证明定理7.1：任何n（n≥0）个不同节点的二又树，都可由它的先序序列a和中序序列b唯一地确定。7.4二叉树构造定理7.2：任何n（n>0）个不同节点的二又树，都可由它的中序序列b和后序序列a唯一地确定。7.4二叉树构造3.举例已知先序序列为ABDGCEF，中序序列为DGBAECF，则构造二叉树的过程如图7.22（1）所示。7.4二叉树构造已知中序序列为DGBAECF，后序序列为GDBEFCA，则构造二叉树的过程如图7.22（2）所示（同先序+中序，略讲，可作为课堂练习）7.4二叉树构造4.算法【算法7.12】由二叉树的先序序列pre和中序序列in构造二叉链。思路:（1）由先序确定根；（2）找到中序中的根位置，从而确定根的左边部分为左子树，右边部分为右子树；（3）先序左子树+中序左子树=根的左子树，先序右子树+中序右子树=根的右子树；（4）在根的左右子树中再执行（1）、（2）、（3），直到序列为空。如图7.23所示。7.4二叉树构造代码见算法7.12i：先序遍历开始位置 j：中序遍历开始位置7.4二叉树构造【算法7.13】由二叉树的后序序列post和中序序列in构造二叉链。思路:（1）由后序确定根；（2）找到中序中的根位置，从而确定根的左边部分为左子树，右边部分为右子树；（3）后序左子树+中序左子树=根的左子树，后序右子树+中序右子树=根的右子树；（4）在根的左右子树中再执行（1）、（2）、（3），直到序列为空。*代码见算法7.13（类同算法7.12，略讲）7.5线索二叉树

7.5.1线索二叉树存储结构7.5.1线索二叉树存储结构线索二叉树节点类ThNode描述7.5.2构造线索二叉树构造线索二叉树即二叉树线索化的过程，实质上是在遍历过程中修改空指针的过程。7.5.2构造线索二叉树【算法7.14】构造以root为头节点的中序线索二叉树。思路:（1）p指向根节点b，pre指向root节点；（2）若p节点没有左孩子，置ltag为1，lchild指针为线索，指向其前驱节点pre。否则置其ltag为0，lchild指向其左孩子，如图7.26（1）所示；（3）若pre节点的rchild为null，置其为线索，指向后继节点p，置其rtag为1。否则置其rtag为0，rchild指向其右孩子，如图7.26（2）所示；（4）将pre指向p，重复（2）、（3），直到线索化完成。代码见算法7.147.5.3遍历线索二叉树2大规则如下：（1）求中序序列的开始节点：实际上该节点就是根节点的最左下节点。（2）对于一个节点p，求其后继节点的过程是：①如果p节点的rchild指针为线索，则rchild所指为其后继节点。②否则p节点的后继节点是其右孩子q的最左下节点post。如图7.27所示。7.5.3遍历线索二叉树【算法7.15】中序线索二叉树的中序遍历。思路:见图7.27所示的2个规则。代码见算法7.15

7.6哈夫曼树哈夫曼树是一种特殊的二叉树。7.6哈夫曼树

7.6.1哈夫曼树基本概念在n0个带权叶子节点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（或最优二叉树）。7.6.1哈夫曼树基本概念【思考与练习7.7】给定4个叶子节点，设其权值分别为1、3、5、7，可以构造出形状不同的4棵二叉树，如图7.28所示，求这4棵二叉树的WPL，并指出哪些是哈夫曼树。答：（1）WPL=1×2+3×2+5×2+7×2=32（2）WPL=1×2+3×3+5×3+7×1=33（3）WPL=7×3+5×3+3×2+1×1=43（4）WPL=1×3+3×3+5×2+7×1=29根据哈夫曼树定义，（4）为哈夫曼树。7.6.2哈夫曼树构造概念哈夫曼树构造是指在给定n个带权叶子节点的情况下，构造1棵哈夫曼树。7.6.2哈夫曼树构造规则：在n个叶子节点中选择2个权值最小的节点作为左右孩子节点，它们权值之和作为其父节点；再在新生成的父节点和剩余节点中选择2个权值最小的节点，重复（1）；重复（2），直到所有节点选择完毕，构成的二叉树便是哈夫曼树。7.6.2哈夫曼树构造举例：好比我们小时候玩的搭积木，在给定的积木方块情况下，从下到上搭建起来。7.6.2哈夫曼树构造思考与练习7.8】对于给定带权叶子节点，构造的哈夫曼树是唯一的吗？答：不是。如图7.29所示，选择好2个最小权值叶子节点后，它们在构造过程中的左右孩子位置是不唯一的，故构造的哈夫曼树不唯一。但是在给定权值叶子节点情况下，构造的所有哈夫曼树的WPL值是唯一的。7.6.2哈夫曼树构造哈夫曼树节点类HuffmanNode描述7.6.2哈夫曼树构造哈夫曼树类HuffmanBTree描述7.6.2哈夫曼树构造2.定理7.3：对于具有n0个叶子节点的哈夫曼树，共有2n0-1个节点。

7.6.2哈夫曼树构造3.算法【算法7.16】构造哈夫曼树。思路:由于在构造哈夫曼树的过程中，始终是选择权值最小的2个节点来构造，因此可以用到优先队列pq（pq中按照权值大小排序，权值越小的越优先出队）。（1）将所有n0个叶子节点进队列pq。（2）pq出队列2个节点，构造它们的父节点，父节点的权值为它们权值之和。（3）将父节点入队列pq。（4）重复（2）、（3），直到2*n0–1个节点构造完毕，哈夫曼树则构造完毕。代码见算法7.167.6.3哈夫曼编码概念对于1棵哈夫曼树，从根节点到每个叶子节点所经过的左分支对应0和右分支对应1组成的序列便为该节点对应的哈夫曼编码。7.6.3哈夫曼编码留意：哈夫曼编码是针对哈夫曼树中的叶子节点的。哈夫曼编码的实质是使用频率越高的采用越短的编码。7.6.3哈夫曼编码

7.7二叉树与树、森林之间的转换树转换为二叉树加线：在各兄弟节点之间加一连线，将其隐含的“兄－弟”关系以“双亲－右孩子”关系显示表示出来。抹线：对任意节点，除了其最左子树之外，抹掉该节点与其他子树之间的“双亲－孩子”关系。调整：以树的根节点作为二叉树的根节点，将树根与其最左子树之间的“双亲－孩子”关系改为“双亲－左孩子”关系，且将各节点按层次排列，形成二叉树。7.7二叉树与树、森林之间的转换2.1棵由树转换的二叉树还原为树加线：在各节点的双亲与该节点右链上的每个节点之间加一连线，以“双亲－孩子”关系显示