第六章 树和二叉树

本章内容 树、二叉树的定义、性质和存储结构； 二叉树的遍历和线索化以及遍历算法的各种描述形式； 树遍历； 二叉树的多种应用。

本章要点 熟练掌握二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 熟练掌握二叉树各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作； 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系； 熟悉树的各种存储结构及其特点； 学会编写实现树的各种操作的算法； 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。　

6.1 树的定义和基本术语

树的定义 树是一类重要的非线性数据结构，是以分支关系定义的层次结构； 树是n(n≥0)个结点的有限集，非空树满足： 有且仅有一个特定的称之为根(root)的结点； 除根以外的其余结点可分为m(0m<n)个互不相交的子集T1,T2,T3…Tm，其中每个子集本身又是一棵树，且称为根的子树。

树的表示方法 特点：除根结点外，每个结点都仅有一个前趋(父)结点。 1层 A 2层 其它表示方法： 3层 B C D 4层 嵌套集合表示法 凹入表表示法 参见教材120页 A B C D E F G H I J 1层 2层 3层 4层

树的一些基本术语 结点的度（degree） 叶子结点（leaf--又称终端结点 terminal node） 结点所拥有的子树的数目。 叶子结点（leaf--又称终端结点 terminal node） 度为零的结点。 分支结点（branch node） 度不为零的结点 孩子（ child） 结点的子树的根称为结点的孩子。

树的一些基本术语(续) 双亲（ parent） 祖先（ forefather） 子孙（progeny） 兄弟（sibling） 结点是其孩子的双亲。 祖先（ forefather） 从树根到双亲的所有结点称为该结点的祖先。 子孙（progeny） 以结点为根的子树的所有结点称为该结点的子孙。 兄弟（sibling） 同一父母的所有孩子互称兄弟。 层次（level） 树根为第一层，其孩子为第二层，孙子为第三层，以此类推。

树的一些基本术语(续) 森林（forest ） 堂兄弟（cousin） 深度（depth） 有序树（ordered tree） 双亲在同一层的结点互称堂兄弟。 深度（depth） 树中结点的最大层次称为树的深度。 有序树（ordered tree） 结点各子树从左至右是有秩序的树称为有序树。 无序树（unordered tree） 结点各子树没有秩序的树称为无序树。 森林（forest ） 森林是 m (m≥0) 棵互不相交的树的集合。

树的基本操作 初始化操作 InitTree(&T) 求根函数 Root(T) 求双亲函数 Parent(T,cur_e) 求左孩子结点函数 LeftChild(T,cur_e) 建树函数 CreateTree(&T,definiton) 清空树函数 ClearTree(&T) 插入子树函数 InsertChild(&T,&p,i,c) 删除子树函数 DeleteChild(&T,&p,i) 遍历函数 TraverseTree(T,visit()) 求右兄弟函数 RightSibling(T,cur_e)

6.2 二叉树

