第六章 树与二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 第六章 树与二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 Huffman树及其应用

树形结构是一种非线性结构，应用十分广泛。 如：行政机构、家谱、磁盘目录等 内蒙古大学 理工学院 计算机学院 生命科学学院 外国语学院 人文学院 数学系 物理系 电子系 计算机系 计算中心 网络中心 汉语系 历史系 哲学系 生物系 环境系 动物中心 生物工程中心 资源所 英语系 日语系 行政机构

磁盘目录

6.1 树（Tree）的定义和基本术语 叶Leaf 分枝Branch 根Root 根-----------------根结点 分枝--------------分枝结点 叶-----------------叶结点

6.1 树（Tree）的定义和基本术语 树的定义具有递归性 树的定义：树是n（n>=0）结点的有限集， 在任意非空树中： (1) 有且仅有一个特定的结点称为根（Root）的结点. (2) 当n>1时，其余的结点可分为m个互不相交的子 集 T1, T2, … , Tm, 每个子集又都是树，称为根 的子树（Sub tree）. 树的定义具有递归性

6.1 树（Tree）的定义和基本术语 例6.1 Book C1 C2 C3 S1.1 S1.2 S2.1 S2.2 S2.3 S2.1.1 Tree=<D, {R}> D={Book, C1, C2, C3, S1.1, S1.2, S2.1, S2.2, S2.3, S2.1.1, S2.1.2 } R={<Book,C1>, <Book,C2>, <Book,C3>, <C1,S1.1>, <C1,S1.2>, <C2,S2.1>, <C2,S2.2>, <C2,S2.3>, <S2.1, S2.1.1>, <S2.1, S2.1.2>} Book C1 C2 C3 S1.1 S1.2 S2.1 S2.2 S2.3 S2.1.1 S2.1.2 Chapter Section

6.1 树（Tree）的定义和基本术语 术语主要来源于家谱和树： 双亲、父母（ Parent）；子女、孩子（Child）： 若〈a,b〉 R，则称a是b的双亲，b是a 的子女(孩子). 叶结点（Leaf）：度为0的结点； 分枝结点（Branch node）：度大于0的结点； 结点度（Degree）：该结点所拥有的子女数； 树的度：树内各结点度的最大值； 结点的层次（Level）：设根结点的层次为1，其它任一结点 所在的层次是其双亲的层次加1；

6.1 树（Tree）的定义和基本术语 树是一种层次结构 （hiberarchy） 1 2 3 4 5

6.1 树（Tree）的定义和基本术语 深度（Depth）：树中结点的最大层次；或称为高； 兄弟（Sibling)：具有同一双亲的结点互称兄弟； 堂兄弟（Cousin）：双亲在同一层的结点之间互称堂兄弟； 路径（Path）：如果有结点序列n1,n2,n3,…,nk，并且前1个结 点是后1个结点的双亲；它的长度是k-1; 祖先、后代（ancestor）:一个结点是它所有子树中的结点 的祖先，这些结点是它的后代(子孙); 有序树（Ordered tree）：每个结点的子女由左到右是有次 序的称有序树；否则是无序树； A B C 无序 有序

结点A的度：3 叶子：K，L，F，G，M，I，J 结点B的度：2 结点M的度：0 结点I的双亲：D 结点L的双亲：E 结点A的孩子：B，C，D 结点B的孩子：E，F A B C D E F G H I J K L M 结点B，C，D为兄弟 结点K，L为兄弟 树的度：3 树的深度：4 结点A的层次：1 结点M的层次：4 结点F，G为堂兄弟 结点A是结点F，G的祖先

6.1 树（Tree）的定义和基本术语 A B C D E F G H I J M K L (例如删除树根后的子树构成一个森林) 森林（Forest）：是m(m 0)棵互不相交的树的集合 A root B C D E F G H I J M K L T1 T2 T3 T4 T5 T6 (例如删除树根后的子树构成一个森林) 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点，F 被称为子树森林

6.1 树（Tree）的定义和基本术语 抽象数据类型树的定义： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下 无前驱； (2) 若D-{root}≠ ，则存在D-{root}的一个划分D1，D2， …，Dm，(m>0)，对任意j≠k(1≤j,k≤m)有Dj∩Dk= , 且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di， 有<root，xi>∈H；

基本操作: (3) 对应于D-{root}的划分，H—{<root，x1>，…，<root，xm>} 有唯一的一个划分H1,H2，…，Hm(m>0)，对任意j≠k(1≤j， k≤m) 有Hj∩Hk= ,且对任意i(1≤i≤m),Hi是Di上的二元 关系,(Di,{Hi})是一棵符合本定义的树,称为根root的子树. 基本操作: InitTree(&T) 操作结果：构造空树T。 DestroyTree(&T) 初始条件：树T存在。 操作结果，销毁树T。

基本操作: CreateTree(&T，definition) 初始条件：definition给出树T的定义。 ClearTree(&T) 初始条件；树T存在。 操作结果：将树T清为空树。 TreeEmpty(T) 初始条件：树T存在。 操作结果：若T为空树，则返回TRUE，否则FALSE。 TreeDepth(T) 操作结果；返回T的深度。

基本操作: Root(T) 初始条件：树T存在。 操作结果：返回T的根。 Value(T，cur_e) 初始条件：树T存在，cur_e是T中某个结点。 操作结果：返回cur_e的值。 Assign(T，cur_e，value) 操作结果：结点cur_e 赋值为value。 Parent(T，cur_e)； 操作结果：若cur_e是T的非根结点，则返回它的双亲， 否则返回“空”。

