Chapter 06 Tree and binary tree 第六章 树和二叉树

Presentation on theme: "Chapter 06 Tree and binary tree 第六章 树和二叉树"— Presentation transcript:

1 Chapter 06 Tree and binary tree 第六章 树和二叉树
Prof. Qing Wang

2 本章学习的线索 主要线索 重点 难点 树和二叉树的定义及表示 二叉树的遍历 树、森林和二叉树的转换 哈夫曼树和哈夫曼编码
二叉树的遍历及线索化 树和二叉树 的定义和 表示 二叉树的遍历（递归和非递归）及线索化 树、森林和 二叉树的转换 哈夫曼树和哈夫曼编码 Prof. Q. Wang

3 Contents Definition and notations of Tree and Forest
Notations and representation of binary tree Binary tree traversal Threading binary tree Reconstruction of binary tree Transformation among Tree, Forest and binary tree Huffman tree and Huffman coding Prof. Q. Wang

4 6.1 Definition and notations of Tree
6.1.1 Definition of Tree A tree is a set of n nodes. If n=0, it is a NULL tree. If n>0, then 1. It has a so-called “root” node which only has successors and without predecessor. 2. Except the root, the remainders can be partitioned into m (m>0) un-overlapped subsets T1,T2,…, Tm, each of which is also a tree. They are called the sub-trees of the root. Note: The root of the tree has no predecessor and 0~m successors (sub-trees). Prof. Q. Wang

5 基本操作： InitTree(&T); DestroyTree(&T); CreateTree(&T); ClearTree(&T);
TreeEmpty(T); TreeDepth(T); Root(T); Value(T, cur_e); Assign(T, cur_e, value); Parent(T, cur_e); LeftChild(T, cur_e); RightSibling(T, cur_e); InsertChild(&T, &p, i, c); DeleteChild(&T, &p, i); TravseTree(T, visit()); ADT描述参见课本 pp118 Prof. Q. Wang

6 Representations of tree
Tree form Representations of tree A B C D E F G H I J K L M General list form (A(B(E(K,L),F), C(G), D(H(M),I,J)) Wen Graph I J F K L G M C H D B E A Retraction form A B D E I J F C G H Prof. Q. Wang

7 6.1.2 Notations Node (结点)：包含一个数据元素及若干指向其子树的分支。
Leaf (树叶)、Branch node(分支结点) Parent node (父结点)、child node(子结点) Edge (边) ：父结点x到子结点y的有序对 <x,y> Sibling (兄弟) ：同一双亲的孩子 Ancestor (祖先) 、offspring (子孙)： 堂兄弟：双亲在同一层的结点 Layer (结点的层数、树的层数)：规定根的层数为1 Degree (结点的度、树的度)：结点拥有的子树数目 Depth (树的高度或深度)：树中结点的最大层次称为树的深度 Path and Path length (路径和路径长度) A B C D E F G H I J K L Prof. Q. Wang

8 Examples 1 2 3 4 Prof. Q. Wang

9 6.1.3 Forest (Orchard) A set of trees. 森林是m (m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。 就逻辑结构而言，任何一棵树是一个二元组Tree=(root, F)，其中root称为树的根结点；F是m (m>=0)棵子树构成的森林，F=(T1, T2,…,Tm), 其中Ti=(ri, Fi)称作根root的第i棵子树；当m0时，在树根和其子树森林之间存在下列关系: 由这个定义，可以得到森林和二叉树之间转换的递归定义。 RF={<root, ri> | i=1,2,…,m, m>0} Prof. Q. Wang

10 6.1.4 Basic functions for the tree
树的基本运算通常有以下几种： 1. Initialization - 创建一棵空树； 2. IsEmpty - 判断某棵树是否为空； 3. GetRoot - 求树中的根结点，若为空树，则返回一特殊值； 4. GetParent - 求树中某个指定结点的父结点，当指定结点为根时，返回一特殊值； 5. GetFirstChild - 求树中某个指定结点的最左子结点，当指定结点为树叶时，它没有子女，则返回一特殊值； 6. GetRightSibling - 求树中某个指定结点的右兄弟结点，当指定结点没有右兄弟时，返回一特殊值； 7. Traversal - 树的遍历（周游），即按某种方式访问树中的所有结点，并使每个结点恰好被访问一次。 Prof. Q. Wang

11 Discussion Storage design of tree General list Prof. Q. Wang

12 Discussion Storage design of tree Fixed multiple-branch list
Number of branch：tree’s degree Null Pointer？ Variable multiple-branch list Number of branch：node’s degree data child1 child2 child3 childd Prof. Q. Wang

13 6.2 Binary tree 6.2.1 Basic notations
二叉树的5种基本形态： ADT描述参见课本 pp121。 Prof. Q. Wang

14 InitBiTree(&T); DestroyBiTree(&T); CreateBiTree(&T, definition); ClearBiTree(&T); BiTreeEmpty (T); BiTreeDepth(T); Root(T); Value(T, e); Assign(T, e,value); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); InsertChild(T, p, LR, c); DeleteChild(T, p, LR); PreOrderTravse(T, visit()); InOrderTravse(T, visit()); PostOrderTravse(T, visit()); LevelOrderTravse(T, visit()); ADT描述参见课本 pp121 Prof. Q. Wang

15 Examples of binary tree
Binary tree = (Root, Left sub-binary-tree, Right sub-binary-tree) Prof. Q. Wang

16 ★ ★ 完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。
二叉树不是树的特殊情形，尽管树和二叉树的概念之间有许多类似，但它们是两个概念。树和二叉树之间最主要的差别是： Full binary tree (满二叉树)：如果一棵二叉树的任何结点或者是树叶，或有两棵结构完全相同的非空子树，则此二叉树称作“满二叉树” 。 Complete binary tree (完全二叉树)：如果一棵二叉树至多只有最下面的两层结点度数可以小于2（度为1的结点只能在倒数第二层），并且最下面一层的结点（叶子）都集中在该层最左边的若干位置上，则此二叉树称为“完全二叉树”。完全二叉树不一定是满二叉树。 ★ 二叉树中结点的子树要区分为左子树和右子树，即使在结点 只有一棵子树的情况下也要明确指出该子树是左子树还是右 子树。 ★ 完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。 Prof. Q. Wang

17 Generic binary tree 1 Generic binary tree 2 Full binary tree
D E F G H I A B C D E F G H I Generic binary tree 1 Generic binary tree 2 A B C F G D E H I J A B C F G D E Full binary tree Complete binary tree Prof. Q. Wang

18 6.2.2 Characteristics of binary tree
(1) Suppose that binary tree is leveled from 1, there are at most 2i-1 nodes at the level i (i1). 在二叉树的第i层上至多有2i-1个结点（i  1）。 可以用归纳法证明。 (2) If the height of binary tree is k (k  1), the number of nodes is at most 2k-1. 深度为k的二叉树至多有2k-1个结点（k>=1）。 Level 1 20 Level 2 21 2k-1 Level 3 22 Level k 2k-1 Prof. Q. Wang

19 6.2.2 Characteristics of binary tree
(3) In binary tree, if the number of leaves is n0, and the number of nodes with left and right children is n2, then n0＝n2＋1 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 证明： 设n1为二叉树中度为1的结点数。则有， n=n0+n1+n2 再看二叉树中的分支数。除了根结点外，其余结点都有一个分支指向它，设B为分支总数，则n=B+1。由于这些分支都是由分支为1或2的结点发出的，因此有： B=n1+2n2 于是有 n=n1+2n2+1 n1+2n2+1=n0+n1+n2 => n0=n2+1 Prof. Q. Wang

20 (4) The depth of the complete binary tree with n nodes is
证明：假设完全二叉树的深度为k，则根据性质2和完全二叉树的定义有 2k-1-1< n <= 2k 或 k-1 <= n < 2k 于是 k-1<=log2n < k 因k是整数，所以 Prof. Q. Wang

21 (5) 如果对一棵有n个结点的完全二叉树按层序从1开始编号，则对任一结点i（1<=i<=n)，有：
a) 如果i=1, 则结点i是二叉树的根, 无双亲; 如果i>1, 则其双亲结点是 i/2 ; b) 如果2i>n, 则结点i无左孩子；否则其左孩子是结点2i; c) 如果2i+1>n, 则结点i无右孩子；否则其右孩子是结点2i+1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 Prof. Q. Wang

