Tree & Binary Tree

树的类型定义 n(n≥0)个元素的有限集合

基 本 术 语

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

孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点 (从根到结点的)路径 由从根到该结点所经分支和结点构成 A B C D E F G H I J K L M 孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点

结点的层次 树的深度 假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1 树中叶子结点所在的最大 层次 A B C D E F G H I J K L M 结点的层次 假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1 树的深度 树中叶子结点所在的最大 层次

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

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

结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点 兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(level) 树的高度(depth) 树的度(degree)

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

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

树的抽象数据类型定义

数据对象 D D是具有相同特性的数据元素的集合

数据关系 R 1.若D为空集，则称为空树 2.在D中存在唯一的称为根的数据元素 root 3.当n>1时，其余结点可分为m (m>0)个 互不相交的有限集T1, T2, …, Tm，其中 每一棵子集本身又是一棵符合本定义 的树，称为根root的子树

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

查找类 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棵子树

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

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

二叉树的类型定义

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

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

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

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)

二叉树的分类 完全二叉树 丰满二叉树 排序二叉树 平衡二叉树

满二叉树：指的是深度为k且含有2k-1个结点的二叉树 3 5 4 6 7 完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应 9 10 11 12 13 14 15 8 a b c d e f g h i j

二叉树 的重要特性

性 质 1 　在二叉树的第i(i≥1)层上至多有 2i-1 个结点

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

性 质 2 深度为k（k≥1）的二叉树上至多 含2k-1 个结点

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

性 质 3 对任何一棵二叉树，若它含有n0 个 叶子结点、n2 个度为2的结点，则必存 在关系式：n0 = n2+1

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

性 质 4 　具有n个结点的完全二叉树的深度 为log2n +1

证明 设完全二叉树的深度为 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的结点为 其右孩子结点

树的存储结构 一、广义表表示法 二、双亲表示法 三、孩子表示法 四、孩子兄弟表示法

广义表表示法 树的广义表表示 (结点的utype域没有画出)

双亲表示法 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 A D B C E F G data parent 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 A D B C E F G

孩子链表表示法 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4 A B C D E F G data firstchild 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4 1 2 3 A 4 5 B C D E F 6 G

孩子兄弟表示法 root A B C E D F G A B C D A B C E D F G E F G

孩子兄弟表示法 data firstChild nextSibling

二叉树的存储结构 一、二叉树的顺 序存储表示 二、二叉树的链 式存储表示

顺序存储表示 完全二叉树的 一般二叉树的 数组表示 数组表示

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

由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况

二叉链表 root 结点结构 lchild data rchild A   B D    C E   F

链表表示

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

二叉链表的静态结构

森林与二叉树 的转换

森林转化成二叉树 的规则

 若F为空，即n = 0，则 对应的二叉树B为空二叉树  若F不空，则 对应二叉树B的根root(B)是F中第 一棵树T1的根root(T1)，其左子树为 B(T11, T12, …, T1m)，其中，T11, T12, …, T1m是root(T1)的子树；其右子 树为B(T2, T3, …, Tn)，其中，T2, T3, …, Tn是除T1外其它树构成的森林

二叉树转换为森林 的规则

 如果B为空，则对应的森林F也为空  如果B非空，则 F中第一棵树T1的根为root；T1的根 的子树森林(T11, T12, …, T1m ) 是由 root的左子树LB转换而来，F 除了T1 之外其余的树组成的森林(T2, T3, …, Tn )是由root的右子树RB转换而成的 森林

森林与二叉树的转换

(Binary Tree Traversal) 二叉树遍历 (Binary Tree Traversal)

问题的提出 顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次 “访问”的含义可以很广，如：输出结 点的信息等

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

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

设 访问根结点 记作 V 遍历根的左子树 记作 L 遍历根的右子树 记作 R 则可能的遍历次序有 前序 VLR 逆前序 VRL 中序 LVR 逆中序 RVL 后序 LRV 逆后序 RLV 层次遍历

前序遍历 (Preorder Traversal) 若二叉树为空，则空操作 否则 访问根结点(V) 前序遍历左子树(L) 前序遍历右子树(R) 遍历结果 - + a * b - c d / e f

中序遍历 (Inorder Traversal) 若二叉树为空，则空操作 否则 中序遍历左子树(L) 访问根结点(V) 中序遍历右子树(R) 遍历结果 a + b * c - d - e / f 表达式语法树

后序遍历 (Postorder Traversal) 若二叉树为空，则空操作 否则 后序遍历左子树(L) 后序遍历右子树(R) 访问根结点(V) 遍历结果 a b c d - * + e f / -

层次遍历(Levelorder Traversal) 从上到下，从左到右 遍历结果 - ＋／a* e f b -cd