基本操作: LeftChild(T，cur_e)； 初始条件：树T存在，cur_e是T中某个结点。 最左孩子，否则返回“空”。 RightSibling(T，cur_e)； 操作结果：若cur_e有右兄弟，则返回它的右兄弟， 否则返回“空”。

基本操作: InsertChild(&T，&P，i，c)； 初始条件：树T存在,p指向T中某个结点，i指结点的度, 非空树c与T不相交。 操作结果：插入c为T中p所指结点的第i棵子树。 DeleteChild(&T，&p，i)； 初始条件：树T存在，p指向T中某个结点，i指结点的度, 操作结果：删除T中p所指结点的第i棵子树。 TraverseTree(T)； 初始条件；树T存在。 操作结果：按某种次序对T的每个结点进行遍历。 }ADT Tree

6.1 树（Tree）的定义和基本术语 树的表示方法： 1. 树形表示： 2. 括号表示(广义表表示)： A B C D E F H I J G 2. 括号表示(广义表表示)： (A(B(E))(C(F))(D(G(H)(I)(J)))) T1 T3 T2 树根

6.1 树（Tree）的定义和基本术语 3. 凹入表表示(目录表示法)： A B C D E F H I J G A B E C F D G 3. 凹入表表示(目录表示法)： A B C D E F H I J G A B E C F D G H I J

4. 文氏图表示(集合表示): 6.1 树（Tree）的定义和基本术语 A B C D E F H I J G A B E C F D G

6.2 二叉树（Binary Tree） 6.2.1 二叉树的定义 二叉树是另一种树形结构。 二叉树：是n（n>=0）结点的有限集，在任意非空树中： (1) 有且仅有一个特定的称为根（Root）的结点; (2) 当n>1时，其余的结点最多分为2个互不相交的子集 T1, T2, 每个又都是二叉树，分别称为根的左子树和右子树.

6.2.1 二叉树的定义 例 A B C D E F G H K 根结点 左子树 右子树 二叉树

注意：二叉树不是树，它是另外单独定义的一种树形结构，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。

二叉树的5种基本形态： 1 空 2 只有根 3 右子树空 4 左子树空 5 左、右子树非空 具有3个结点的二叉树可能有几种不同形态？

6.2.1 二叉树的定义 抽象数据类型二叉树的定义： ADT BinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。 若D= ，则R= ， 称Binary为空二叉树； 若D≠ ，则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠ ，则存在D-{root}的一个划分{Dl，Dr}，且Dl∩Dr= ； (3) 若Dl≠ ,则Dl中存在唯一的元素x1,<root,x1> H, 且存在Dl上的关系HlH,若Dr ≠ ,则Dr中存在唯一的元素xr,<root,xr> H,且存在Dr上的关系HrH;H={<root,xl>,<root,xr>,Hl,Hr} (4)(Dl,{Hl})是一颗符合本定义的二叉树，称为根的左子树 (Dr,{Hr})是一颗符合本定义的二叉树，称为根的右子树

基本操作: InitBiTree(&T); 操作结果：构造空二叉树T。 DestroyBiTree(&T); 初始条件：二叉树T存在。 操作结果：销毁二叉树T。 CreatBiTree(&T,definition); 初始条件：definition给出二叉树T的定义。 操作结果：按definition构造二叉树T。 ClearBiTree(&T)； 操作结果：将二叉树T清为空树。

操作结果：若T为空二叉树,则返回TRUE,否则FALSE. 基本操作: BiTreeEmpty(T)； 初始条件：二叉树T存在。 操作结果：若T为空二叉树,则返回TRUE,否则FALSE. BiTreeDepth(T)； 操作结果：返回T的深度。 Root(T)； 初始条件: 二叉树T存在。 操作结果：返回T的根。 Value(T，e) 初始条件：二叉树T存在，e是T中某个结点。 操作结果；返回e的值。

