第六章 树和二叉树

§6.1 树的类型定义 § 6.2 二叉树的类型定义 § 6.3 二叉树的性质和存储结构 § 6.4 二叉树的遍历 § 6.5 二叉树的遍历应用举例 § 6.6线索二叉树 § 6.7 树和森林 § 6.8 赫夫曼树与赫夫曼编码

§ 6.1 树的类型定义

数据对象 D： D是具有相同特性的数据元素的集合。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。

A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) 例如: A C D B E F G H I J K L M A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) 树根 T1 T2 T3

树的表示方法 A A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) T1 T3 T2 树根 广义表表示 B E 文氏图表示 凹入表示

对比树型结构和线性结构的结构特点

线性结构 树型结构 根结点 (无前驱) 第一个数据元素 (无前驱) 最后一个数据元素 (无后继) 多个叶子结点 (无后继) 其它数据元素 (一个前驱、 一个后继) 其它数据元素 (一个前驱、 多个后继)

基 本 术 语

结点: 数据元素+若干指向子树的分支 结点的度: 分支的个数 树的度: 树中所有结点的度的最大值 叶子结点: 度为零的结点 分支结点: D 叶子结点: 度为零的结点 H I J 分支结点: 度大于零的结点 M

结点的层次: 树的深度： (从根到结点的)路径： 由从根到该结点所经分支和结点构成 孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点 A 由从根到该结点所经分支和结点构成 B C D E F G H I J 孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点 K L M 结点的层次: 假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1 树的深度： 树中叶子结点所在的最大层次

森林： 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林 是m（m≥0）棵互 A 是m（m≥0）棵互 不相交的树的集合 B C D E F G H I J K L M 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林

有向树： 有序树： 无序树： (１) 有确定的根； (２) 树根和子树根之间为有向关系。 子树之间存在确定的次序关系。 子树之间不存在确定的次序关系。

基本操作： 查 找 类 插 入 类 删 除 类

查找类： Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历

插入类： InitTree(&T) // 初始化置空树 CreateTree(&T, definition) // 按定义构造树 Assign(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树

删除类： DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树 ClearTree(&T) // 将树清空 DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树

§ 6.2 二叉树的定义

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。 A B E C F G D 左子树 H K

二叉树的五种基本形态： 只含根结点 空树 左右子树均不为空树 N 右子树为空树 左子树为空树 N N N L R L R

二叉树的主要基本操作： 查 找 类 插 入 类 删 除 类

查找类： LeftChild(T, e); RightChild(T, e); Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());

CreateBiTree(&T, definition); InsertChild(T, p, LR, c); 插入类： InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);

删除类： ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR);

§6.3 二叉树的性质 和存储结构 一、 二叉树的重要性质 二、二叉树的顺序存储表示 三、二叉树的链式存储表示 二叉树是非线性结构，该怎样存储？ 三、二叉树的链式存储表示

用归纳法证明： 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1) 归纳基： i = 1 层时，只有一个根结点： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点： 2i-1 = 20 = 1； 假设对所有的 j，1≤ j  i，命题成立； 二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-2 2 = 2i-1 。

性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。 证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+       +2k-1 = 2k-1 。

证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。

两类特殊的二叉树： 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。 3 4 5 6 7 8 9 10 11 12 13 14 15 完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。 1 a 3 2 b c 7 完全二叉树的特点：叶子结点只可能在层次最大的两层上出现； 对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1 4 5 6 d e f g j 8 9 10 10 h i j

性质 4 ： 具有 n 个结点的完全二叉树的深度为  log2n +1 。 证明： 利用第二条性质。

证明： …… …… …… 设完全二叉树的深度为 k 则根据第二条性质得 2k-1≤ n < 2k 1层 2层 …… …… …… K-1层 K层 设完全二叉树的深度为 k 则根据第二条性质得 2k-1≤ n < 2k 即 k-1 ≤ log2 n < k 因为 k 只能是整数，因此， k =log2n + 1 。