22 Extended binary tree (扩充二叉树 )：
对一个二叉树进行“扩充”，可得到扩充的二叉树。扩充的方法是： 把原二叉树的结点都变为度数为2的分支结点，也就是说，如果原结点的度数为2，则不变，度数为1，则增加一个分支，度数为0 (树叶)增加两个分支。 在扩充的二叉树里外部结点 (叶结点)都是新增加的结点。如果原二叉树有n个结点，在扩充的二叉树里这n个结点的度数都是2。因此扩充的二叉树有2n条边，2n+1个结点，除n个原来二叉树结点，还有n+1个是新增加的外部结点，也就是说：在扩充的二叉树里，新增加的外部结点的个数比原来的内部结点个数多1。 a b c d e f 1 2 3 4 6 7 5 a b c d e f Prof. Q. Wang

23 “外部路径长度”E：在扩充的二叉树里从根到每个外部结点的路径长度之和。
“内部路径长度”I：在扩充的二叉树里从根到每个内部结点的路径长度之和。 Example: I= =9 E= =21, n=6 关系： E = I + 2n 请证明上述关系式。 a b c d e f 1 2 3 4 6 7 5 Prof. Q. Wang

24 6.2.3 Basic functions for binary tree
二叉树的基本运算通常有以下几种： 1. Initialization - 创建一棵空二叉树； 2. IsEmpty - 判断某棵二叉树是否为空； 3. GetRoot -求二叉树中的根结点，若为空二叉树，则返回一特殊值； 4. GetParent - 求二叉树中某个指定结点的父结点，当指定结点为根时，返回一特殊值； 5. GetLeftChild - 求二叉树中某个指定结点的左子女结点，当指定结点没有左子女时，返回一特殊值； 6. GetRightChild - 求二叉树中某个指定结点的右子女结点，当指定结点没有右子女时，返回一特殊值； 7. Traversal - 二叉树的遍历，即按某种方式访问二叉树中的所有结点，并使每个结点仅仅被访问一次。 Prof. Q. Wang

25 6.3 Storage of Binary Tree 6.3.1 Sequential form
用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树的结点。对于一般树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。 A B C D E F G A B C D E F G 顺序表 A B C D E F G Prof. Q. Wang

26 #define MAXNODE 100 /* 定义二叉树中结点的最大个数 */
//Declaration #define MAXNODE /* 定义二叉树中结点的最大个数 */ typedef struct SeqBTree /* 顺序二叉树类型定义 */ { DataType nodelist[MAXNODE+1]; int n; /* 改造成完全二叉树后，结点的个数 */ }SeqBTree, *PSeqBTree; Prof. Q. Wang

27 6.3.2 Linked form 由二叉树的定义可知，二叉树的结点由一个数据元素和两个分支构成，因此在表示时，至少需要包含三个域：数据域和左、右指针域。如果想能够找到父结点，则可以增加一个指向父结点的指针域。利用这两种结点结构所得的二叉树存储结构分别称为二叉链表和三叉链表。 //Declaration typedef struct BinTreeNode { DataType info; struct BinTreeNode *lchild; struct BinTreeNode *rchild; }BinTreeNode, *PBinTreeNode, BinTree, *PBinTree; Prof. Q. Wang

28 Example Prof. Q. Wang

29 Static tri-branch linked list
Prof. Q. Wang

30 Quick Review Tree and Binary tree Binary tree ADT
Concepts and notations Binary tree Physical form: bi-branch linked list Complete binary tree  Sequential list 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 … 11 12 Prof. Q. Wang

31 6.4 Traversal of binary tree
6.4.1 Definition of Traversal Traversing Binary Tree (二叉树的遍历)：按某条搜索路径访问树中每一个结点，使得每个结点被访问且仅被访问一次 (once and only once)。 Depth-first traversal (深度优先)： 由于二叉树是由根结点和左右子树构成的，因此访问时就可以有6种访问顺序。如果限定访问从左到右进行，则只有三种情况，分别称为先根次序 (先序)、中根次序 (中序)、后根次序 (后序)，相应的输出序列称为先序、中序和后序序列。 Level-first traversal (按层次遍历)： Prof. Q. Wang

32 Expression: a-b/c+d Fig.1 (a-b)/(c+d) Fig.2 a-(b/c+d) Fig.3 a-b/c+d
＋ / d a b c d b c Fig.1 (a-b)/(c+d) Fig.2 a-(b/c+d) + - - d a / a / b + b c c d Fig.3 a-b/c+d Fig.4 a-b/(c+d) Prof. Q. Wang

33 从上图我们可以看出，二叉树表示一个算术表达式。二叉树的每一个子树对应一个子表达式，而且二叉树的左右次序也对应了表达式的运算次序。
对图1进行先根、后根和中根次序的遍历得到如下的结点序列: 先根：/-ab+cd 后根：ab-cd+/ 中根：a-b/c+d 这些序列分别称为表达式的前缀表示法、后缀表示法 (逆波兰表示法) 和中缀表示法。逆波兰表示法可以简化表达式的计算(why?) / - a b ＋ c d Fig.1 (a-b)/(c+d) Prof. Q. Wang

34 6.4.2 Traversal algorithms Recursive algorithms (递归算法)
InOrderTraverse (中序遍历) PreOrderTraverse (先序遍历) PostOrderTraverse (后序遍历) Non-recursive algorithms (非递归算法) LevelOrderTraverse (按层次遍历) Prof. Q. Wang

35 Inorder traversal a + b * c - d - e / f Framework of Inorder traversal
If binary tree T is NULL, NULL operation else 1) Inorder traverse the left sub-tree 2) Visit the root 3) Inorder traverse the right sub-tree The result of Inorder traversal is a + b * c - d - e / f Syntax tree of expression Prof. Q. Wang