按给定的表达式建相应二叉树 由前缀表达式建树 例如: -×+abc/de 由中缀表达式建树 例如：(a+b)×c–d/e 由后缀表达式建树

对应前缀表达式 -×+abc/de 的二叉树 - × / + c d e 特点： 操作数为叶子结点 运算符为分支结点 a b

对应中缀表达式 (a+b)×c-d/e 的二叉树 - × / + c d e 特点： 操作数为叶子结点 运算符为分支结点 a b

对应后缀表达式 ab+c×de/- 的二叉树 - × / + c d e 特点： 操作数为叶子结点 运算符为分支结点 a b

+ + + / + 分析表达式和二叉树的关系 a+b (a+b)×c × c a b b a a+b×c (a+b)×c – d/e - ×

二叉树的计数 由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树 由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树 　　由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树 　　由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树 　　由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树

仅知二叉树的先序序列“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 先序序列中序序列 ^ ^ ^

前序序列{ABHFDECKG} 中序序列{HBDFAEKCG}

　如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树

　　问题是有n个数据值，可能构造多少种不同的二叉树？ 　　我们可以固定前序排列，选择所有可能的中序排列

有 3 个数据 { 1, 2, 3 }，可得5种不同的二叉树。它们的前序排列均为123，中序序列可能是 123，132，213，231，321

　有0个, 1个, 2个, 3个结点的不同二叉树如下

计算具有n个结点的不同二叉树的棵数 Catalan函数 具有4个结点的不同二叉树

树　的　遍　历 深度优先遍历 树的先根次序遍历 树的后根次序遍历 广度优先遍历 树的层次次序遍历

先根遍历 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 1．森林中第一棵树的根结点 E F G H I J K 2．森林中第一棵树的子树森林 3．森林中其它树构成的森林

森林的先根遍历 若森林F为空, 返回 否则: 访问F的第一棵树的根结点 先根次序遍历第一棵树的子树森林 先根次序遍历其它树组成的森林 森林的二叉树表示

森林的后根遍历 若森林F为空，返回 否则: 后根次序遍历第一棵树的子树森林 后根次序遍历其它树组成的森林 访问F的第一棵树的根结点 森林的二叉树表示

森林的层次遍历 若森林F为空，返回 否则: 依次遍历各棵树的根结点 依次遍历各棵树根结点的所有子女 依次遍历这些子女结点的子女结点 森林的二叉树表示

二叉树的类定义

template <class Type> class BinTreeNode { private: BinTreeNode<Type> *LChild,*RChild; Type data; }; class BinaryTree { BinTreeNode<Type> *root; };

二叉树前序遍历递归算法 template <class Type> void BinaryTree<Type>:: PreOrder(BinTreeNode<Type>*current) { if ( current != NULL ) { cout << current→data; PreOrder ( current→LChild ); PreOrder ( current→RChild ); } }

二叉树中序遍历递归算法 template <class Type> void BinaryTree <Type>:: InOrder(BinTreeNode<Type>*current) { if ( current != NULL ) { InOrder ( current→LChild ); cout << current→data; InOrder ( current→RChild ); } }

二叉树后序遍历递归算法 template <class Type> void BinaryTree<Type>:: PostOrder(BinTreeNode<Type>*current) { if ( current != NULL ) { PostOrder ( current→LChild ); PostOrder ( current→RChild ); cout << current→data; } }

二叉树前序遍历 非递归算法

template <class Type> void BinaryTree<Type>:: PreOrder(BinTreeNode<Type> *p ) { do { while ( p != NULL ) { cout << p→data; Push ( s, p ); p = p→LChild; } if ( !Empty ( s ) ) { p = pop ( s ); p = p→RChild; } }while ( ( !Empty ( s ) ) || ( p != NULL ) ) }

二叉树中序遍历 非递归算法

template <class Type> void BinaryTree<Type>:: PreOrder(BinTreeNode<Type> *p ) { do { while ( p != NULL ) { Push ( s, p ); p = p→LChild; } if ( !Empty ( s ) ) { p = pop ( s ); cout << p→data; p = p→RChild; } }while ( ( !Empty ( s ) ) || ( p != NULL ) ) }

应用二叉树遍历的事例

计算二叉树结点个数的一种方法 template <class Type> int BinaryTree<Type>:: Size ( BinTreeNode <Type> *t ) { if ( t == NULL ) return 0; else return 1 + Size ( t→LChild ) + Size ( t→RChild ); }

计算二叉树的高度 template <class Type> int BinaryTree<Type>:: Depth ( BinTreeNode <Type> *t ) { if ( t == NULL ) return 0; else return 1+ Max( Depth( t→LChild ), Depth( t→RChild ) ); }

线索二叉树

遍历二叉树的结果是， 求得结点的一个线性序列 A 先序序列 B A B C D E F G H K E F C 中序序列 B D C A H G K F E 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 ^