性质 5 ： 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点； (2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

证明： …… i i+1 2i 2i+1 2i+2 2i+3 (1) 当j=1时，其左孩子结点为2，右孩子结点为3，命题成立； (2) 假设j=i (i>1)时命题成立，即i结点的左孩子结点编号为2i，右孩子结点编号为2i+1; i+1 2i+2 2i+3 i 2i 2i+1 …… 当j=i+1时， 命题是否成立？

二、 二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_ TREE_SIZE]; // 0号单元存储根结点 SqBiTree bt;

例如: A 2 1 B D 4 3 E C 5 F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A B D C E F

A 2 1 B D 6 3 4 5 E C 11 12 9 10 13 8 7 F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A B D C E F

三、二叉树的链式存储表示 1. 二叉链表 3．双亲链表 4．线索链表 2．三叉链表

1. 二叉链表 root        结点结构: lchild data rchild A B D C E F 在n个结点的二叉链表中， 有n+1个空指针域   F

typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; 结点结构: lchild data rchild

静态二叉链表 A B D E C F 结点结构: lchild data rchild -1 B 1 -1 C -1 A 3 -1 D 4 1 2 3 4 5 6 -1 B 1 -1 C -1 A A 3 -1 D 4 B D 5 E -1 -1 F -1 E C F

typedef struct SBiTNode { // 结点结构 TElemType data; int lchild, rchild; // 左右孩子指针 } SBiTNode; 结点结构: lchild data rchild SBiTNode sBiTree[MaxSize]; //定义存储静态二叉链表的数组

2．三叉链表 root         结点结构: A B D C E F parent lchild data rchild  A   B D    C E   F

struct TriTNode *lchild, *rchild; // 左右孩子指针 typedef struct TriTNode { // 结点结构 TElemType data; struct TriTNode *lchild, *rchild; // 左右孩子指针 struct TriTNode *parent; //双亲指针 } TriTNode, *TriTree; 结点结构: parent lchild data rchild

3．双亲链表 结点结构: data parent LRTag L R 1 2 3 4 5 6 1 2 3 4 5 6 双亲链表是一种静态链表，找双亲容易，找孩子结点难

char LRTag; // 左、右孩子标志域 } BPTNode typedef struct BPTree{ // 树结构 typedef struct BPTNode { // 结点结构 TElemType data; int parent; // 指向双亲的指针 char LRTag; // 左、右孩子标志域 } BPTNode typedef struct BPTree{ // 树结构 BPTNode nodes[MAX_TREE_SIZE]; int num_node; // 结点数目 int root; // 根结点的位置 } BPTree

§ 6.4 二叉树的遍历

1、问题的提出 2、先左后右的遍历算法 3、算法的递归描述 4、遍历算法的非递归描述

1、问题的提出 顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次。 “访问”的含义可以很广，如：输出结 点的信息等。 二叉树的基本操作必须建立在对树结点能够“遍历”的基础上！

“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构， 每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。

对“二叉树”而言，可以有三条搜索路径： 1)．先上后下的按层次遍历； 2)．先左（子树）后右（子树）的遍历； 3)．先右（子树）后左（子树）的遍历。

2、先左后右的遍历算法 先（根）序的遍历算法 中（根）序的遍历算法 后（根）序的遍历算法

先（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。

先序遍历: 先序遍历序列：A B D C D L R D L R A A D B C D L R B D L R C > >

中（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。

中序遍历: 中序遍历序列：B D A C L D R A L D R A D B C L D R L D R B C > >

后（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。

后序遍历: 后序遍历序列： D B C A L R D A A L R D L R D C B > B > > C D