36 Recursive Inorder Traversal
Status InOrderTraverse (PBinTree T, Status (*Visit)(ElemType e)) { if (T){ InOrderTraverse (T->lchild, Visit); (*Visit)(T-> info); InOrderTraverse (T->rchild, Visit); } int PrintElement (ElemType e) printf (e); return OK; Prof. Q. Wang

37 a + b * c - d - e / f Recursive tree of Inorder traversal 1 2 8 3 4 10
6 5 9 7 11 a + b * c - d - e / f Prof. Q. Wang

38 Preorder traversal - + a * b - c d / e f
Framework of Preorder traversal If binary tree T is NULL, NULL operation else 1) Visit the root 2) Preorder traverse the left sub-tree 3) Preorder traverse the right sub-tree The result of Preorder traversal is - + a * b - c d / e f Syntax tree of expression Prof. Q. Wang

39 Recursive Preorder Traversal
Status PreOrderTraverse (PBinTree T, Status (*Visit)(ElemType e)) { if (T){ (*Visit)(T-> info); PreOrderTraverse (T->lchild, Visit); PreOrderTraverse (T->rchild, Visit); } int PrintElement (ElemType e) printf (e); return OK; Prof. Q. Wang

40 Postorder traversal a b c d - * + e f / -
Framework of Postorder traversal If binary tree T is NULL, NULL operation else 1) Postorder traverse the left sub-tree 2) Postorder traverse the right sub-tree 3) Visit the root The result of Postorder traversal is a b c d - * + e f / - Syntax tree of expression Prof. Q. Wang