对线索链表中结点的约定 在二叉链表的结点中增加两个标志域 LTag和RTag,并作如下规定: 若该结点的左子树不空， 则LChild域的指针指向其左孩子， 且左标志LTag的值为0 否则，LChild域的指针指向其“前驱”， 且左标志LTag的值为1

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

LTag = 0, LChild为指针,指向左孩子 LTag = 1, LChild为线索,指向前驱 RTag = 0, RChild为指针,指向右孩子 RTag = 1, RChild为线索,指向后继

猜一猜,是哪一种线索二叉树

前序序列 A B D C E 后序序列 D B E C A

带表头结点的中序线索二叉树

寻找当前结点 在中序下的后继

if (pRTag==1) if (pRChild!=T.root) 后继为 pRChild else 无后继 else //pRTag==0 后继为当前结点右 子树的中序下的第 一个结点 else 出错情况 A B C D E F G H I J K L

寻找当前结点 在中序下的前趋

if (pLTag==1) if (pLChild!=T.root) 前驱为pLChild else 无前驱 else //pLTag==0 前驱为当前结点左 子树的中序下的最 后一个结点 else 出错情况 A B C D F E H I G K J L

在前序线索化二叉树中寻找当前结点的后继

在前序线索化二叉树中寻找当前结点的前趋

在后序线索化二叉树中寻找当前结点的后继

在后序线索化二叉树中寻找当前结点的前趋

堆 ( Heap ) 优先级队列 每次出队列的是优先权最高的元素 template <class Type> class MinPQ { public: Virtual void Insert ( const Type & ) = 0; Virtual Type *RemoveMin ( Type & ) = 0; } 最小优先级队列类的定义

Ki  K2i+1 && Ki  K2i+1 && Ki  K2i+2 Ki  K2i+2 堆的定义 完全二叉树的数组表示

最小堆的类定义 template <class Type> class MinHeap : public MinPQ <Type> { public: MinHeap ( int maxSize ) const; MinHeap ( Type arr[ ], int n ); ~MinHeap ( ) { delete [ ] heap; } const MinHeap<Type> & operator = ( const MinHeap &R ); int Insert ( const Type &x ); int RemoveMin ( Type &x ); int IsEmpty ( ) const { return CurrentSize == 0; }

int IsFull ( ) const { return CurrentSize == MaxHeapSize; } void MakeEmpty ( ) { CurrentSize = 0; } private: enum { DefaultSize = 10 }; Type *heap; int CurrentSize; int MaxHeapSize; void FilterDown ( int i, int m ); void FilterUp ( int i ); }