基本操作: Assign(T，&e，value)； Parent(T，e)； LeftChild(T，e)； 初始条件；二叉树T存在，e是T中某个结点。 操作结果：结点e赋值为value。 Parent(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。 LeftChild(T，e)； 操作结果：返回e的左孩子，若e无左孩子，则返回“空”。 RightChild(T，e)； 操作结果：返回e的右孩子,若e无右孩子，则返回“空”。

操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则 返回“空”。 基本操作: LeftSibling(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则 返回“空”。 Rightsibling(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟， 则返回“空”。

InsertChild(T，p，LR，c)； 基本操作: InsertChild(T，p，LR，c)； 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1， 非空二叉树c与T不相交且右子树为空。 操作结果：根据LR为0或1，插入c为T中p所指结点的左或 右子树。P所指结点的原有左或右子树则成为c 的右子树。 DeleteChild(T，p，LR)； 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。

PreOrderTraverse(T)； 基本操作: PreOrderTraverse(T)； 初始条件：二叉树T存在。 操作结果：先序遍历T中对每个结点一次且仅一次。 InOrderTraverse(T)； 初始条件：二叉树T存在。 操作结果：中序遍历T中每个结点一次且仅一次。

基本操作: PostOrderTraverse(T)； 初始条件：二叉树T存在。 操作结果：后序遍历T中每个结点一次且仅一次。 LevelOrderTraverse(T)； 初始条件：二叉树T存在。 操作结果：层序遍历T中每个结点一次且仅一次. }ADT BinaryTree

6.2.2 二叉树的性质 性质1: 在二叉树的第i层最多有2i-1 个结点(i>=1). 用归纳法证明： 归纳基： 6.2.2 二叉树的性质 性质1: 在二叉树的第i层最多有2i-1 个结点(i>=1). 用归纳法证明： 归纳基： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点， 2i-1 = 20 = 1； i=k时命题成立; i=k+1时,二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2k-1 2 = 2(k+1)-1=2i-1 。

证明： 基于性质1，深度为 k 的二叉树上的结点数最多为 20+21+       +2k-1 = 2k-1 6.2.2 二叉树的性质 性质2: 深度为k的二叉树最多有2k –1个结点（k>=1). 证明： 基于性质1，深度为 k 的二叉树上的结点数最多为 20+21+       +2k-1 = 2k-1

证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 6.2.2 二叉树的性质 性质3: 任一二叉树, 若叶结点数是n0 , 度为2的结点数 是 n2 ,则 n0 = n2 +1 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1

6.2.2 二叉树的性质 满二叉树(Full Binary Tree): 每一层的结点数都达到了最 大的二叉树. 编号的满二叉树: 从根开始,由上到下, 从左到右地对每个结点 进行编号. 也就是说:根的编号是1,一个结点,若它是双亲 的左子女,则它的编号是它的双亲编号的2倍;若它是双亲 的右子女,则它的编号是双亲编号的2倍+1. A B C D E F H 1 2 3 4 5 6 7 编号的满二叉树

6.2.2 二叉树的性质 完全二叉树(Complete Binary Tree): 深度为k的满二叉树, 删去第k层上最右边的j(0 j<2k-1)个结点,就得到一个深度为k 的完全二叉树. 编号的完全二叉树: 与满二叉树编号相同 A B C E F H 1 2 3 4 5 6 7 A B C D E 1 2 3 4 5 1 A B C E 2 3 4

证明： 设 完全二叉树的深度为 k 则根据性质2得 2k-1 -1 < n ≤ 2k-1 或者 2k-1 ≤ n < 2k 6.2.2 二叉树的性质 性质4: 具有n个结点的完全二叉树,其深度为 。 证明： 设 完全二叉树的深度为 k 则根据性质2得 2k-1 -1 < n ≤ 2k-1 或者 2k-1 ≤ n < 2k 即 k-1 ≤ log2 n < k 因为 k 只能是整数，因此， k =log2n + 1 或 k = log2n+1

6.2.2 二叉树的性质 性质5：在编号的完全二叉树中，对任一结点i（1≤i ≤ n）有： （2）若2i ≤ n，则结点i的左子女是2i; 否则无左子女； （3）若2i+1 ≤ n，则结点i的右子女是2i; 否则无右子女； 1 2 3 i i+1 4 5 6 2i 2i+1 2i+2

6.2.3 二叉树的存储结构 一 、二叉树的顺序存储 根据性质5知： ST[i] 的双亲是ST[ ], 6.2.3 二叉树的存储结构 一 、二叉树的顺序存储 完全二叉树的顺序存储： A B C E F H 1 2 3 4 5 6 0 1 2 3 4 5 6 A B C E H F ST[ ] 根据性质5知： ST[i] 的双亲是ST[　　], 　　　　　　　左子女是ST[2*i]，右子女是ST[2*i+1]．

6.2.3 二叉树的存储结构 一、二叉树的顺序存储 根据性质5知： ST[i] 的双亲是ST[ ], 左子女是 6.2.3 二叉树的存储结构 A B C E F H 1 2 3 4 7 9 一、二叉树的顺序存储 0 1 2 3 4 5 6 7 8 9 A B C E F H ST[ ] 根据性质5知： ST[i] 的双亲是ST[ ], 左子女是 ST[2*i],右子女是ST[2*i+1]. 这样太浪费空间,适合完全二叉树

6.2.3 二叉树的存储结构 二、 二叉树的链式存储结构(二叉链表) 二叉链表 lchild data rchild Left child 6.2.3 二叉树的存储结构 二、 二叉树的链式存储结构(二叉链表) lchild data rchild Left child Right child BiTNode: typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,* rchild; }BiTNode, *BiTree; A B C E H F G 二叉链表 BT A B C E F H G

6.2.3 二叉树的存储结构 二 、二叉树的链式存储结构(三叉链表) BiTNode: typedef struct BiTNode{ 6.2.3 二叉树的存储结构 二 、二叉树的链式存储结构(三叉链表) BiTNode: typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild,*parent; }BiTNode, *BiTree; Parent lchild data rchild parent Left child Right child

6.2.3 二叉树的存储结构 二 、二叉树的链式存储结构(三叉链表) A B C E H F G 三叉链表 BT A B C E F H G

6.3 遍历二叉树和线索二叉树 一、遍历 按照某种搜索路径访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。 6.3 遍历二叉树和线索二叉树 一、遍历 按照某种搜索路径访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。 “访问”的含义特别很广，如：输出结点的信息等。 因二叉树是非线性结构， 每个结点可能有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。

N L R 6.3 遍历二叉树和线索二叉树 二、遍历方法 NLR 前(先)序 遍历 LNR LRN 中序遍历 后序遍历 NRL RNL 6.3 遍历二叉树和线索二叉树 二、遍历方法 NLR LNR LRN 前(先)序 遍历 1 中序遍历 N 3 后序遍历 2 L R NRL RNL RLN

6.3 遍历二叉树和线索二叉树 算法思想6.1 前序遍历： 若BT非空，则： 1.访问根结点； 2.前序遍历左子树； 3.前序遍历右子树; 6.3 遍历二叉树和线索二叉树 算法思想6.1 前序遍历： 若BT非空，则： 1.访问根结点； 2.前序遍历左子树； 3.前序遍历右子树; 算法思想6.2 中序遍历： 若BT非空，则： 1.中序遍历左子树； 2.访问根结点； 3.中序遍历右子树； 算法思想6.3 后序遍历： 若BT非空，则： 1.后序遍历左子树； 2.后序遍历右子树； 3.访问结点；