41 Recursive Postorder Traversal
Status PostOrderTraverse (PBinTree T, Status (*Visit)(ElemType e)) { if (T){ PostOrderTraverse (T->lchild, Visit); PostOrderTraverse (T->rchild, Visit); (*Visit) (T-> info); } int PrintElement (ElemType e) printf (e); return OK; Prof. Q. Wang

42 Other recursive algorithm of binary tree
1. Get the number of nodes of a binary tree (求二叉树的结点个数) int count ( PBinTree T ) { if ( !T ) return 0; else return 1 + count ( T->lchild ) + count ( T->rchild ); } Prof. Q. Wang

43 Other recursive algorithm of binary tree
2. Get the depth of a binary tree (求二叉树的深度) int depth (PBinTree T) { if ( !T ) return 0; else return 1+Max{depth ( T->lchild ) , depth ( T->rchild ) }; } Prof. Q. Wang

44 Initialization of binary tree via PreOrder
Input：Get the character sequentially A B C Ø Ø D E Ø G Ø Ø F Ø Ø Ø int CreateBinTree (PBinTree T ) //按先序次序构造二叉链表 { scanf(&ch); if ( ch == ‘Ø’ ) T = NULL; else { if ( !(T = (PBinTree) malloc(sizeof(BinTreeNode)))) exit(-1); T -> info = ch; CreateBinTree (T->lchild); CreateBinTree (T->rchild); } A B C D E F G A B C Ø Ø D E Ø G Ø Ø F Ø Ø Ø Prof. Q. Wang

45 Non-recursive traversal algorithm 二叉树遍历的非递归算法
★ ★ 先序遍历的基本思想： 遇到一个结点，访问之，接着把压入栈中，然后去遍历它的左子树。遍历完它的左子树后，从栈顶弹出这个结点，然后再去遍历它的右子树。 ★ 中序遍历的基本思想： 遇到一个结点，就把它压入栈中，去遍历它的左子树，遍历它的左子树后，从栈顶弹出这个结点并访问之，然后再去遍历它的右子树。 对于先根遍历，可以通过适当判断减少进出栈的次数：访问一个结点之后，仅当该结点左、右子树都不空时才把结点的右子女压进栈。这样可以节省算法的时间与空间开销。 Prof. Q. Wang

46 ptr //Preorder Traversal struct StackNode { PBinTree ptr; };
void PreOrderTraverse (PBinTree T ) { Stack S; PBinTree p; StackEmpty( S ); p = T; do { while ( p ) { printf ( p->info); Push( S, p ); p = p->lchild; } if ( !IsEmpty( S ) ) { p = getTop( S ); Pop( S ); p = p->rchild; } while ( p || !IsEmpty( S ) ); struct StackNode { PBinTree ptr; }; ptr Prof. Q. Wang

47 先序遍历中栈的变化 Stack state in PreOrderTraversal - - + - + a - + - - * - * b
Prof. Q. Wang

48 先序遍历中栈的变化 Stack state in PreOrderTraversal - - d - / / e / f 栈空
Prof. Q. Wang

49 ptr //Inorder Traversal void InOrderTraverse (PBinTree T ) {
Stack S; PBinTree p; StackEmpty( S ); p = T; do { while ( p ) { Push( S, p ); p = p->lchild; } if ( !IsEmpty( S ) ) { p = getTop( S ); Pop( S ); printf ( p->info); p = p->rchild; } while ( p || !IsEmpty( S ) ); ptr Prof. Q. Wang

50 - - + - + a - + - - * - * b - * - - - c -
Stack state in InOrderTraversal 中序遍历中栈的变化 - - + - + a - + - - * - * b - * - - - c - Prof. Q. Wang

51 Stack state in InOrderTraversal 中序遍历中栈的变化
- - d - / / e / f 栈空 Prof. Q. Wang

52 需要考虑二次进栈！！！ 后序遍历的基本思想是：
后序非递归算法比较复杂，每个结点要到它们左、右子树都遍历完时才得以访问，所以在去遍历它的左、右子树之前都需要进栈。 当它出栈时，需要判断是从左子树回来（即刚遍历完左子树，此时需要去遍历右子树），还是从右子树回来（即刚遍历完右子树，此时需要去访问这个结点）。因此，进栈的结点需要伴随着一个标记tag 。 L 表明遍历它的左子树 tag = R 表明遍历它的右子树 需要考虑二次进栈！！！ Prof. Q. Wang

53 typedef struct StackNode {
enum tag { L, R }; PBinTree ptr; } StackNode; ptr tag (LR) 后序遍历根为 T 的二叉树, 存储结构为二叉链表, S 是存储所经过二叉树结点的工作栈。其中, tag 是结点标记。当 tag＝L 时, 表示刚才是在左子树中, 从左子树退出时, 还要去遍历右子树。当 tag ＝R 时, 表示刚才是在右子树中, 在从右子树中退出时, 去访问位于栈顶的结点。 Prof. Q. Wang

54 //Postorder Traversal void PostOrderTraverse (PBinTree T ) {
Stack S; PBinTree p; StackNode w; StackEmpty( S ); p = T; do { while ( p ) { w.ptr = p; w.tag = L; Push( S, w); p = p->lchild; } - + a L - + a L R - + L - + L R Prof. Q. Wang

55 while ( continue && ! IsEmpty( S ) ) { w = getTop( S ); Pop( S );
int continue = 1; while ( continue && ! IsEmpty( S ) ) { w = getTop( S ); Pop( S ); p = w.ptr; switch (w.tag) { case L : w.tag = R; Push( S, w); continue = 0; p = p->rchild; break; case R : printf (p->info); } } while ( p || !IsEmpty( S ) ); 二次进栈 Prof. Q. Wang

56 Stack state in InOrderTraversal 后序遍历中栈的变化
- L - + L - + a L - + a L R - + a L R - + L - + L R - + L R * b - + L R * b - + L R * b - + L R * - + L R * c - + L R * c - + L R * c - + L R * d - + L R * - + L R * - + L R * Prof. Q. Wang

57 Stack state in InOrderTraversal 后序遍历中栈的变化
- + L R * d - + L R * d - + L R * - + L R * - + L R - R - R / L - R / L e - R / L e - R / L e - R / L - R / - R / f L - R / f - R / f - R / - R 栈空 Prof. Q. Wang

58 Quick Review Structure of binary tree Traversal of binary tree
Binary linked list Traversal of binary tree Recursive algorithms Non-recursive algorithms Prof. Q. Wang

59 LevelOrderTraversal From the root, visit the node
from the top to the bottom, and from the left to the right at the same level. Queue involved Prof. Q. Wang

60 //Level order Traversal void LevelOrderTraverse (PBinTree T ) {
Queue qu; PBinTree p; if ( !T ) { printf( “End of level order traversal!\n”); return; } EnQueue ( qu, T ); while ( !empty( qu ) ) { DeQueue ( qu, p ); printf ( p->info ); //DeQueue & output if ( p->lchild != NULL ) //Left child EnQueue ( qu, p->lchild ); //EnQueue if ( p->rchild != NULL ) //Right child EnQueue ( qu, p->rchild ); //EnQueue struct QueueNode { PBinTree ptr; }; Prof. Q. Wang

61 Analysis of binary tree traversal
Time complexity (时间复杂度) O(n) Space complexity (空间复杂度) Depth-first methods (深度优先的方法) O(栈的深度) Level-first method (按层次遍历) n: number of binary tree nodes (二叉树的结点个数) Prof. Q. Wang

62 void Postorder(PBinTree t){ Stack s;
PBinTreeNode p; /* 周游时当前要处理结点的位置 */ char flag; /* 结点p的标志量 */ char continueflag; /* 表明是否要继续退栈，当从右子树返回 时，则要在访问完根之后继续退栈 */ ElemType elem; if (t == NULL) return; InitStack(&s); p = t; /* 从根结点开始 */ do{ /* 每执行一次大循环进入一棵由p指出根的子树去周游 */ while (p != NULL) /* 反复地把遇到的结点进栈并进入 它的左子树 */ { elem.ptr = p; elem.tag = '1'; Push(&s, elem); p = p->llink; } continueflag = '1'; Prof. Q. Wang

63 while ( continueflag == '1' && !IsStackEmpty(s)) { Pop(&s, &elem);
p = elem.ptr; if (elem.tag == ‘1’) /* 如果是从左子树回来，则 改标志重新进栈，停止退栈并进入右子树 */ elem.tag = 'r'; Push(&s, elem); continueflag = '0'; p = p->rlink; } else visit(p->info); } while (!IsStackEmpty(s)); /* 栈为空时，全部周游完 */ DestroyStack(&s); Prof. Q. Wang

64 6.4.3 Reconstruction of Binary Tree
★ ★ Problem 1 Given a binary tree, is Preorder sequence, or Inorder sequence, or Postorder sequence Unique? Problem 2 Given a preorder sequence of BT, can you reconstruct an unique binary tree? How about Inorder sequence, postorder sequence? Prof. Q. Wang

65 Problem 3 Given preorder and inorder sequences of BT, can you reconstruct this binary tree? Preorder: abcd; Inorder: badc; Given postorder and inorder sequences of BT, can you reconstruct this binary tree? Postorder: bdca; Inorder: badc; Given preorder and postorder sequences of BT, can you reconstruct this binary tree? Preorder: abcd; Postorder: dcba; Prof. Q. Wang

66 Example ABECDFGHIJ EBCDAFHIGJ
Suppose that the preorder sequence of BT is ABECDFGHIJ and the inorder sequence of BT is EBCDAFHIGJ try to reconstruct this binary tree. Prof. Q. Wang

67 Preorder sequence: ABECDFGHIJ Inorder sequence: EBCDAFHIGJ
Prof. Q. Wang

68 Preorder sequence: ABECDFGHIJ Inorder sequence: EBCDAFHIGJ
Prof. Q. Wang

69 6.4.4 Counting of BT ★ ★ 123456789 Problem (问题)
给你一个二叉树的先序遍历序列，问具有这样先序序列的二叉树有多少棵？ Prof. Q. Wang

70 Example (1) 123 132 213 231 321 For example, { 1, 2, 3 }
Preorder sequence 123 Inorder traversed sequences are 123, 132, 213, 231, and 321. 123 132 213 231 321 Prof. Q. Wang

71 Example (2) n=0, 1, 2, 3, 4 Prof. Q. Wang

72 Conclusion bi bn-i-1 Prof. Q. Wang

73 定义生成函数 由于 Prof. Q. Wang

74 Prof. Q. Wang

75 Questions Prof. Q. Wang

76 Questions Prof. Q. Wang

77 6.4 Traversal of binary tree
6.4.1 Definition of Traversal Traversing Binary Tree (二叉树的遍历)：按某条搜索路径访问树中每一个结点，使得每个结点被访问且仅被访问一次 (once and only once)。 Depth-first traversal (深度优先)： 由于二叉树是由根结点和左右子树构成的，因此访问时就可以有6种访问顺序。如果限定访问从左到右进行，则只有三种情况，分别称为先根次序 (先序)、中根次序 (中序)、后根次序 (后序)，相应的输出序列称为先序、中序和后序序列。 Level-first traversal (按层次遍历)： Prof. Q. Wang

78 Preorder sequence: ABECDFGHIJ Inorder sequence: EBCDAFHIGJ
Prof. Q. Wang

79 6.5 Threading binary tree 遍历二叉树是按一定的规则将二叉树中结点排列成一个线性序列，这实际上是把一个非线性结构进行线性化的操作。 以二叉链表作为存储结构时，对于某个结点只能找到其左右孩子，而不能直接得到结点在任一序列中的前驱或后继。要想得到，只能通过遍历的动态过程才行。 怎样保存遍历过程中得到的信息呢？ Prof. Q. Wang

80 (1) 增加两个指针，分别指示其前驱和后继结点
predecessor successor pre suc rchild lchild info Prof. Q. Wang

81 struct ThrTreeNode *lchild; struct ThrTreeNode *rchild;
/* 线索树中每个结点的结构 */ { DataType info; struct ThrTreeNode *lchild; struct ThrTreeNode *rchild; struct ThrTreeNode *pre; struct ThrTreeNode *suc; }ThrTree, *PThrTree, *PThrTreeNode; root suc B D A E C pre Prof. Q. Wang

82 (2) 利用结构中的空链域，并设立标志，即采用如下的形式
rtag rchild lchild info ltag Prof. Q. Wang

83 struct ThrTreeNode /* 线索树中每个结点的结构 */ { DataType info;
struct ThrTreeNode *lchild, *rchild; int ltag, rtag; }ThrTree, *PThrTree, *PThrTreeNode; 其中当ltag或rtag为0时，llink或rlink为指针；否则为1时，llink或rlink表示线索。 Prof. Q. Wang

84 线索链表：以上面结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。
线索：指向结点前驱或后继的指针叫做线索。 线索二叉树：加上线索的二叉树叫线索二叉树。 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。 Prof. Q. Wang

85 Question (1) In an InOrderThreading binary tree, where is
The predecessor of a given node The successor of a given node Prof. Q. Wang

86 1) 若右标志是1，则右链为线索，指示其后继；
在中序线索二叉树中找结点的后继 在中序线索树中找结点后继的规律是： 1) 若右标志是1，则右链为线索，指示其后继； 2) 否则，遍历该结点的右子树时访问的第一个结点(右子树中最左下的结点)为其后继。 - NULL + + NULL a * e f b - c d Prof. Q. Wang

87 1) 若左标志是1，则左链为线索，指示其前驱；
在中序线索二叉树中找结点的前驱 在中序线索树中找结点前驱的规律是： 1) 若左标志是1，则左链为线索，指示其前驱； 2) 否则，遍历该结点的左子树时最后访问的结点(左子树中最右下的结点)为其前驱。 - NULL + + NULL a * e f b - c d Prof. Q. Wang

88 √ √ Other questions (2) In PreOrderThreading tree,
The successor of the given node The predecessor of the given node In PostOrderThreading tree √ √ Prof. Q. Wang

89 (1) 若结点x是二叉树的根，则其前驱为空; (2) 若结点x是其双亲的左孩子或是右孩子且其双亲没有左子树，则其前驱即为双亲结点。
可分三种情况： (1) 若结点x是二叉树的根，则其前驱为空; (2) 若结点x是其双亲的左孩子或是右孩子且其双亲没有左子树，则其前驱即为双亲结点。 (3) 若结点x是其双亲的右孩子，且其双亲有左子树，则其前驱为双亲的左子树上按先序遍历出的最后一个结点。 H D G A C F B E 前驱线索 由此可见，在先序线索化树上找前驱时也需知道结点的双亲，因此需要使用三叉链表。 Prof. Q. Wang

90 (1) 若结点x是二叉树的根，则其后继为空; (2) 若结点x是其双亲的右孩子或是左孩子且其双亲没有右子树，则其后继即为双亲结点。
后继线索 可分三种情况： (1) 若结点x是二叉树的根，则其后继为空; (2) 若结点x是其双亲的右孩子或是左孩子且其双亲没有右子树，则其后继即为双亲结点。 (3) 若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历出的第一个结点。 H D G A C F B E 由此可见，在后序线索化树上找后继时需知道结点的双亲，因此需要使用三叉链表。 Prof. Q. Wang

91 - + a * b c d e f 如何中序遍历中序线索二叉树？
可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度也是O(n)，但常数因子小，且不需要设栈，因此若在某程序中需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作存储结构。 - + a * b c d e f NULL 如何中序遍历中序线索二叉树？ Prof. Q. Wang

92 中序遍历中序线索二叉树 void InOrderTravse_Thr (PThrTree t) { PThrTreeNode p;
if ( !t ) return ; p = *t; while (p->lchild!=NULL && p->ltag==0) /* 顺左子树一直向下 */ p = p->lchild; while ( !p ) { visit(p); /* 访问该结点 ，printf(p->info);*/ if ( p->rchild && p->rtag==0) { /* 右子树不是线索时 */ p = p->rchild; while ( p->lchild && p->ltag==0) p = p->lchild; /* 顺右子树根结点的左子树一直向下 */ } else p = p->rchild; /* 顺线索向下 */ Prof. Q. Wang

93 二叉树的中序线索化 原理 递归算法 非递归算法 在遍历的过程中，修改二叉树中原有的n+1个空指针
必备的辅助存储，设置一个指针*pre始终指向刚刚访问过的结点 递归算法 非递归算法 Prof. Q. Wang

94 Status InOrderTraverse (PBinTree T, Status (*Visit)(ElemType e))
{ if (T){ InOrderTraverse (T->lchild, Visit); (*Visit)(T-> info); InOrderTraverse (T->rchild, Visit); } 中序遍历 void InThreading (PThrTree p, PThrTree *pre) { if (p) { InThreading (p->lchild, pre); if (!p->lchild) { p->ltag = 1; p->lchild = *pre;} if (!(*pre)->rchild) {(*pre)->rtag = 1; (*pre)->rchild = p;} *pre = p; InThreading (p->rchild, pre); } 中序线索化 Prof. Q. Wang

95 - + a * b c d e f *pre=null BT p - + / a * e f b - c d Prof. Q. Wang

96 - + a * b c d e f *pre=null BT - p + / a * e f b - c d Prof. Q. Wang

97 - + a * b c d e f *pre=null BT - + / p a * e f b - c d Prof. Q. Wang

98 - + a * b c d e f BT - + / p 1 a * e f b - *pre=null c d Prof. Q. Wang

99 - + a * b c d e f BT - p + / *pre 1 a 1 * e f b - c d Prof. Q. Wang

100 - + a * b c d e f BT *pre - + p / 1 a 1 * e f p b - c d Prof. Q. Wang

101 - + a * b c d e f BT *pre - + / 1 a 1 * e f p 1 b - c d Prof. Q. Wang

102 - + a * b c d e f p *pre BT - + / 1 a 1 * e f 1 b 1 - c d
- + p / 1 a 1 * e f *pre 1 b 1 - c d Prof. Q. Wang

103 - + a * b c d e f *pre p BT - + a * e f b - c d / 1 1 1 1 1
- *pre + / 1 a 1 * e f 1 b 1 - p 1 c d Prof. Q. Wang

104 - + a * b c d e f NULL thrt 1 BT - + / 1 a 1 * 1 e 1 1 f 1 1 b 1 - 1 c
1 BT - + / 1 a 1 * 1 e 1 1 f 1 1 b 1 - 1 c 1 1 d 1 Prof. Q. Wang

105 递归算法 void InThreading (PThrTree p, PThrTree *pre) { if (p) {
InThreading (p->lchild, pre); if (!p->lchild) { /* If left child is NULL, let it point to its previous node */ p->ltag = Thread; p->lchild = *pre; } if (!(*pre)->rchild) { /* 如果前驱的右指针空，则让它指向当前结点 */ (*pre)->rtag = Thread; (*pre)->rchild = p; *pre = p; InThreading (p->rchild, pre); } /* End of InThreading() */ 递归算法 Setup Threading Prof. Q. Wang

106 InOrderThreading (二叉树的中序线索化递归算法)
enum tag {Link, Thread}; Status InOrderThreading (PThrTree *Thrt, PThrTree BT) { /* Threading the Binary Tree, let Thrt point to the head node */ PThrTree pre; /* point to the previous node */ /* 创建头结点 */ *Thrt = (PThrTree *) malloc (sizeof(PThrTree )); (*Thrt)->ltag = Link; (*Thrt)->rtag = Thread; (*Thrt)->rchild = *Thrt; /* 右指针指向头结点 */ if (!BT) (*Thrt)->lchild = *Thrt; /* 树空，则让其左指针指向头结点*/ Prof. Q. Wang

107 (*Thrt)->lchild = BT; pre = *Thrt; InThreading (BT, &pre);
else { (*Thrt)->lchild = BT; pre = *Thrt; InThreading (BT, &pre); /* 线索化后，pre指向二叉树的最后一个结点*/ pre->rchild = *Thrt; /* 最后一个结点的右指针指向头结点。 */ pre->rtag = Thread; (*Thrt)->rchild = pre; /* 头结点的右指针指向最后一个结点*/ } return OK; } /* End of InOrderThreading() */ Prof. Q. Wang

108 InOrderThreading (二叉树的中序线索化非递归算法)
void thread (PThrTree t) { Stack S; /*栈元素的类型为PThrTreeNode*/ PThrTreeNode p; /*指向当前正在访问的结点*/ PThrTreeNode pre; /*指向p的中序前驱结点*/ if ( !t ) return ; StackEmpty( S ); p = *t; pre = NULL; do { while ( p ) /* 遇到结点入栈,然后处理其左子树 */ Push( S, p ); p = p->lchild; } Prof. Q. Wang

109 p = getTop( S ); Pop( S ); while ( !p && !IsEmpty( S ) ) /* 左子树处理完,
{ 从栈顶退出结点并访问 */ p = getTop( S ); Pop( S ); if ( !pre) { if ( pre->rchild == NULL) /* 检查前驱结点的右指针 */ { pre->rchild = p; pre->rtag = 1; } if ( !p->lchild) /* 检查该结点的左指针 */ { p->lchild = pre; p->ltag = 1; pre = p; p = p->rchild; /* 处理右子树 */ } while ( p || !IsEmpty( S ) ); Setup Threading Prof. Q. Wang

110 ★ ★ ★ 非形式地说，中序线索二叉树里的线索总是指向二叉树中更高层的结点，也就是说是“向上”指的 (如下图） 。
利用这个“向上”指的线索我们还可以在中序线索二叉树里找出指定结点在先根下的后继结点和后根下的前驱结点。 thrt ★ A ★ ★ B E 1 C 1 D 1 F G 1 H 1 K Prof. Q. Wang

111 1) 当一个结点有左子树时，其先根的后继为它的左子树的根结点； 2) 当一个结点没有左子树但有右子树时，其先根的后继为它的右子树的根结点；
对于先根的后继： 1) 当一个结点有左子树时，其先根的后继为它的左子树的根结点； 2) 当一个结点没有左子树但有右子树时，其先根的后继为它的右子树的根结点； 3) 当一个结点为叶子结点时，先根顺序的后继恰好为其中序下右线索所指结点的右子树的根结点。 A B E 1 C D F G H K thrt Prof. Q. Wang

112 1) 当一个结点有右子树时，其后根的前驱为它的右子树的根结点； 2) 当一个结点没有右子树但有左子树时，其后根的前驱为它的左子树的根结点；
对于后根的前驱： 1) 当一个结点有右子树时，其后根的前驱为它的右子树的根结点； 2) 当一个结点没有右子树但有左子树时，其后根的前驱为它的左子树的根结点； 3) 当一个结点为叶子结点时，后根顺序的前驱恰好为其中序下左线索所指结点的左子树的根结点。 A B E 1 C D F G H K thrt Prof. Q. Wang

113 Question 在中序线索二叉树中，如何找先序下的前驱和后序下的后继结点？
在先序、中序和后序线索二叉树中插入一个结点，或者删除一个结点，二叉树中的线索将如何维护？ 主要研究中序线索二叉树。 Prof. Q. Wang

114 6.6 Representation of tree and forest
6.6.1 Storage of Tree (1) Parent method (双亲表示法) 用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。结构类型如下： typedef struct ParTreeNode /* 树中结点结构 */ { DataType info; /* 结点中的元素 */ int parent; /* 结点的父结点位置 */ }ParTreeNode; typedef struct ParTree ParTreeNode nodelist[MAXNUM]; int n; }ParTree, *PParTree; Prof. Q. Wang