二叉树的定义 定义 二叉树是n(n0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和两棵互不相交的左子树和右子树的二叉树组成。 二叉树的特点： 定义是递归的； 0结点的度2； 是有序树。

二叉树（续）  二叉树的五种基本形态 两种特殊的二叉树 满二叉树：每一层上的结点数都是最大结点数。 完全二叉树：只有最下面两层结点的度可小于2，而最下一层的叶结点集中在左边若干位置上。  1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7

二叉树的性质 性质1 性质2 性质3 性质4 二叉树的第i层上至多有2i-1(i1)个结点。 深度为k的二叉树至多有2k-1个结点(k1)。 性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2 ，则n0 = n2 + 1。 性质4 具有n个结点的完全二叉树的深度为 log2n+1。

二叉树的性质（续） 性质5 对一棵具有n个结点的完全二叉树(其深度为log2n+1)，对其结点按层从上至下(每层从左至右)进行0至n-1的编号，则对任一结点i(0i<n)有： 若i=0，则i是根，无双亲；若i>0，则i的双亲是(i-1)/2。 若2i+1<n，则i有左孩子，左孩子是2i+1。 若2(i+1)<n，则有右孩子，右孩子是2(i+1)。 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6

二叉树的存储结构 顺序存储结构 按完全二叉树存储 A B D E F C A B C D E F 0 1 2 3 4 5 6 #define MaxTreeSize 128 typedef TElemType SqBiTree[MaxTreeSize]; SqBiTree bt; A B D E F C A B C D E F 0 1 2 3 4 5 6

二叉树的存储结构（续） 顺序存储结构 用父母指针存储 A B D E F C A B C D E F - 1 2 0 1 2 3 4 5 存储结点数据和其父结点的序号 A B D E F C A B C D E F - 1 2 0 1 2 3 4 5 #define MaxTreeSize 100 typedef struct Node{ Telemtype data; int parent ; }Node; typedef Node bTree[MaxTreeSize];

二叉树的存储结构（续） 链式存储结构 链式存储结构 A ^ B ^ C ^ ^ D ^ E ^ bt A ^ ^ B ^ C ^ ^ D 用二叉链表存储 链式存储结构 用三叉链表存储 A ^ B ^ C ^ ^ D ^ E ^ bt A ^ ^ B ^ C ^ ^ D ^ E ^ bt

二叉树的存储结构（续） 二叉链表的类型定义 三叉链表的类型定义 typedef struct TriTNode typedef struct BiTNode { TElemType data； struct BiTNode*lchild； struct BiTNode*rchild； }BiTNode,*BiTree； 三叉链表的类型定义 typedef struct TriTNode { TElemType data； struct BiTNode*lchild； struct BiTNode*rchild； struct BiTNode*parent； }TriTNode,*TriTree；

二叉树的基本操作 建树函数 CreateBiTree(&T) 先序遍历函数 PreOrder(T,visit()) 中序遍历函数 InOrder(T,visit()) 后序遍历函数 PostOrder(T,visit()) 按层次遍历函数 LevelOrder(T,visit())

6.3.1 遍历二叉树

遍历二叉树 遍历二叉树 指按某条搜索路线走遍二叉树的每个结点，使得树中每个结点都被访问一次，且仅被访问一次。 根据搜索路径的不同，二叉树的遍历分为八种： √ 1、前序遍历（preorder traversal） DLR 2、中序遍历（inorder traversal） LDR 3、后序遍历（postorder traversal） LRD 4、逆前序遍历（inverse preorder traversal） DRL 5、逆中序遍历（inverse inorder traversal） RDL 6、逆后序遍历（inverse postorder traversal） RLD √ 7、按层次遍历（level-by-level traversal） 8、按层次逆遍历（ inverse level-by-level traversal）

遍历二叉树示例 1-前序 2-中序 3-后序 4-逆前序 5-逆中序 6-逆后序 7-层次 8-层次逆 1. ABDCEF B C D E 遍历方法 先序遍历：ABDEC 中序遍历：DBEAC 后序遍历：DEBCA 1-前序 2-中序 3-后序 4-逆前序 5-逆中序 6-逆后序 7-层次 8-层次逆 1. ABDCEF 2. DBAECF A B D E F C 3. DBEFCA 4. ACFEBD 5. FCEABD 6. FECDBA 7. ABCDEF 8. ACBFED

遍历二叉树的递归算法 void Preorder(BiTree t) void Inorder(BiTree t) { if (t) { visit(t); Preorder(t->lchild); Preorder(t->rchild); } void Inorder(BiTree t) { if (t) { Inorder(t->lchild); visit(t); Inorder(t->rchild); } void Postorder(BiTree t) { if (t) { Postorder(t->lchild); Postorder(t ->rchild); visit( t ); }

利用遍历结果确定二叉树问题 A 先序序列: ABCDEFGH F B G C D E H 思考：层序+先序/中序/后序， 能否确定？如何做？ 先序序列+中序序列 中序序列+后序序列 先序序列+后序序列 (x) 先序序列: ABCDEFGH 中序序列: BDCEAFHG F B G C D E H 思考：层序+先序/中序/后序， 能否确定？如何做？ 例如：层序ABCDEFGHIJ,中序DBGEHJACIF

根据先序中序求后序的算法 void get_post(char *pre, char *in, char *post, int n) { if ( n == 0) return; for (k = 0; k < n; k++) if (in[k] == pre[0]) break; if (! k < n) { printf("错误的数据!\n"); exit(1); } post[n - 1] = pre[0]; get_post(pre + 1, in, post, k); get_post(pre + 1 + k, in + k + 1, post + k, n - k - 1); }

先序遍历的非递归算法

先序遍历的非递归算法(1) void Preorder(Struct NODE *t) { init_stack(); push(t); 非递归算法1(朴素的非递归算法) void Preorder(Struct NODE *t) { init_stack(); push(t); while (!stack_empty()) { if ((p = pop()) != NULL) { visit(p); push(p->rchild); push(p->lchild); }

先序遍历的非递归算法(2) 非递归算法,考虑取消多余的空指针入栈,空指针个数可观，为n+1个 init_stack(); p = t; while (!stack_empty() || p) { visit(p); if (p->rchild) push(p->rchild); if (p->lchild) p = p->lchild; else p = pop(); } init_stack(); p = t; push(NULL); while (p) { visit(p); if (p->rchild) push(p->rchild); if (p->lchild) p = p->lchild; else p = pop(); }

后序遍历的非递归算法

后序遍历的非递归算法(1) init_stack(); push(root,0); while(!stack_empty()) { p = pop(&state); if (p == NULL) continue; if (state == 0) { push(p, 1); push(p->lchild, 0); } else if (state == 1) { push(p, 2); push(p->rchild, 0); } else { visit(p); }

后序遍历的非递归算法(2) init_stack(); push(root, 0); while(!stack_empty()) { p = pop(&state); if (p == NULL) continue; if (state == 0) { push(p, 2); push(p->rchild, 0); push(p->lchild, 0); } else { visit(p); }

中序遍历的非递归算法

中序遍历的非递归算法(1) 朴素的算法 init_stack(); 效率问题 push(root, 0); while(!stack_empty()) { p = pop(&state); if (p == NULL) continue; if (state == 0) { push(p, 1); push(p->lchild, 0); } else if (state == 1) { visit(p); push(p->rchild, 0); } 效率问题 新压入堆栈的state0节点马上弹出然后再次压入作为state1节点

中序遍历的非递归算法(2) init_stack(); p = root; while (p) { push(p); p = p->lchild; } while(!stack_empty()) { p = pop(); visit(p); p = p->rchild; } init_stack(); p = root; while (p || !stack_empty()) { if (p) { push(p); p = p->lchild; } else { p = pop(); visit(p); p = p->rchild; }

二叉树遍历的应用

二叉树遍历的应用 在二叉树中查找结点值为x的结点 求二叉树中每个结点所处的层次 求二叉树的高度 复制一棵二叉树

6.4 树和森林

树的存储结构:双亲表示法 A B C E F G D A B C D E F G ^ 1 3 ０ 1 2 3 4 5 6 存储方法：使用顺序结构 #define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data; int parent; } PTNode; /* 节点的存储结构*/ typedef struct {/* 顺序存储结构 */ PTNode nodes[MAX_TREE_SIZE]; int r, n; /* 根位置和节点数*/ } PTree; A B C E F G D A B C D E F G ^ 1 3 ０ 1 2 3 4 5 6 优点：简单，紧凑，易于寻找双亲节点 缺点：查询某节点的孩子效率低

树的存储结构:孩子表示法 方法一 struct PTNode { TElemType data; struct PTNode *child[NUM_CHILD]; }; 缺点：NUM_CHILD值不容易确定; 空域数目太多 方法二： 改进方法1，记录节点的度，分配合适大小的内存 方法三： 使用链表勾链，链表的每个节点记录一个孩子指针 优缺点比较和其他存储方案 选用的实际存储结构该考虑到可能需要操作（增加，删除，检索）

树的存储结构:孩子表示法(方法3) A B C E F G D A B C D E F G 1 2 3 4 6 5 ∧

树的存储结构:孩子表示法(方法2) #define MAX_TREE_SIZE 100 struct TNode { TElemType data; int degree; int child[1]; }; struct PTree { struct TNode *node[MAX_TREE_SIZE]; int n; } PTree; struct TNode *create_tnode(void) { struct TNode *p; int k, degree; scanf(“%d”, &degree); p = malloc(sizeof(struct TNode)+(degree-1)* sizeof(int)); P->degree = degree; for (k = 0; k < degree; k++) scanf(“%d”, &p->child[k]); input_node_data(p); return(p); }

树的存储结构(孩子兄弟表示法) 孩子兄弟表示法 A B C E F G D A ∧ B C D E F G

森林与二叉树的转换 转换原则 按孩子兄弟表示法进行转换。 树与二叉树的转换 E D

森林与二叉树的转换

树和森林的遍历 树的遍历 A B C D E F G E F G 先序遍历 后序遍历 先访问树的根结点，然后依次先根遍历根的每棵子树； ABEFCDG (二叉树先序) 后序遍历 先依次后根遍历根的每棵子树，然后访问树的根结点 EFBCGDA (二叉树中序)

森林的遍历 先序遍历： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除第一棵树外剩余的树构成的森林； 举例：A B C D E F G H I J 中序遍历 中序遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点； 中序遍历除第一棵树外剩余的树构成的森林 举例：B C D A F E H J I G

6.5 树的等价问题

集合的查找与合并 集合的运算 集合的数据结构有多种实现方法 采用的结构取决于集合大小和所进行的操作 find(x) 判断元素x属于哪个集合 Merge(Si, Sj) 将集合Si和Sj合并 集合的数据结构有多种实现方法 位图法 O(1) 有序表方法 O(n) 树型结构表示集合 采用的结构取决于集合大小和所进行的操作

树的存储结构:双亲表示法 A B C E F G D A B C D E F G ^ 1 3 ０ 1 2 3 4 5 6 存储方法：使用顺序结构 #define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data; int parent; } PTNode; /* 节点的存储结构*/ typedef struct {/* 顺序存储结构 */ PTNode nodes[MAX_TREE_SIZE]; int r, n; /* 根位置和节点数*/ } PTree; A B C E F G D A B C D E F G ^ 1 3 ０ 1 2 3 4 5 6 优点：简单，紧凑，易于寻找双亲节点 缺点：查询某节点的孩子效率低

树型结构表示集合 采用双亲表示法，存储一个森林 type PTree MFSet; int find_mfset(MFSet S, int i) { if (i < 0 || i >= S.n) return -1; for (j = i; S.nodes[j].parent >= 0; j = S.nodes[j].parent); return j; } Status merge_mfset(MFSet S, int i, int j) { if (i < 0 || i >= S.n || j < 0 || j >= S.n) return ERROR; S.node[i].parent = j; return OK; }

算法分析和改进 分析算法的效率 改进思路 改进后的分析 合并O(1),检索O(d)， d为深度，最糟糕情况下，d = n 合并时，将数量少的集合，合并到数量多的集合中 根的parent记录集合中节点个数，为区别于正常parent值，用负数 改进后的分析 合并O(1)，树深度低于log2n

改进后的合并算法 void mix_mfset(MFSet S, int i, int j) { if (S.nodes[i].parent > S.nodes[j].parent) { /* i中节点少 */ swap(i, j); } /* i中节点多 */ S.nodes[i].parent += s.nodes[j].parent; S.[j].parent = i;

改进后的检索算法 改进思路： 检索时压缩路径 int fix_mfset(MFSet S, int i) { 改进思路： 检索时压缩路径 int fix_mfset(MFSet S, int i) { for(j=i; S.nodes[j].parent>=0; j=S.nodes[j].parent); for (k = i; k != j; k = t) { t = S.nodes[k].parent; S.nodes[k].parent = j; } return j;

6.6 赫夫曼树及其应用

赫夫曼树及其应用 赫夫曼树 最优树，是一类带权路径长度最短的树； 路径长度 树的路径长度 带权路径长度 指树中两个结点间路径上所含有的分支数目。 树的路径长度 指从树根到每一结点的路径长度之和。 带权路径长度 指结点的路径长度与该结点的权之积。

赫夫曼树 树的带权路径长度 树中所有叶子结点的带权路径长度； 最优二叉树或赫夫曼树 WPL 最小的二叉树

赫夫曼树的特点 赫夫曼树中除叶子结点外，所有分支结点的度均为2； 叶子结点（外部结点）可看成是由分支结点（内部结点）组成的树扩充出来的（扩充二叉树）

赫夫曼树的构造 根据给定的n个权值{w1,w2,...wn}构成n棵二叉树的集合F={T1,T2,...,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空； 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在F中删除这两棵树，同时将新得到的二叉树加入F中； 重复2和3，直到F中只含一棵树为止； 这棵树就是赫夫曼树；

赫夫曼树构造举例1 29 14 8 7 15 11 3 5 19 23 42 [例] w={5, 29, 7, 8, 14, 23, 3, 11} 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 11 3 5 8 19 23 42 29 14 7 15 58 8 7 15 14 29 23 3 5 11 11 3 5 8 19 14 29 23 7 15 11 3 5 8 19 23 42 29 14 7 15 58 100 11 3 5 8 19 29 23 14 7 15

赫夫曼编码的存储结构和构造算法 初始有n个叶子结点(0~n-1号)，构造出的哈夫曼树有2n-1个结点 用大小m=2n-1的向量存储哈夫曼树（顺序存储） struct HTNode { int weight; int parent, lchild, rchild; } *ht; m = 2 * n - 1; ht = malloc(m*sizeof(struct HTNode)); for (p=&ht[0]; p < &ht[m]; p++) p->parent = -1; 输入ht前n个元素的weight; for (i = n; i < m; i++) { 在ht的前i个节点中寻找parent为-1且weight最小的两个节点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; }

赫夫曼树构造举例1 例： 7) 1.00 已知字符 A，B，C，D，E，F，G，使用频 度分别为：0.25，0.1，0.15，0.06 ， 0.3 ， 0.05，0.09，试以此构造霍夫曼树。 1) 0.25 0.1 0.15 0.06 0.3 0.05 0.09 2) 0.25 0.1 0.15 0.3 0.09 0.11 1 3) 0.25 0.15 0.3 0.11 0.19 A 0.44 E 0.56 4) 0.25 0.3 0.19 0.26 G B 0.19 C 0.26 5) 0.3 0.26 0.44 F D 0.11 6) 0.44 0.56 7) 1.00

霍夫曼树的应用 霍夫曼编码 G B A F D C E 1 A: 01 B: 001 C: 101 D: 1001 E: 11 1 A: 01 B: 001 C: 101 D: 1001 E: 11 F: 1000 G: 000 1、最佳判定树； 2、霍夫曼编码： WPL霍夫曼编码 = 2.56 WPL等长编码 = 3 等长编码 E: 100 A: 000 B: 001 C: 010 D: 011 F: 101 G: 110 1 G B A F D C E 利用霍夫曼 编码可提高效率： ( 3 - 2.56 ) / 3 ≈ 15%

赫夫曼编码 主数据结构：构造哈夫曼编码表，使用ht的parent域 辅助数据结构：char cd[N]; char *get_code(int i) // 求i号符号的编码串 { cd[N - 1] = '\0'; start = N - 1; for (c = i, f = ht[c].parent; f != -1; c = f, f = ht[f].parent) cd[--start] = ht[f].lchild == c ? '0' : '1'; return &cd[start]; } 解码程序比较简单，从树根出发按1或0分别走向右或左孩子，直到叶子节点，解出编码的符号

赫夫曼解码 解码程序:从树根出发按1或0分别走向右或左孩子，直到叶子节点，解出编码的符号 decode() // 求i号符号的编码串 { k = 2 * n - 2；/* 树根节点 */ for(j = 0; j < rcv_buf_len; j++) { k = rcvbuf[j] == ‘0’ ? ht[k].lchild : ht[k].rchild; if (k < n) { out_code(k); /* 解出第k号符号 */ k = 2 * n – 2; }

赫夫曼编码的特点 赫夫曼编码是不等长编码； 赫夫曼编码是前缀编码，即任一字符的编码都不是另一字符编码的前缀； 赫夫曼编码树中没有度为1的结点。若叶子结点的个数为n，则赫夫曼编码树的结点总数为 2n-1； 发送过程：根据由赫夫曼树得到的编码表送出字符数据； 接收过程：按左0、右1的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束；

作业和上机作业

作业 1.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2.一棵含有n个结点的k叉树，何种形态达到最大深度？何种形态达到最小深度？ 3.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。

作业（续） 4.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这8个字母设计哈夫曼编码。 5.画出下列森林对应的二叉树。 1 2 3 4 5 6 7 8 9 10 11 12 13 14

作业（续） 6.画出和下列二叉树相应的森林 A A A A A (1) (2) (3) (4) (5) 7.画出和下列已知序列对应的森林F： (1) (2) (3) (4) (5) 7.画出和下列已知序列对应的森林F： 森林的先序次序访问序列为：ABCDEFGHIJKL 森林的中序次序访问序列为：CBEFDGAJIKLH A A A A A B B B C B C C C D

作业（续） 8. 一棵完全 k 叉树按层次顺序从 1 开始对全部结点编号，若所求结点存在，则： ① 编号为 n 的结点的父结点的编号是多少？ ② 结点 n 的第 i 个儿子的编号是多少？ ③ 结点 n 有右兄弟的条件是什么？ 9. 设计算法将二叉树中所有节点的左右孩子互换。 10. 设计算法拷贝二叉树。 11. 设计算法判断一个二叉树是否是完全二叉树。

二叉树上机作业 a b e c d (1) 建立二叉树:两种方法 ①用先序递归过程建立二叉树 (存储结构：二叉链表) 输入数据按前序遍历所得序列输入，当某结点左子树或右子树为空时，输入‘*’号，如输入abc**d**e**得到的二叉树为： a b e c d ②由二叉树的层次序列和中序序列建立一棵二叉树。 对上例：输入abecd和cbdae两个字符串 (2) 编写递归算法，先序，后序和后序输出二叉树 (3) 计算二叉树中叶子结点的数目，和每个节点的深度。 (4) 按凹入表方式输出该二叉树。 (5) 按层次遍历的方法输出该二叉树，求出每层的结点个数。

测试实例 应当设计多个测试实例，检验程序的正确性。下边是一个例子。 A B C D E F