3、算法的递归描述 void Preorder (BiTree T, void Inorder (BiTree T, void( *visit)(TElemType& e)) { // 先序遍历二叉树 if (T) { visit(T->data); // 访问结点 Preorder(T->lchild, visit); // 遍历左子树 Preorder(T->rchild, visit);// 遍历右子树 } void Postorder (BiTree T, void( *visit)(TElemType& e)) { // 后序遍历二叉树 if (T) { Postorder(T->lchild, visit); // 遍历左子树 Postorder(T->rchild, visit);// 遍历右子树 visit(T->data); // 访问结点 } void Inorder (BiTree T, void( *visit)(TElemType& e)) { // 中序遍历二叉树 if (T) { Inorder(T->lchild, visit); // 遍历左子树 visit(T->data); // 访问结点 Inorder(T->rchild, visit);// 遍历右子树 }

四、遍历算法的非递归描述 分析： 1）遍历二叉树左右子树所采用的策略与遍历二叉树本身的策略是一样的； 2）进入子树进行遍历时，需保存根结点的信息； 3）当子树遍历完成时，根据保存的根结点信息找到右子树； 4）获取保存的根结点信息时，最后保存的根结点最先利用，因此采用栈结构存储根结点；

p p 例： p p A B C D E F p S p p p p C A D 中序遍历序列： B F C A E D

中序遍历算法的非递归描述 BiTNode *GoFarLeft(BiTree T, Stack *S){ if (!T ) return NULL; while (T->lchild ){ Push(S, T); T = T->lchild; } return T; }//找到最左端的叶结点

t = GoFarLeft(T, S); // 找到最左下的结点 while(t){ void Inorder_I(BiTree T, void (*visit) (TelemType& e)){ Stack *S; t = GoFarLeft(T, S); // 找到最左下的结点 while(t){ visit(t->data); if (t->rchild) t = GoFarLeft(t->rchild, S); else if ( !StackEmpty(S )) // 栈不空时退栈 t = Pop(S); else t = NULL; // 栈空表明遍历结束 } // while }// Inorder_I

while(p || !StackEmpty(S)){ void Inorder_II(BiTree T, void (*visit) (TelemType& e)){ InitStack(S); p = T; while(p || !StackEmpty(S)){ // 根指针进栈，遍历左子树 if (p){ Push(S, p); p = p->lchild; } else{ // 根指针退栈，访问根结点，遍历右子树 Pop(S,p); visit(t->data); p = p->rchild; } // else } // while }// Inorder_II

p 例： p p A B C D E F S p p p p F C B p A 中序遍历序列： B F C A E D

§6.5 遍历算法的应用举例 1、统计二叉树中叶子结点的个数 (先序遍历) 2、求二叉树的深度(后序遍历) 3、复制二叉树(后序遍历) 4、建立二叉树的存储结构

1、统计二叉树中叶子结点的个数 算法基本思想: 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。

void CountLeaf (BiTree T, int& count){ if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if } // CountLeaf

2、求二叉树的深度(后序遍历) 算法基本思想: 首先分析二叉树的深度和它的左、右子树深度之间的关系。 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。

int Depth (BiTree T ){ // 返回二叉树的深度 if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); } return depthval;

3、复制二叉树 (后序遍历) 其基本操作为：生成一个结点。 NEWT T 根元素 根元素 左子树 右子树 左子树 右子树 左子树 右子树

BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ){ 生成一个二叉树的结点 (其数据域为item,左指针域为lptr,右指针域为rptr) BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ){ if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(1); T-> data = item; T-> lchild = lptr; T-> rchild = rptr; return T; }

BiTNode *CopyTree(BiTNode *T) { if (!T ) return NULL; if (T->lchild ) newlptr = CopyTree(T->lchild);//复制左子树 else newlptr = NULL; if (T->rchild ) newrptr = CopyTree(T->rchild);//复制右子树 else newrptr = NULL; newT = GetTreeNode(T->data, newlptr, newrptr); return newT; } // CopyTree

例如：下列二叉树的复制过程如下： A B E C F G D H K newT A ^ B E ^ C ^ ^ F ^ ^ D ^ G

不同的定义方法相应有不同的存储结构的建立算法 4、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法

A(B( ,C( , )),D( , )) 以字符串的形式 根 左子树 右子树 定义一棵二叉树 例如: 以空白字符“ ”表示 空树 以字符串的形式 根 左子树 右子树 定义一棵二叉树 例如: 以空白字符“ ”表示 空树 以字符串“A ”表示 只含一个根结点的二叉树 A 以下列字符串表示 A A(B( ,C( , )),D( , )) B D C

Status CreateBiTree(BiTree &T) { scanf(&ch); if (ch==' ') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; // 生成根结点 CreateBiTree(T->lchild); // 构造左子树 CreateBiTree(T->rchild); // 构造右子树 } return OK; } // CreateBiTree

上页算法执行过程举例如下： A B C D A B C D T A B D ^ ^ ^ C ^ ^

仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 由二叉树的先序和中序序列建树 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列 根 左子树 右子树 二叉树的中序序列 左子树 根 右子树

a a b c d e f g a b c d e f g c c b d a e g f b d e g f 例如: ^ ^ ^ ^ ^ 先序序列中序序列 c c b d a e g f b d a e g f a b e ^ c d f ^ ^ ^ ^ ^ g ^ ^

§ 6.6 线索二叉树 何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？

一、何谓线索二叉树？ 遍历二叉树的结果是， 求得结点的一个线性序列。 例如: A 先序序列: A B C D E F G H K B E 中序序列: B D C A H G K F E C F G D 后序序列: D C B H K G F E A H K

包含 “线索” 的存储结构，称作 “线索链表” 指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索” A B C D E F G H K 包含 “线索” 的存储结构，称作 “线索链表” ^ B E ^ C ^ 与其相应的二叉树，称作 “线索二叉树” ^ D ^

对线索链表中结点的约定： 在二叉链表的结点中增加两个标志域， 并作如下规定： 若该结点的左子树不空， 则Lchild域的指针指向其左子树， 且左标志域的值为“指针 Link”； 否则，Lchild域的指针指向其“前驱”， 且左标志的值为“线索 Thread” 。

若该结点的右子树不空， 则rchild域的指针指向其右子树， 且右标志域的值为 “指针 Link”； 否则，rchild域的指针指向其“后继”， 且右标志的值为“线索 Thread”。 如此定义的二叉树的存储结构称作“线索链表”。

线索链表的类型描述： typedef enum { Link, Thread } PointerThr; typedef struct BiThrNod { TElemType data; struct BiThrNode *lchild, *rchild; // 左右指针 PointerThr LTag, RTag; // 左右标志 } BiThrNode, *BiThrTree;

二、线索链表的遍历算法: for ( p = firstNode(T); p; p = Succ(p) ) Visit (p); 由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。 for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);

例如: 对中序线索化链表的遍历算法 左子树上处于“最左下”（没有左子树）的结点。 若无右子树，则为后继线索所指结点； ※ 中序遍历的第一个结点 ？ 左子树上处于“最左下”（没有左子树）的结点。 ※ 在中序线索化链表中结点的后继 ？ 若无右子树，则为后继线索所指结点； 否则为对其右子树进行中序遍历时访问的第一个结点。

void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) { p = T->lchild; // p指向根结点 while (p != T) { // 空树或遍历结束时，p==T while (p->LTag==Link) p = p->lchild; // 第一个结点 while (p->RTag==Thread && p->rchild!=T) { p = p->rchild; Visit(p->data); // 访问后继结点 } p = p->rchild; // p进至其右子树根 } // InOrderTraverse_Thr

三、如何建立线索链表？ 在中序遍历过程中修改结点的 左、右指针域，以保存当前访问结 点的“前驱”和“后继”信息。遍历过 程中，附设指针pre, 并始终保持指 针pre指向当前访问的、指针p所指 结点的前驱。

void InThreading(BiThrTree p) { if (p) { // 对以p为根的非空二叉树进行线索化 InThreading(p->lchild); // 左子树线索化 if (!p->lchild) // 建前驱线索 { p->LTag = Thread; p->lchild = pre; } if (!pre->rchild) // 建后继线索 { pre->RTag = Thread; pre->rchild = p; } pre = p; // 保持 pre 指向 p 的前驱 InThreading(p->rchild); // 右子树线索化 } // if } // InThreading

Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { // 构建中序线索链表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode)))) exit (OVERFLOW); Thrt->LTag = Link; Thrt->RTag =Thread; Thrt->rchild = Thrt; // 添加头结点 return OK; } // InOrderThreading … …

if (!T) Thrt->lchild = Thrt; else { Thrt->lchild = T; pre = Thrt; InThreading(T); pre->rchild = Thrt; // 处理最后一个结点 pre->RTag = Thread; Thrt->rchild = pre; }

§ 6.7 树和森林 一、树的存储结构 二、树和森林的遍历

一、树的三种存储结构 1、双亲表示法 2、孩子链表表示法 3、树的二叉链表(孩子-兄弟） 存储表示法

1、双亲表示法: 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 A r=0 n=7 B C D E data parent 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 A r=0 n=7 B C D E F G

#define MAX_TREE_SIZE 100 C语言的类型描述: #define MAX_TREE_SIZE 100 结点结构: data parent typedef struct PTNode { Elem data; int parent; // 双亲位置域 } PTNode;

树结构: typedef struct { PTNode nodes [MAX_TREE_SIZE]; int r, n; // 根结点的位置和结点个数 } PTree;

2、孩子链表表示法: A 0 A 1 B 2 C 3 D 4 E 5 F 6 G -1 2 4 B C D E F r=0 n=7 G data firstchild A 0 A 1 B 2 C 3 D 4 E 5 F 6 G -1 2 4 1 2 3 B C D 4 5 E F 6 r=0 n=7 G

typedef struct CTNode { int child; struct CTNode *next; } *ChildPtr; 孩子结点结构: child next typedef struct CTNode { int child; struct CTNode *next; } *ChildPtr;

双亲结点结构 typedef struct { Elem data; ChildPtr firstchild; // 孩子链的头指针 data firstchild typedef struct { Elem data; ChildPtr firstchild; // 孩子链的头指针 } CTBox;

树结构: typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; // 结点数和根结点的位置 } CTree;

3、树的二叉链表 (孩子-兄弟）存储表示法 root A B C E D F G A B C D E F G A B C E D F G

typedef struct CSNode{ Elem data; struct CSNode 结点结构: firstchild data nextsibling typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;

B =( LBT, Node(root), RBT ); 森林和二叉树的对应关系 设森林 F = ( T1, T2, …, Tn ); T1 = (root，t11, t12, …, t1m); 二叉树 B =( LBT, Node(root), RBT );

由森林转换成二叉树的转换规则为: 若 F = Φ，则 B = Φ； 否则， 由 ROOT( T1 ) 对应得到 Node(root)； 由 (t11, t12, …, t1m ) 对应得到 LBT； 由 (T2, T3,…, Tn ) 对应得到 RBT。

由二叉树转换为森林的转换规则为： 若 B = Φ， 则 F = Φ； 否则， 由 Node(root) 对应得到 ROOT( T1 )； 由LBT 对应得到 ( t11, t12, …，t1m)； 由RBT 对应得到 (T2, T3, …, Tn)。

例：森林转换成二叉树 A B C D E F G H I A B C D E F G H I

例：二叉树转换成森林 A B C D A B C D E F G H I E F G H I

应当注意的是，和树对应的二叉树，其左、右子树的概念 由此，树的各种操作均可对应二叉树的操作来完成。 应当注意的是，和树对应的二叉树，其左、右子树的概念 已改变为： 左是孩子，右是兄弟。

二、树和森林的遍历 1、树的遍历 2、森林的遍历

树的遍历可有三条搜索路径: 先根(次序)遍历: 后根(次序)遍历: 按层次遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 若树不空，则先依次后根遍历各棵子树，然后访问根结点。 按层次遍历: 若树不空，则自上而下自左至右访问树中每个结点。

先根遍历时顶点的访问次序： A B C D E F G H I J K A B E F C D G H I J K 后根遍历时顶点的访问次序： E F B C I J K H G D A 层次遍历时顶点的访问次序： A B C D E F G H I J K

B C D E F G H I J K 森林由三部分构成： 1．森林中第一棵树的根结点； 2．森林中第一棵树的子树森林； 3．森林中其它树构成的森林。

森林的遍历 若森林不空，则 1. 先序遍历 访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林； 先序遍历森林中(除第一棵树之外)其 余树构成的森林。 1. 先序遍历 即：依次从左至右对森林中的每一棵树进行先根遍历。

２．中序遍历 若森林不空，则 中序遍历森林中第一棵树的子树森林； 访问森林中第一棵树的根结点； 中序遍历森林中(除第一棵树之外)其 余树构成的森林。 即：依次从左至右对森林中的每一棵树进行后根遍历。

例：森林的遍历 B C D 先序遍历序列： E F G H I J K 中序遍历序列： B E F C D G H I J K E F B C I J K H G D

树的遍历和二叉树遍历的对应关系 ？ 树 森林 二叉树 先根遍历 先序遍历 先序遍历 后根遍历 中序遍历 中序遍历

二叉树的应用 平衡树—— 排序树—— 字典树—— 判定树—— 带权树—— 最优树—— 特点：左右子树深度差 ≤1 特点：“左小右大” 由字符串构成的二叉树排序树 例如，12个球只称3次分出轻重 特点：路径长度带权值 带权路径长度最短的树，又称 Huffman树，用途之一是通信中的压缩编码。

§ 6.8 赫 夫 曼 树 与 赫 夫 曼 编 码 最优树的定义 如何构造最优树 前缀编码

结点的路径长度定义为： 从根结点到该结点的路径上 分支的数目。 树的路径长度定义为： 树中每个结点的路径长度之和。 树的带权路径长度定义为： 一、最优树的定义 结点的路径长度定义为： 从根结点到该结点的路径上 分支的数目。 树的路径长度定义为： 树中每个结点的路径长度之和。 树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点)。

WPL(T)= 72+52+23+43+92 =60 WPL(T)= 74+94+53+42+21 =89 例如： 2 7 9 WPL(T)= 72+52+23+43+92 =60 WPL(T)= 74+94+53+42+21 =89

在所有含 n 个叶子结点、 并带相同权值的 m 叉树中， 必存在一棵其带权路径长度 取最小值的树， 称为“最优树”。

二、如何构造最优树 (赫夫曼算法) 以二叉树为例： 根据给定的 n 个权值 {w1, w2, …, wn}， (1) (赫夫曼算法) 以二叉树为例： 根据给定的 n 个权值 {w1, w2, …, wn}， 构造 n 棵二叉树的集合 F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树； (1)

在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和； (2)

从F中删去这两棵树，同时加入 刚生成的新树； (3) 重复 (2) 和 (3) 两步，直至 F 中只 含一棵树为止。 (4)

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

9 7 13 5 2 6 7 29 1 13 16 1 1 6 7 9 7 1 00 01 10 5 2 110 111

三、前缀编码 指的是，任何一个字符的编码都 不是同一字符集中另一个字符的编码 的前缀。 利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。

例1：设有4个字符d,i,a,n，出现的频度分别为7,5,2, 4，怎样编码才能使它们组成的报文在网络中传得最快？ 方法1：等长编码。例如用二进制编码来实现。 取 d=00，i=01，a=10，n=11 方法2：不等长编码，例如用哈夫曼编码来实现。 取 d=0，i=10，a=110，n=111 最快的编码是哪个？ 是非等长的Huffman码！ 怎样实现Huffman编码？ 先要构造Huffman树！

didandd didandd didandd 方法1：等长编码。例如用二进制编码来实现。 00010010110000 取 d=00，i=01，a=10，n=11 didandd 00010010110000 方法2：不等长编码。 取 d=0，i=10，a=110，n=111 didandd 010011011100 取 d=0，i=10，a=100，n=101 didandd 010010010100 最快的编码是哪个？ 是非等长的Huffman编码！ 怎样实现Huffman编码？ 先要构造Huffman树！

霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。由于霍夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。 例2：假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方案又如何？ 解：先将概率放大100倍，以方便构造哈夫曼树。 权值集合 w={7, 19, 2, 6, 32, 3, 21, 10}，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。

为清晰起见，重新排序为: w={2, 3, 6, 7, 10, 19, 21, 32} 1 哈夫曼树 21 19 40 32 60 × 1 100 1 哈夫曼树 为清晰起见，重新排序为: w={2, 3, 6, 7, 10, 19, 21, 32} 21 19 40 32 60 × 1 1 w1={5, 6, 7, 10, 19, 21, 32} × 28 1 w2={7, 10, 11, 19, 21, 32} × b c a d e g f h 17 11 10 7 w3={11, 17, 19, 21, 32} × 1 1 w4={19, 21, 28, 32} × 6 2 3 5 1 w5={28,32,40} × w6={40,60} × w7={100}

　1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 　2. 熟悉二叉树的各种存储结构的特点及适用范围。 　3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。

　　4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。

　5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 　6. 学会编写实现树的各种操作的算法。 　7. 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。