堆的建立 template <class Type> MinHeap <Type>:: MinHeap ( int maxSize ) { //根据给定大小maxSize,建立堆对象 MaxHeapSize = DefaultSize < maxSize ? maxSize : DefaultSize; //确定堆大小 heap = new Type [MaxHeapSize]; //创建堆空间 CurrentSize = 0; //初始化 } MinHeap ( Type arr[ ], int n ) { //根据给定数组中的数据和大小,建立堆对象

MaxHeapSize = DefaultSize < n ? n : DefaultSize; heap = new Type [MaxHeapSize]; heap = arr; //数组传送 CurrentSize = n; //当前堆大小 int currentPos = (CurrentSize-2)/2; //最后非叶 while ( currentPos >= 0 ) { //从下到上逐步扩大,形成堆 FilterDown ( currentPos, CurrentSize ); //从currentPos开始,到CurrentSize为止, 调整 currentPos--; }

将一组用数组存放的任意数据调整成堆 自下向上逐步调整为最小堆

最小堆的向下调整算法 template <class Type> void MinHeap<Type>:: FilterDown ( const int start, const int EndOfHeap ) { int i = start, j = 2*i+1; // j 是 i 的左子女 Type temp = heap[i]; while ( j <= EndOfHeap ) { if ( j < EndOfHeap && heap[j].key > heap[j+1].key ) j++; //两子女中选小者 if ( temp.key <= heap[j].key ) break; else { heap[i] = heap[j]; i = j; j = 2*j+1; } } heap[i] = temp;

堆的插入 template <class Type> int MinHeap<Type>:: Insert ( const Type &x ) { //在堆中插入新元素 x if ( CurrentSize == MaxHeapSize ) //堆满 { cout << "堆已满" << endl; return 0; } heap[CurrentSize] = x; //插在表尾 FilterUp (CurrentSize); //向上调整为堆 CurrentSize++; //堆元素增一 return 1; }

template <class Type> void MinHeap<Type>:: FilterUp ( int start ) { //从 start 开始,向上直到0,调整堆 int j = start, i = (j-1)/2; // i 是 j 的双亲 Type temp = heap[j]; while ( j > 0 ) { if ( heap[i].key <= temp.key ) break; else { heap[j] = heap[i]; j = i; i = (i -1)/2; } } heap[j] = temp;

最小堆的向上调整

template <class Type> int MinHeap <Type>:: RemoveMin ( Type &x ) { if ( !CurrentSize ) { cout << “ 堆已空 " << endl; return 0; } x = heap[0]; //最小元素出队列 heap[0] = heap[CurrentSize-1]; CurrentSize--; //用最小元素填补 FilterDown ( 0, CurrentSize-1 ); //从0号位置开始自顶向下调整为堆 return 1; }

哈 夫 曼 树 (Huffman Tree) 与 哈 夫 曼 编 码

设给出一段报文 CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 } 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36

若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度 A : 0 T : 10 C : 110 S : 111 它的总编码长度为 7*1+5*2+( 2+4 )*3 = 35 比等长编码的情形要短

结点间路径长度(Path Length) 连接两结点的路径上的分支数 结点的路径长度 从根结点到该结点的路径上分 支的数目

树的路径长度 树中每个结点的路径长度之和 树的带权路径长度 (Weighted Path Length,WPL) 树的各叶结点所带的权值与该 结点到根的路径长度的乘积的 和

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

具有不同带权路径长度的二叉树 哈夫曼树中，权值大的结点离根最近

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 4 7 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 个权值 {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 7 6

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

哈夫曼树的构造过程

哈夫曼树的构造过程

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

设给出一段报文 CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 } 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36

以各字符出现概率{2,7,4,5}为各叶结点权值，建立哈夫曼树，得哈夫曼编码(不等长编码) A:0 T:10 C:110 S:111 总编码长度为 7*1+5*2+(2+4)*3=35 总编码长度正好等 于哈夫曼树的带 权路径长度WPL

在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。 哈夫曼树的应用 （1）判定树 在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。 例1 将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的，可用图（a)二叉树结构来实现。 a<60 a<70 a<80 a<90 不及格 中等 良好 优秀 及格 Y N (a) 输入10000个数据，则需进行31500次比较。

10000个学生成绩转换成五分制的判定 500*1+1500*2+4000*3+3000*4+1000*4 =31500 分数 0-59 60-69 70-79 80-89 90-100 比例数 0.05 0.15 0.40 0.30 0.10 A<60 500*1+1500*2+4000*3+3000*4+1000*4 =31500 Y N A<70 不及格 Y N 及格 A<80 N Y 中等 A<90 Y N 良好 优秀

学生成绩分布不是均匀的情况： Y N Y N (c) (b) 分数 0—59 60—69 70—79 80—89 90—99 比例 0.05 0.15 0.4 0.3 0.10 70≤a< 80 a<60 及格 中等 良好 80≤a<90 60≤a<70 不及格 优秀 Y N 以比例数为权构造一棵哈夫曼树，如（b)判断树所示。 输入10000个数据，仅需进行22000次比较。 再将每一比较框的两次比较改为一次，可得到（c)判定树。 不及格 Y a<90 a<80 a<70 a<60 优秀 中等 及格 良好 N (c) (b)

用此形式比较次数为： 500*3+1500*3+4000*2+3000*2+1000*2=22000 A<80 Y N A<70 中等 良好 优秀 Y N 不及格 及格 用此形式比较次数为： 500*3+1500*3+4000*2+3000*2+1000*2=22000

（2）哈夫曼编码-----利用哈夫曼树构造通讯中电文编码（前缀码） 例2：要传输的电文是{CAS；CAT；SAT；AT} 要传输的字符集是 D={C，A，S，T， ；} 每个字符出现的频率是W={ 2，4， 2，3， 3 } 各字符编码是 T ； A C S       00 01 10 110 111 上述电文编码： 11010111011101000011111000011000 14 6 8 3 4 2 1 T ; A C S 方法： （1）用{ 2，4， 2，3， 3 }作为叶子结点的权值生成一棵哈夫曼树，并将对应权值wi的叶子结点注明对应的字符； （2）约定左分支表示字符“0”，右分支表示字符‘1’ （3）从叶子结点开始，顺着双亲反推上去，直到根结点，路径上的‘0’或‘1’连接的序列就是结点对应的字符的二进制编码的逆序。 例2：哈夫曼树用于电文编码 要传输的电文是{CAS；CAT；SAT；AT} 要传输的字符集是 D={C，A，S，T， ；} 每个字符出现的频率是W={ 2，4， 2，3， 3 } 以带权字符为叶子结点建立哈夫曼树，得到各字符编码是 T ； A C S 00       01 10 110 111 上述电文编码：11010111011101000011111000011000 其总长度为32，恰好等于哈夫曼树的带权路径长。可见哈夫曼编码是使电文具有最短长度的二进制编码。 注意：编码的总长度恰好为哈夫曼树的带权路径长。

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

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

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