115 改进的方法是按一种遍历次序在数组中存放结点。其中较常见的一种方法是依次存放树的先根序列，如图：
在这种表示中，容易找到父结点及其所有的祖先；也能找到结点的子女和兄弟（虽然比较麻烦）。但它没有表示出结点之间的左右次序，所以无法求树中某个指定结点的最左子结点和右兄弟结点等基本运算。 改进的方法是按一种遍历次序在数组中存放结点。其中较常见的一种方法是依次存放树的先根序列，如图： a b c d e h i j f g info parent a -1 b e d 1 h 3 i j c f 7 g 2 4 5 6 8 9 Prof. Q. Wang

116 (2) Sub-list method (子表表示法)
结点表中的每一元素又包含一个子表，存放该结点的所有子结点。结点表顺序存放，子表用链接表示，子表中的元素按从左到右的次序存放。结构类型如下： typedef struct EdgeNode /* 子表中结点的结构 */ { int node_position; struct EdgeNode *link; }EdgeNode; typedef struct ChiTreeNode /* 结点表中结点的结构 */ DataType info; struct EdgeNode *children; }ChiTreeNode; Prof. Q. Wang

117 typedef struct ChiTree /* 树结构 */ { ChiTreeNode node_list[MAXNUM];
int root; /* 根结点的位置 */ int n; /* 结点的个数 */ }ChiTree, *PChiTree; info children a b c d e h i j f g a 1 7 1 b 2 3 2 d 3 e 4 5 6 4 h 5 i 6 j 7 c 8 9 8 f 9 g Prof. Q. Wang