6.3 遍历二叉树和线索二叉树 例6 前序遍历(NLR)序列： A B E H G C F 中序遍历(LNR)序列： E B G H A F 6.3 遍历二叉树和线索二叉树 例6 A A A A 算法思想6.1 前序遍历： 若BT非空，则： 1.访问根结点； 2.前序遍历左子树； 3.前序遍历右子树; B B B B C C C C E E E E H H H H F F F F G G G G 前序遍历(NLR)序列： A B E H G C F 中序遍历(LNR)序列： E B G H A F C 后序遍历(LRN)序列： E G H B F C A

前序遍历二叉树的递归算法 算法 6.1 Void PreOrderTraverse(BiTree BT){ if (BT){ visit(BT); PreOrderTraverse(BT->lchild); PreOrderTraverse(BT->rchild); }// } // end of PreOrderTraverse 请同学们自己写出 InOrderTraverse(BT) 和　PostOrderTraverse(BT)

建立二叉树 建立二叉树的方法很多，我们给出以前序遍历序列建 立二叉树的方法，但该序列是扩充二叉树的前序遍历 序列。 是扩充的叶结点，它代表空指针。 D B F E A C 该扩充二叉树的前序遍历序列是：ABD**EF***C** 该算法是一递归算法，递归三要素： 1. 递归出口：当遇到*时，是空。 2. 建立根。 3. 建立左子树和右子树。

建立二叉树的算法 Status CreateBiTree(BiTree &BT) { //按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树， 构造二叉链表表示的二叉树T. scanf(&ch)； if(ch==‘ ’) BT=NULL； else{ if(!(BT=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW)； BT->data=ch; ／／生成根结点 CreateBiTree(BT->lchild); ／／构造左子树 CreateBiTree(BT->rchild); ／／构造右于树 } return OK； }／／CreateBiTree

A B C D BT A B D ^ ^ ^ C ^ ^

遍历二叉树的非递归算法： 我们先观察一下三种遍历行走的路线 前序遍历NLR * A B C E F H G D I * * * * * *

中序遍历LNR A B C E F H G D I # # # # # # # # #

后序遍历LRN & A B C E F H G D I & & & & & & & &

三种遍历的访问位置对比： 前序：第一次经过* 时访问 中序：第二次经过# 时访问 后序：第三次经过& 时访问 三种遍历的路线完全一样，只是访问时间不同； & A B C E F H G D I * # 前序：第一次经过* 时访问 中序：第二次经过# 时访问 后序：第三次经过& 时访问

遍历线路的核心规则是：先左后右； 非递归中序遍历二叉树的算法思想 建立栈 stack； P指向根； 当p不空 且 stack 不空时反复做： stack 中数据元素的类型：　*BiTNode(或BiTree) 函数：BiTree P; push(S,p); pop(S,p); Boolean StackEmpty(S); 下面给出基于逻辑 结构的算法描述 非递归中序遍历二叉树的算法思想 建立栈 stack； P指向根； 当p不空 且 stack 不空时反复做： 若 p不空 ,p 入 栈; p指向左子女； 否则： 出栈顶元素到p中； 访问p； p指向右子女； 4. 结束 如何进行前序遍历？

非递归中序遍历BT的算法: Void lnorderTraverse(BiTree BT) { InitStack(S)； p=BT； while(p||!StackEmpty(S)) { if(p) { push(S，p)； p=p->lchild；}//根指针进栈，遍历左子树 else { ／／根指针退栈，访问根结点，遍历右子树 pop(S，p)； visit(p)); p=p->rchild； }//else }／／InOrderTraverse

例 A B C D E F G p i &A (1)

例 A B C D E F G p i &A &B (2)

例 A B C D E F G p i &A &B &C (3)

例 p=NULL A B C D E F G i &A &B 访问：C (4)

例 p A B C D E F G i &A 访问：C B (5)

例 A B C D E F G i &A &D 访问：C B p (6)

例 A B C D E F G i &A &D &E 访问：C B p (7)

例 A B C D E F G i &A &D 访问：C B E p (8)

例 A B C D E F G i &A &D &G 访问：C B E P=NULL (9)

例 A B C D E F G i &A &D 访问：C B E G p (10)

例 A B C D E F G i &A 访问：C B E G D p (11)

例 A B C D E F G i &A &F 访问：C B E G D p (12)

例 A B C D E F G i &A 访问：C B E G D F p=NULL (13)

例 A B C D E F G i 访问：C B E G D F A p (14)

例 A B C D E F G i 访问：C B E G D F A p=NULL (15)

非递归后序遍历BT的算法 非递归后序遍历二叉树的算法思想 后序遍历时，访问一个结点的时间是： 建立栈 stack； P指向根； 当p不空 且 stack 不空时反复做： 若 p不空 ：(p,L) 入 栈; p指向左子女； 否则： 出栈顶元到p和tag中； 若tag==R ,则访问p；p置空； 否则 （p,R）入栈； 并让 p指向右子女； 4. 结束 后序遍历时，访问一个结点的时间是： 第3次经过时或 第2次反回时或 从右边返回时； 如何区分从左还是右返回的呢？ P入栈时带一标记: 向左走时带L 向左走时带R

非递归的后序遍历BT算法:（基于二叉链表存储结构） void PostOrderTraverse (BiTree BT) { InitStack(S)； //建立栈 p=BT; //指向根 while (p || !StackEmpty(S)) { if (p) { push((p, L))； // p带L入 栈 p=p->lchild; } // p指向左子女 else { pop(p,e); //出栈顶元到e中 p=e.p; tag=e.tag; if (tag==‘R’) { visite(p->data); p=NULL;} //访问p else { push((p, R)); p=p->rchild; } // p指向右子女 } // else } // end of while } // end of postOrderTraverse (bt)

例 (A,L) 入栈 (A,L) (B,L) 入栈 (A,L)(B.L) (B.L)退栈， (A,L) (B,R)入栈 (A,L) (B,R) (E,L)入栈 (A,L) (B,R) (E,L) (E,L)退栈 (A,L) (B,R) (E,R)入栈 (A,L) (B,R) (E,P) (E,R)退栈 (A,L) (B,R) 访问E (B,R)退栈 (A,L) 访问B (A,L)退栈 (A,R)入栈 (A,R) (C,L)入栈 (A,R) (C,L) (C,L)退栈 (A,R) (C,R)入栈 (A,R) (C,R) (C,R)退栈 (A,R) 访问C (A,R)退栈 访问A 1 例 2 3 Start 4 5 A 1 6 16 7 10 11 8 B C 2 12 15 9 9 14 3 4 10 13 E 11 5 8 7 12 6 13 14 15 16

课堂练习 前序遍历序列：EDACBGFE 中序遍历序列：ADCBEFHG 试画出满足以上序列的二叉树 课堂练习 中序遍历序列：ADCBHFEG 后序遍历序列：ABCDEFGH 试画出满足以上序列的二叉树

二、线索二叉树(Threaded Binary Tree) 目的：利用二叉树的空指针保存遍历序列的前驱和后继。 n个结点的二叉树,有2n个指针,只用了n-1个,有n+1个是空指。 用空的左指针指向某一遍历序列的前驱. 用空的右指针指向某一遍历序列的后继. 这两种指针称为线索(Thread)。 为了区分线索与真实指针，给结点增加两个域Ltag和Rtag

Ltag=0: lchild 指向结点的左子女； Rtag=0: rchild 指向结点的右子女； 二、线索二叉树(Threaded Binary Tree) lchild Ltag data Rtag rchild Ltag=0: lchild 指向结点的左子女； Ltag=1: lchild 指向某一遍历序列前驱； Rtag=0: rchild 指向结点的右子女； Rtag=1: rchild 指向某一遍历序列后继；

二、线索二叉树(Threaded Binary Tree) Typedef enum{Link,Thread} PointerTag; Typedef struct BiThrNode { ElemType data; struct BiThrNode *lchild, *rchild; PointerTag Ltag, Rtag; } BiThrNode, *BiThrTree; lchild Ltag data Rtag rchild

二、线索二叉树(Threaded Binary Tree) 加了线索的二叉树是线索二叉树； 给二叉树加线索的过程是线索化（穿线）； 按前序遍历序列穿线的二叉树是前序线索二叉树； 按中序遍历序列穿线的二叉树是中序线索二叉树； 按后序遍历序列穿线的二叉树是后序线索二叉树； 中序线索二叉树简称线索二叉树；

二、 线索二叉树(Threaded Binary Tree) C E T 先序序列：ABCDE 先序线索二叉树 A B C D E 1 1 1 1 1 1 ^

二、 线索二叉树(Threaded Binary Tree) C E T 中序序列：BCAED 中序线索二叉树 A B C D E ^ 1 1 ^ 1 1 1 1

二、 线索二叉树(Threaded Binary Tree) C E T 后序序列：CBEDA 后序线索二叉树 A B C D E 1 1 ^ 1 1 1 1

二、线索二叉树(Threaded Binary Tree) NULL B C NULL D E F 中序线索二叉树

非递归中序遍历二叉树的算法(回忆) Void lnorderTraverse(BiTree BT) { InitStack(S)； p=BT； while(p||!StackEmpty(S)) { if(p) { push(S，p)； p=p->lchild；}//根指针进栈，遍历左子树 else { ／／根指针退栈，访问根结点，遍历右子树 pop(S，p)； visit(p); p=p->rchild； }//else }／／InOrderTraverse

visit(p) 对以二叉链表存储的二叉树进行中序线索化(非递归的) void InOrderThreading (BiThrTree BT) { InitStack(S); //建立栈 p=BT; pre=NULL; //p指向根,pre是p的前驱结点 while (p || !StackEmpty(S)) { if (p) { push(S,p); // p入栈 p=p->lchild; } // p指向左子女 else { pop(S,p); //出栈顶元到p中 if (!p->lchild) { p->lchild=pre; p.ltag=true;} if(pre && !pre->rchild) { pre->rchild=p; pre.rtag=true;} pre=p; p=p->rchild; } // p指向右子女 } // end of while } // end of InOrderThreading(BT) visit(p)

(中序)线索二叉树的线索给我们提供了足够的信息, 对其进行遍历时，既不需要递归 (使用了系统栈), 也不需要栈. 对(中序)线索二叉树进行非递归遍历且不需要设栈时需要主要解决的两个问题: 找到某一次序下的第一个结点p; 2) 找出给定结点p在某一次序中的后继结点;

中序遍历(中序)线索二叉树时如何解决这两个问题: 关键问题1 沿着根的左链走,直到无左子女的结点p，即中序序列中的第一个结点; p=BT; while (!p.ltag) p=p->lchild; 关键问题2，有如下两种情况： P无右子女：则p->rchild是p的后继； P有右子女：则p的右子树中最左的结点就是p的后继，方法同关键问题1。 if (p.rtag) p=p->rchild; // P无右子女 else { p=p->rchild; // P有右子女 while (!p.ltag) p=p->lchild; }

void InOrderTraverse(BiThrTree BT) { while(!p) { 中序遍历线索二叉树的算法 void InOrderTraverse(BiThrTree BT) { p=BT; while(!p) { while (!p->ltag) p=p->lchild; //沿左链走直到无左子女的结点 visit(p); while (p->rtag && p) { p=p->rchild; visit(p);} p=p->rchild; } } // inOrderTraverse

同理，我们可以前序非递归遍历中序线索二叉树， 同样不需要递归（使用了系统栈）也不需要栈. 关键问题1 根就是第一个结点. 关键问题2，有如下3种情况： P有左子女：则p左子女是p的后继；否则 P有右子女：则p的右子女是p的后继; 否则 P是叶：沿着p的线索走，直到空或一个有右子女的结点r为止，若空，则p无后继，否则r的右子女是p 的 后继。

前序遍历线索二叉树的算法 void PreOrderTraverse(BiThrTree BT){ p=BT; while (p) { visit(p); if (!p->ltag) p=p->lchild; // P有左子女 else if (!p->rtag) p=p->rchild; // P有右子女 else{ r=p->rchild; //p是叶 while (r && r.rtag) r=r->rchild; if (r) p=r->rchild; else p=r; } } } // PreOrderTraverse

6.4 树的存储结构 一、 树的存储结构 1、双亲表示法 是一种顺序存储方法，即用数组存储。 每个结点有两个域: data是结点的数据元素； 6.4 树的存储结构 一、 树的存储结构 1、双亲表示法 是一种顺序存储方法，即用数组存储。 每个结点有两个域: data是结点的数据元素； parent是指出该结点的双亲结点在数组中的下标； PTNode: data parent

一、 树的存储结构 树的双亲表示法说明： #define MAX-TREE-SIZE 100 typedef struct PTNode{ 一、 树的存储结构 树的双亲表示法说明： #define MAX-TREE-SIZE 100 typedef struct PTNode{ ElementType data; int parent; // 该结点的双亲的下标 } PTNode; typedef struct { PTNode nodes[MAX-TREE-SIZE]; int n; //树的结点数 } PTree;

一、 树的存储结构 例 用双亲法存储树 A -1 B 0 C 0 D 0 E 1 F 2 G 3 H 6 I 6 J 6 1 2 3 4 5 一、 树的存储结构 例 用双亲法存储树 A -1 B 0 C 0 D 0 E 1 F 2 G 3 H 6 I 6 J 6 1 2 3 4 5 6 7 8 9 10 11 A B C D E F H I J G A B C D E F G H I J 1 2 3 4 5 6 7 8 9

一、 树的存储结构 例 用双亲法存储森林 1 2 3 4 5 6 7 8 9 10 11 A -1 B -1 C 0 D -1 E 1 一、 树的存储结构 例 用双亲法存储森林 1 2 3 4 5 6 7 8 9 10 11 A -1 B -1 C 0 D -1 E 1 F 2 G 3 H 6 I 6 J 6 A C D F H I J G 2 3 B E 1 4 5 6 7 8 9 同样的道理可以存储森林

Data child1 child2 child3 child4 ……….…childk 一、 树的存储结构 2、 孩子（子女）表示法 结点结构 Data child1 child2 child3 child4 ……….…childk 对不同的结点,k(度)是不同的, 因此应取最大数,即树的度; 这种方法不可取;所以最自然的方法是为每个结点建立一 个单链表，该单链表存储它的所有孩子，所有结点组成一个 数组，称表头数组。表头数组中每一项称孩子链表头指针 CTBox: (头结点) 单链表中每一项称孩子结点(也称表结点)： CTNode: data firstchild child next

树的孩子链表存储表示说明： typedef struct CTNode { //孩子结点（表结点） int child； struct CTNode *next； } *ChildPtr； tyPedef struct { //头结点 TElemType data； ChildPtr firstchild; }CTBox； typedef struct { //孩子链表头指针 CTBox nodes[MAX_TREE_SIZE]； int n，r； //结点数和根的位置； }CTree；

2、孩子表示法(子女表示法) ^ ^ ^ a b c d e f h g i a c d e f g h i b 6 1 2 3 4 5 7 1 2 3 4 5 7 8 9 data firstchild 1 2 ^ 3 4 ^ 5 ^ ^ 8 6 7 ^ ^ ^ ^ ^ 如何找双亲结点

带双亲的孩子链表存储表示: typedef struct CTNode { //孩子结点（表结点） int child； struct CTNode *next； } *ChildPtr； typedef struct{ //头结点 TElemType data； int parent; ChildPtr firstchild; }CTBox； typedef struct { //孩子链表头指针 CTBox nodes[MAX_TREE_SIZE]； int n，r； //结点数和根的位置； }CTree；

2、孩子表示法(子女表示法) 带双亲的孩子链表 5 1 2 3 4 6 7 8 a c d e f g h i b data 1 2 3 4 6 7 8 a c d e f g h i b data firstchild -1 parent a b c d e f h g i 1 2 ^ ^ 3 4 5 ^ ^ ^ 8 6 7 ^ ^ ^ ^

一、 树的存储结构 3、 孩子兄弟表示法(也称二叉树表示法 或二叉链表表示法) 结点结构（CSNode）: 一、 树的存储结构 3、 孩子兄弟表示法(也称二叉树表示法 或二叉链表表示法) 结点结构（CSNode）: data firstchild nextsibling 指向该结点的 下一个兄弟 指向该结点的 第一个孩子

树的孩子链表存储表示 typedef struct CSNode { TElemType data； struct CSNode * firstchild， * nextsihling； }CSNode，*CSTree；

一、 树的存储结构 例 用孩子兄弟法存储树 A B C D E F H I J G 1 2 3 4 5 6 7 8 9 I Λ A Λ B 一、 树的存储结构 例 用孩子兄弟法存储树 A B C D E F H I J G 1 2 3 4 5 6 7 8 9 I Λ A Λ B C D Λ E Λ Λ F Λ Λ G Λ H Λ J Λ Λ

二、 树与森林的遍历 若树非空，则 访问根结点; 从左到右先根遍历根的每棵子树; 树的遍历: 按根的次序区分有两种遍历次序 (1) 先根遍历: 若树非空，则 访问根结点; 从左到右先根遍历根的每棵子树;

二、 树与森林的遍历 例 先根遍历树 A B C D E F H I J G 先根遍历序列: A B E C F D G H I J

二、 树与森林的遍历 （2）后根遍历: 若树非空，则 从左到右后根次序遍历根的每棵子树; 访问根结点;

二、 树与森林的遍历 例 后根遍历树 A B C D E F H I J G 后根遍历序列: E B F C H I J G D A

二、 树与森林的遍历 森林的遍历: 森林的遍历是基于树的遍历完成的,对应有两种遍历次序: (1) 先序遍历: 访问第一棵树的根; (1) 先序遍历: 访问第一棵树的根; 先序遍历第一棵树中的根结点的子树森林； 先序遍历其余的树所构成的森林； (2) 中序遍历: 中序遍历第一棵树的子树； 中序遍历其余的树所构成的森林；

二、 树与森林的遍历 先序遍历森林 先序遍历序列： B E A C F D G H I J 先序遍历: 访问第一棵树的根; 先序遍历第一棵树中的根 结点的子树森林； 先序遍历其余的树所构成 的森林； 先序遍历森林 D H I J G A C F B E 先序遍历序列： B E A C F D G H I J

二、 树与森林的遍历 中序遍历森林 中序遍历序列：BCDAFEHJIG 中序遍历: 中序遍历第一棵树的子树； 访问第一棵树的根; 中序遍历其余的树所构成的 森林； A B C D E F G H I J 中序遍历序列：BCDAFEHJIG

三、 森林与二叉树的转换 1). 森林=>二叉树的转换 自然转换法： 但保留双亲到其第一子女的连线，最后转45°。 三、 森林与二叉树的转换 在森林与二叉树 之间存在一一对应的关系。 1). 森林=>二叉树的转换 自然转换法： 凡是兄弟用线连起来，然后去掉双亲到子女的连线， 但保留双亲到其第一子女的连线，最后转45°。

= = 三、 森林与二叉树的转换 例：森林到二叉树的转换 前序序列：ABCDEFGHIJ 前序序列：ABCDEFGHIJ 三、 森林与二叉树的转换 例：森林到二叉树的转换 A B C D E F G H I J A E G B C D F H I J = 前序序列：ABCDEFGHIJ 前序序列：ABCDEFGHIJ = 中序序列：BCDAFEHJIG 中序序列：BCDAFEHJIG

三、 森林与二叉树的转换 2) 二叉树=>森林的转换 自然转换法： 若某结点是其双亲的左孩子，则该结点的右孩子、 三、 森林与二叉树的转换 2) 二叉树=>森林的转换 自然转换法： 若某结点是其双亲的左孩子，则该结点的右孩子、 右孩子的右孩子 …, 都与该结点的双亲连接起来, 最后去掉所有双亲到右孩子的连线.

A E A B C D E F G H I J B G C F D H I J

6.6 Huffman树及其应用 问题提出:在数据通信中，用二进制给每个字 符编码,如何使电文总长最短且不产生二义性? 根据字符出现频率，利用Huffman树可以构造一种不等长的二进制编码，并且构造所得的Huffman编码是一种最优前缀编码，即使所传电文的总长度最短。任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

6.6 Huffman树及其应用 最优二叉树（Huffman） 如何构造最优二叉树 如何求哈夫曼编码

一、哈夫曼树(最优树)的定义 结点的路径长度：从根结点到该结点的路径上分支的 数目。 树的路径长度：树中每个结点的路径长度之和。 (结点)带权路径长度:结点的路径长度*结点的权=li*wi 树的带权路径长度：树中所有叶结点的带权路径长度之和WPL(T)=

设K={k1,k2,…kn},它们的权W={w1,w2,…,wn}, 构造以k1,k2,…kn为叶结点的二叉树，使得 一、哈夫曼树(最优树)的定义 设K={k1,k2,…kn},它们的权W={w1,w2,…,wn}, 构造以k1,k2,…kn为叶结点的二叉树，使得 WPL= 为最小,则称之为“最优二叉树”。

例 W={1,2,4,6} ,可构造出如下的二叉树： 6 1 4 1 2 4 6 2 1 2 4 6 (1) (2) (3) WPL =(1+2+4+6)*2=26 WPL =1+2*2+(4+6)*3=35 WPL =6+4*2+(1+2)*3=23 根据定义求Huffman树的方法是：对给定的n个叶子结点（外部结点），构造出全部二叉树并求出其WPL，然后找出WPL最小的树。 当n较大时，显然这种方法是不可取的。

二、构造huffman树 问题: 如何证明所构造的二叉树是最优树? 算法思想： 1. 根据权值{w1 , w2 ,…, wn}构造n个二叉树F={T1 , T2 , …, Tn}，其中 Ti中是只含权值为wi 的结点。 2. 从F中选两个权值最小的二叉树Ti和Tj，构造一个 根结点R, R的权wR为wi + wj 。 3. 从F中删除Ti和Tj ，加入新的树R到F中。 4. 重复2，3 直到F中只有一棵树(或执行n-1次)为止。 问题: 如何证明所构造的二叉树是最优树?

例: 已知权值 W={ 5, 6, 3, 9, 7 } 5 6 3 9 7 6 7 3 8 5 9

例: 已知权值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 3 8 5 7 6 13 9

例: 已知权值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 3 8 5 9 17 7 6 13

例: 已知权值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 3 8 5 9 17 7 6 13 30

Huffman 算法的实现： 用n个叶结点构造出的最优二叉树共有几个结点？ 构造最优树时共执行n-1次循环，每次增加一个新 结点，共增加了n-1个结点，所以结点总数一定 是n+n-1=2n-1 因为n0=n2+1, 所以n2=n0-1, 又由于在最优二叉树中 没有度为1的结点,所以在最优二叉树中总的结点数为 n+n-1=2n-1

Huffman编码： 设字符集为 {c1 , c2 ,…, cn} , 看作叶结点 出现概率为 {w1 , w2 ,…, wn} ,叶结点的权 （1）构造Huffman树 （2）左分支标0，右分支标1 （3）根到叶结点ci的路径上的二进制编码就是ci的编码 编码长度为{ l1 , l2 ,…, ln} 是叶结点的路径长度, 则树的带权路径长度WPL是：

Huffman编码： 根到任何ci的路径都不会经过任何其它ck, 因此 Huffman编码是无前缀编码，即任何一个编码都不 会是另一个编码的前缀。 例：字符集{a,b,c,d,e,f,g,h}出现概率分别是 {0.14, 0.08, 0.11, 0.23, 0.29, 0.05, 0.03, 0.07}

构造Huffman 树： 100 1 (2)编码： a: 110 b: 1111 c: 011 d: 00 e: 10 f: 0101 g: 0100 h: 1110 1 42 58 1 1 1 1 d 19 e 29 1 1 23 1 1 29 8 c a 15 1 1 1 1 14 11 g f h b 8 3 5 7 (3)编码长度： WPL= 2*0.23+4*0.03+ 4*0.05+ 3*0.11+ 2*0.29+3*0.14+4*0.08+4*0.07=2.71

Huffman 算法的实现： 用数组存储Huffman 树，每个数组元素HTNode包括4个域: 1 2 3 n n+1 2n-1 权 w 双亲 parent 左子女 lchild 右子女 rchild 叶子结点(外部结点) 内部结点

//——哈夫曼树和哈夫曼编码的存储表示—— typedef struct{ unsigned int weight； unsigned int parent，lchild，rchild； }HTNode，*HuffmanTree；//动态分配数组存储哈夫曼树 typedef char **HuffmanCode；//动态分配数组存储哈夫曼编码表

构造哈夫曼树的算法 void HuffmanCoding(HuffmanTree &HT，HuffmanCode &Hc,int *w,int n) { //w存放n个字符的权值(均>0),构造哈夫曼树,并求出n个字符的赫夫曼编码Hc。 if(n<=1) return； m=2*n-1; HT=(HuffmanTree)malloc((m十1)*sizeof(HTNode))；// 0号单元未用 for(p=HT+1, i=1; i<=n; ++i, ++p,++w) *p= {*w， 0，0，0 }；//前n个结点 for(; i<=m； ++i，++p) *p={0，0，0，0}；//后n-1个结点 for(i=n+1；i<=m；++i){ //建哈夫曼树 //在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。 Select(HT，i-1，s1，s2)； HT[s1].parent=HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2； HT[i].weight=HT[s1].weight+HT[s2].weight； }

//—从叶子到根逆向求每个字符的哈夫曼编码— HC=(HuffmanCode)malloc((n十1)*sizeof(char*)); //分配n个字符编码的头指针向量 cd=(char*)malloc(n*sizeof(char))； //分配求编码的工作空间 cd[n-1]="＼0";； //编码结束符。 for(i=1;i<=n；++i){ //逐个字符求哈夫曼编码 start=n-1； //编码结束符位置 for(c=i，f=HT[i].parent；f!=0；c=f，f=HT[f].parent) //从叶子到根逆向求编码 if(HT[f].lchild==c) cd[--start]="0"； else cd[--start]="1"； HC[i]=(char*)malloc((n—start)*sizeof(char))； //为第i个字符编码分配空间 strcpy(Hc[i]，&cd[start])； //从cd复制编码(串)到Hc } free(cd)； //释放工作空间 } //HuffanCoding

本章小结 存储结构 遍历 1、定义和性质 树 2、存储结构 森林 3、遍历 4、线索化：线索树 Huffman树 先序遍历 后序遍历 双亲表示 孩子表示 孩子兄弟 存储结构 遍历 1、定义和性质 树 二叉树 森林 顺序结构 链式结构 2、存储结构 二叉链表 三叉链表 中序遍历 后序遍历 先序遍历 3、遍历 遍历 Huffman树 先序线索树 中序线索树 后序线索树 先 序 遍 历 中 序 遍 历 4、线索化：线索树 定义,构造,编码

本章小结 理解树形结构的基本概念和术语； 深刻领会二叉树的定义和存储结构，熟悉二叉树的 遍历并熟练掌握遍历算法； 理解二叉树线索化的实质，熟练掌握二叉树的线索 化过程以及遍历中序线索二叉树的方法; 理解树和森林的定义、树的存储结构并掌握树、森 林与二叉树之间的相互转换方法。 理解最优树的特性，掌握建立最优树和Huffman编 码的方法。在此基础上能进行算法设计。

作 业 书面作业: p38: 6.3题，6.5题 p39: 6.14题 p40: 6.20题 p41: 6.27题 p43: 6.43题 作 业 书面作业: p38: 6.3题，6.5题 p39: 6.14题 p40: 6.20题 p41: 6.27题 p43: 6.43题 上机作业: 1.遍历二叉树(使用栈非递归实现，三种遍历任选一种，前序中序满分4分，后序满分5分) 2. 哈夫曼编/译码器(p149)