118 (3) Left-child right-sibling method (左孩子右兄弟表示法)
typedef struct CSNode { DataType info; struct CSNode *lchild; struct CSNode *rsibling; }CSTree, *PCSTree; t a b c d e h i j f g a b c d e f g h i j Prof. Q. Wang

119 (1) Parent method (双亲表示法)
Storage of Forest (1) Parent method (双亲表示法) info parent A -1 B K C 2 D E 4 H 5 F J 7 G 1 3 6 8 9 A B C H D E F G K J Prof. Q. Wang

120 (2) Sub-list form (子表表示法)
info children A B K C D E H F J G 1 2 3 4 5 6 7 8 9 A B C H D E F G K J Prof. Q. Wang

121 (3) Left-child right-sibling method (左孩子右兄弟表示法)
A D B C E F G K H J A B C H D E F G K J Prof. Q. Wang

122 6.7 Traversal of Tree and Forest
1 6.7.1 Traversal of Tree 2 3 4 1. Definition of traversal (遍历的定义) 2. Traversal methods (遍历的方法) （1）深度方向（以右图为例） a. 先根次序 (1, 2, 3, 5, 8, 9, 6, 10, 4, 7) b. 后根次序 (2, 8, 9, 5, 10, 6, 3, 7, 4, 1) （2）广度方向 层次序列 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10） 5 6 7 8 9 10 Prof. Q. Wang

123 6.7.2 Traversal of forest (森林的遍历)
1. PreOrder 先序 (A, B, C, K, D, E, H, F, J, G) 2. InOrder 中序 (B, K, C, A, H, E, J, F, G, D) A B C H D E F G K J Prof. Q. Wang

124 6.8 Conversion among Tree, Forest and Binary tree
6.8.1 Tree, Forest  Binary tree 由于树和二叉树都可以用二叉链表作存储结构，则以二 叉链表作媒介可以导出树与二叉树之间的一个对应关系。 A A B A B C E C B D C D E D E Prof. Q. Wang

125 如果F＝{T1, T2, …, Tm}是森林，则可按如下规则转换成一棵二叉树B＝{root, LB, RB}。
从二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。这样，若把森林中第二棵树的根结点看成是第一棵树的兄弟，则可以导出森林和二叉树之间的对应关系。 1. 森林转换成二叉树 如果F＝{T1, T2, …, Tm}是森林，则可按如下规则转换成一棵二叉树B＝{root, LB, RB}。 (1) 若F为空，则B为空树； (2) 若F非空，则B的根root为森林中第一棵树的根Root(T1)，B的左子树LB是从T1中根结点的子树森林F1＝{T11, T12 ,…, T1m1}转换而成的二叉树；其右子树RB是从森林F’＝{T2, T3, … , Tm}转换而成的二叉树。 Prof. Q. Wang

126 如果B＝{root, LB, RB} 是一棵二叉树，则可按如下规则转换成森林F＝{T1, T2, …, Tm}
2. 二叉树转换成森林 如果B＝{root, LB, RB} 是一棵二叉树，则可按如下规则转换成森林F＝{T1, T2, …, Tm} (1) 若B为空，则F为空树； (2) 若B非空，则为森林中第一棵树的根Root(T1)即为 B的根root， T1中根结点的子树森林F1＝{T11, T12,…, T1m1} 是由B的左子树LB转换而来的森林；F中除T1之外的其余树组成的森林F’＝{T2, T3, … , Tm}是由B的右子树转换而成的。 根据上述递归定义很容易写出相互转换的递归算法。森林和树的操作也可转换成二叉树的操作来实现。 把树和森林转换成对应的二叉树的直观方法：凡是兄弟就用线连起来，然后去掉父母到子女的连线，只留下父母到其第一个子女的连线。 Prof. Q. Wang

127 Tree  Binary tree A B C E F D A B C E F D Prof. Q. Wang

128 Forest  Binary tree A B C H D E F G K J A B D A D C E B E F G C K H F
Prof. Q. Wang

129 6.9 Huffman tree and coding
Background if (a<60) b=‘E’; else if (a<70) b=‘D’; else if (a<80) b=‘C’; else if (a<90) b=‘B’; else b=‘A’; a<60 31500次比较 Y N E a<70 N Y D a<80 Y N C a<90 Y N B A Prof. Q. Wang

130 a<80 Y N 70≤a<80 a<70 a<90 Y N Y N Y N C 80≤a<90
B A Y N Y N B 60≤a<70 E D N Y 22000次比较 a<60 D Y N Prof. Q. Wang E A

131 1. Definition of Huffman tree (定义及构造方法)
在6.2中我们介绍了扩充二叉树及其外部路径长度的概念。用Ｅ表示某扩充二叉树的外部路径长度。则有： 其中 li 为从根到外部结点的路径长度，m为外部结点的个数。 如果给每个外部结点ki赋一个实数wi作为“权”，则将 记作“带权的外部路径长度”。 现要构造一棵以wi (i = 1, 2, …, m)为权的m个外部结点的扩充的二叉树，使得带权的外部路径长度最小。满足这一要求的扩充二叉树也称为“哈夫曼树”，也叫最优二叉树。 Prof. Q. Wang

132 Path length of binary tree
PL= =13 PL= =14 Prof. Q. Wang

133 In general Minimum Prof. Q. Wang

134 Weighted path length of binary tree
WPL=( )*2=36 WPL=2*1+4*2+(5+7)*3=46 WPL=7*1+5*2+(2+4)*3=35 Prof. Q. Wang

135 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
Prof. Q. Wang

136 Huffman algorithm (1) 根据给定的n个权值{w1, w2, …, wn}，构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每一棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。 (2) 在F中选取两棵权值最小的树作为左右子树构造一棵新的二叉树，且新二叉树的根结点的权值为其左右子树是根结点权值之和。 (3) 在F中删除这两棵树，同时将新得到的二叉树加入F中。 (4) 重复(2)和(3)，直到F中只含一棵树为止。该树即为哈夫曼树。 Prof. Q. Wang

137 Prof. Q. Wang

138 Structural design of Huffman tree
#define MAXNODE 100 #define MAXNUM 50 struct HtNode /* 哈夫曼树结点的结构 */ { int weight; int parent, lchild, rchild; }; struct HtTree struct HtNode ht[MAXNODE]; int root; /* 哈夫曼树根在数组中的位置 */ }HtTree, *PHtTree; Prof. Q. Wang

139 Example A communication system has eight symbols
c1, c2, c3, c4, c5, c6, c7, c8 and the probability of each symbol is 5, 25, 3, 6, 10, 11, 36, 4 Try to design a coding method. Step1: setup a Huffman tree; Step2: coding. Prof. Q. Wang

140 Step 0: 5 25 3 6 10 11 36 4 Step 1: 5 25 3 6 10 11 36 4 7 5 25 6 10 11 36 3 4 Prof. Q. Wang

141 Step 2: 7 5 25 6 10 11 36 3 4 7 11 25 10 11 36 3 4 5 6 Prof. Q. Wang

142 Step 3: 7 11 25 10 11 36 3 4 5 6 17 7 11 10 25 11 36 3 4 5 6 Prof. Q. Wang

143 22 Step 4: 17 7 11 10 11 25 36 3 4 5 6 Step 5: 39 22 17 25 36 7 11 10 11 3 4 5 6 Prof. Q. Wang

144 Step 6: 39 61 22 17 25 36 7 11 10 11 3 4 5 6 Prof. Q. Wang

145 100 Step 7: 39 61 22 17 25 36 7 11 10 11 3 4 5 6 Prof. Q. Wang

146 Principle and Procedure of Huffman tree
n leaves (external nodes) and (n-1) internal nodes, and The last one is the root. Prof. Q. Wang

147 Principle and Procedure of Huffman tree
Prof. Q. Wang

148 Principle and Procedure of Huffman tree
Prof. Q. Wang

149 Principle and Procedure of Huffman tree
Prof. Q. Wang

150 Root node Prof. Q. Wang

151 Programming of Huffman tree
PHtTree huffman (int n, int *w) /* 构造具有n个叶结点的哈夫曼树*/ /* 数组w[1…n]中存放n个权值 */ { PHtTree pht; int i, j, x1, x2, m1, m2; pht = (PHtTree) malloc (sizeof (struct HtTree)); /* 创建空哈夫曼树 */ assert(pht); for( i=1; i<=2*n - 1; i++ ) { /* 置初态 */ pht->ht[i].lchild = 0; pht->ht[i].rchild = 0; pht->ht[i].parent = 0; if (i<=n) pht->ht[i].weight = w[i]; else pht->ht[i].weight = 0; } Prof. Q. Wang

152 pht->ht[x1].parent = n + i; /* 构造一个内部结点 */
/* 每循环一次构造一个内部结点 */ for( i=1; i < n ; i++ ) { Select (pht, n+i, &x1, &x2); pht->ht[x1].parent = n + i; /* 构造一个内部结点 */ pht->ht[x2].parent = n + i; pht->ht[n+i].weight = pht->ht[x1].weight + pht->ht[x2].weight; pht->ht[n+i].lchild = x1; pht->ht[n+i].rchild = x2; pht->root = n+i; } return pht; Prof. Q. Wang

153 void Select (PHtTree pht, int pos, int *x1, int *x2) {
int m1 = MAXINT, m2 = MAXINT; /* 相关变量赋初值 */ for (j=1; j<pos; j++) {/* 找两个最小权的无父结点的结点 */ if (pht->ht[j].weight<m1 && pht->ht[j].parent == 0) { m2 = m1; x2 = x1; m1 = pht->ht[j].weight; x1 = j; } else if (pht->ht[j].weight<m2 && pht->ht[j].parent == 0) { m2 = pht->ht[j].weight; x2 = j; Prof. Q. Wang

154 补充材料 信号编码 信源编码(香农理论Shannon)和信道编码 Prof. Q. Wang

155 补充材料 编码(coding): 需建立码本来表达数据
码本(codebook): 用来表达一定量的信息或一组事件所需的一系列符号（如字母、数字等） 码字(code): 对每个信息或事件所赋的码符号序列 码字的长度（字长）(code length): 每个码字里的符号个数 Prof. Q. Wang

156 举例 解码端收到01 bit stream a c f e d f h d h g
符号 a b c d e f g h 解码端收到01 bit stream 平均码长=( )*2+0.16*3+0.08*4+0.06*5+0.05*6=2.7 a c f e d f h d h g f b b c d a b a c a a a c 定长编码（自然码） 10个符号 变长编码（哈夫曼码） 13个符号 Prof. Q. Wang

157 2. Huffman coding (哈夫曼编码)
在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。 我们可以利用二叉树来设计二进制的前缀编码。约定左分支表示字符‘0’，右分支表示字符‘1’，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。 证明： 假设某一个叶子x结点的编码是另一个叶子结点y编码的前缀，说明从根结点到叶子结点y中间需经过结点x，从而说明x有左或右子树，这与x是叶子结点矛盾。 那么现在求最短的二进制编码实际上就是构造哈夫曼树的过程，由此得到的二进制编码，称为哈夫曼编码。 Prof. Q. Wang

158 由于哈夫曼树中没有度为1的结点（这类树又称严格的(strict) (或正则的)二叉树）, 为什么？；
则一棵有n个叶子结点的哈夫曼树共有2n-1个结点（因n2=n0-1)，可以存储在一个大小为2n-1的一维数组中。 如何选定结构类型？ (1) 编码需要从叶子到根（自底向上） (2) 译码需要从根到叶子（自顶向下） Prof. Q. Wang

159 Huffman Tree Huffman Coding Huffman Code C1 1 C2 1 C3 C4 1 1 C5 1 C6 1
1 C2 1 C3 C4 1 1 C5 1 C6 1 1 C7 1 1 C8 1 Prof. Q. Wang

160 Prof. Q. Wang

161 Total length of these symbols is
Huffman coding: c1 c2 c c c5 c6 c7 c8 5, , , , , , , Total length of these symbols is 4 * * * * * * * * 4 = 257 Prof. Q. Wang

162 void TraverseHuffman (PhtTree T, char** HC, int n) {
static int codeLen = 0; /* 为什么使用静态变量? */ static char cd[MaxLen]; if (!T) return; if (T.ht[n].rchild = = 0) { /* Why ? */ cd[codeLen] = '\0'; strcpy(HC[n], cd); } else { cd[codeLen++] = '0'; TraverseHuffman (T, HC, T.ht[n].lchild); codeLen--; cd[codeLen++] = '1'; TraverseHuffman (T, HC, T.ht[n].rchild); Prof. Q. Wang

163 unsigned int parent, lchild, rchild; } HTNode, *HuffmanTree;
typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; } HTNode, *HuffmanTree; typedef char ** HuffmanCode; C Program in textbook void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) { if (n<=1) return; m=2*n-1; HT= (HuffmanTree) malloc ((m+1)*sizeof(HTNode)); for (p=HT, i=1; i<=n; ++i, ++p, ++w) *p={*w, 0, 0, 0}; for (; i<=m; ++i, ++p) *p={0,0,0,0}; for (i=n+1; i<=m; ++i) { Select (HT, i-1, s1, s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } Prof. Q. Wang

164 HC=(HuffmanCode) malloc ((n+1)*siezof(char *));
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)); strcpt (HC[i], &cd[start]); } free (cd); Prof. Q. Wang

165 Assignments (5) 提交算法和程序 6.70, 6.42, 6.51, 6.65 自己练习与思考
6.14, 6.26, 6.27, 6.28, 6.31, 6.56, 6.57, 6.62 Prof. Q. Wang

166 Practical (3) P149 5.2 哈夫曼编/译码器
完成Huffman 编码的译码过程。即输入一个码串，请翻译成相应的字符串。要求有编码过程和解码过程。 Prof. Q. Wang

167 Conclusion Definition and notations of Tree and Forest (树和森林的定义)
Notations and representation of binary tree (二叉树的概念及存储表示) Binary tree traversal (二叉树的遍历) Threading binary tree (线索二叉树) Reconstruction of binary tree (二叉树的构造) Transformation among Tree, Forest and binary tree (树、森林和二叉树的转换) Huffman tree and Huffman coding (哈夫曼树和哈夫曼编码) Prof. Q. Wang

168 其他问题 树与等价问题 回溯法和树的遍历 Tree的计数 Prof. Q. Wang

169 Tree的计数 具有n个结点有不同形态的树（有序树）的数目Tn和具有n-1个结点互不相似的二叉树的数目相同，即 Why?
Prof. Q. Wang

170 The End! Prof. Q. Wang