第六章 树 2019/1/14

6.1 树(tree)的(递归)定义 树：非线性数据结构，以分支关系定义的层次结构 树是 n(≥0) 个结点的有限集 T，在非空树中： 有且仅有一个特定的结点，称为树的根(root) n>1时，其余结点可分为 m(>0) 个互不相交的有限集 T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) A 只有根结点的树 2019/1/14

根 A B C D E F G H I J K L M 有子树的树 子树 子树 子树 2019/1/14

基本术语 结点(node)：树的元素 结点的度(degree)：结点拥有的子树数 树的度：一棵树中最大的结点度数 含数据项及若干指向其子树的分支 结点的度(degree)：结点拥有的子树数 叶子(leaf)：度为 0 的结点 树的度：一棵树中最大的结点度数 2019/1/14

基本术语(cont.) 孩子(child)：结点的子树的根 双亲(parents)：孩子结点的上层结点 兄弟(sibling)：同一双亲的孩子 结点层次(level)：根为第 1 层，根的孩子为第 2 层…… 树的深度/高度(depth)：树中结点的最大层次数 2019/1/14

基本术语(cont.) 子孙：一个结点所有子树中的结点。 祖先：从根结点到达某结点路径上的所有结点。 有序树/无序树：如果树中结点的各子树从左到右是有次序的，则称该树为有序树；否则称为无序树 森林(forest)：m(≥0) 棵互不相交的树的集合 2019/1/14

结点A的度：3 结点B的度：2 结点M的度：0 叶子：K，L，F，G，M，I，J 结点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 结点F，G为堂兄弟 结点A是结点F，G的祖先 结点A的层次：1 结点M的层次：4 2019/1/14

6.2 二叉树 定义：二叉树是 n≥0 个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左、右子树的互不相交的二叉树构成 特点： 每个结点至多有二棵子树(即不存在度大于 2 的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 2019/1/14

6.2 二叉树  基本形态： 度为2的有序树 空二叉树 A 只有根结点 的二叉树 A B 右子树为空 A B 左子树为空 A B C 左、右子树 均非空 2019/1/14

练习：给出 3 个结点A、B和C构成的所有形态的二叉树（不考虑结点值的差异） 2019/1/14

i=1时，只有一个根结点，2i-1=20=1，结论正确 假设对所有 j(1≤j＜i) 命题成立 二叉树性质 性质1： 二叉树的第 i(≥1) 层上至多有 2i-1 个结点 证明：(归纳法) i=1时，只有一个根结点，2i-1=20=1，结论正确 假设对所有 j(1≤j＜i) 命题成立 即第 j 层上至多有 2j-1 个结点，则第 i-1 层至多有 2i-2 个结点 又二叉树每个结点的度至多为 2  第 i 层上最大结点数是第 i-1 层的 2 倍，即 2×2i-2=2i-1 故命题得证 2019/1/14

二叉树性质 性质2： 深度为 k(≥1) 的二叉树至多有 2k-1 个结点 证明：由性质1，可得深度为k 的二叉树最大结点数是 2019/1/14

二叉树性质 性质3：任何一棵二叉树 T，如果其叶子数为 n0，度为 2 的结点数为 n2，则 n0=n2+1 证明：设 n1 为二叉树 T 中度为 1 的结点数 因为：二叉树中所有结点的度均小于或等于2 所以二叉树的结点总数 n=n0+n1+n2 又：除根结点外，其余结点都只有一个分支进入 设 B 为分支总数，则 n=B+1 又：分支只能由度为 1 和 2 的结点射出，即 B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 故：n0=n2+1 2019/1/14

二叉树特殊形式 满二叉树：深度为 k 且有 2k-1 个结点的二叉树 特点：每层上的结点数都是最大值 完全二叉树：深度为 k、有 n 个结点的完全二叉树当且仅当，其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应 特点 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为 l，则其左分支下子孙的最大层次必为 l 或 l+1 2019/1/14

证明：设二叉树深度为 k，根据性质 2 和完全二叉树的定义，前 k-1 层都是满的，最后一层可以满，也可以不满，则： 性质4：有 n 个结点的完全二叉树深度＝ 证明：设二叉树深度为 k，根据性质 2 和完全二叉树的定义，前 k-1 层都是满的，最后一层可以满，也可以不满，则： ① 2k-1－1＜n≤2k－1 即： 2k-1＜n+1≤2k k－1＜log2(n+1)≤k log2 (n+1)≤k＜log2(n+1)+1 因 k 为整数，所以 k= 2019/1/14

证明：设二叉树深度为 k，根据性质 2 和完全二叉树的定义，前 k-1 层都是满的，最后一层可以满，也可以不满，则： 性质4：有 n 个结点的完全二叉树深度＝ 证明：设二叉树深度为 k，根据性质 2 和完全二叉树的定义，前 k-1 层都是满的，最后一层可以满，也可以不满，则： ② 2k-1≤n＜2k 则：k－1≤log2n＜k 即：log2n＜k≤log2n+1 因 k 为整数，故 k= 2019/1/14

哪个是完全二叉树？ 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 4 5 6 7 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6 2019/1/14

性质5：对有 n 个结点的完全二叉树按层编号，则对任一结点 i(1≤i≤n)，有： (1) 若 i=1，则结点 i 是二叉树的根，无双亲；若 i＞1，则其双亲编号＝i/2 (2) 若 2i＞n，则结点 i 无左孩子；如果 2i≤n，则其左孩子编号＝2i (3) 若 2i+1＞n，则结点 i 无右孩子；如果2i+1≤n，则其右孩子编号＝2i+1 2019/1/14

理想平衡二叉树 / 理想平衡树 / 理想二叉树 在一棵二叉树中，若除最后一层外，其余层都是满的，而最后一层上的结点可以任意分布 显然！理想平衡树包括满二叉树和完全二叉树 2019/1/14

练习：任意一个有 n 个结点的二叉树，已知它有 m 个叶子，请证明非叶结点中有 m-1 个结点的度为 2、其余度为 1 证明：设度为 1 的结点有 n1 个，度为 2 的有 n2 个 则总结点 n＝n1＋n2＋m 又：n＝B＋1，B为分支数 且：B＝n1＋2n2 则：n＝n1＋2n2＋1 又：n1＋n2＋m＝n1＋2n2＋1 ∴ n2＝m－1 2019/1/14

练习：已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有多少个？ 解：设度为 0、1、2 的结点数为 n0、n1、n2，结点总数为 n n0=50，因有 n0 = n2 + 1，则 n2=49 又结点总数 n = n0+n1+n2，将上面结果代入得： n = 50 + n1 + 49，即 n=n1+99 由上式可知，当 n1=0 时n 最少，则 n 至少有 99 个结点 2019/1/14

二叉树的存储结构 顺序存储结构 按满二叉树结点的层次编号，依次存放二叉树的数据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树 1 2 3 4 5 6 7 1 2 3 4 5 0 0 0 0 6 7 0 1 2 3 4 5 6 7 8 9 10 2019/1/14

假设二叉树的存储结构如下，画出对应的二叉树 练习： 假设二叉树的存储结构如下，画出对应的二叉树 25 15 36 10 20 32 48 4 11 18 0 1 2 3 4 5 6 7 8 9 I D P C F M E H N 0 1 2 3 4 5 6 7 8 9 10 11 12 2019/1/14

二叉树顺序存储结构的类型定义： 注：下标为 0 的元素存储根结点 #define MAX_TREE_SIZE 100 typedef TElemType SqBiTree [MAX_TREE_SIZE]; SqBiTree bt; 注：下标为 0 的元素存储根结点 2019/1/14

二叉树的链式存储结构（二叉链表） 结点 typedef struct BiTNode { BTElemType data ; 数据域：数据本身 左指针：左孩子结点 右指针：右孩子结点 二叉链表 由如上结点链接而成 二叉树 BiTNode bt; //二叉树根结点 BiTree T; //指向二叉树根结点的指针 lchild data rchild typedef struct BiTNode { BTElemType data ; struct BiTNode *lchild, *rchild; } BiTNode , *BiTree ; 2019/1/14

二叉树的链式存储结构（二叉链表）示例 ^ ^ ^ ^ ^ ^ ^ ^ T (指向根结点的指针) A B C D E F G A B C D 2019/1/14

二叉树的链式存储结构（二叉链表）示例 A B C D E F G ^ T 2019/1/14

静态二叉链表：数组存储结点及父子关系 #define MAX_TREE_SIZE 100 //存储结点最大个数 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 9 … 99 2019/1/14

静态二叉链表：数组存储结点及父子关系 #define MAX_TREE_SIZE 100 //存储结点最大个数 //结点 struct SBiTreeNode { TElemType data; //数据 int left , right ; //左、右孩子对应数组元素下标 } ; 1 2 3 4 5 6 7 8 9 … 99 data left right 2019/1/14

静态二叉链表：数组存储结点及父子关系 SBiTree #define MAX_TREE_SIZE 100 //存储结点最大个数 struct SBiTreeNode {//结点 TElemType data; //数据 int left , right ; //左、右孩子对应数组元素下标 } ; typedef SBiTreeNode SBiTree [ MAX_TREE_SIZE ]; //静态二叉链表 99 … 9 8 7 6 5 4 3 2 1 data left right SBiTree 2019/1/14

练习：画出以上数组所示二叉树。 静态二叉链表：数组存储结点及父子关系 typedef SBiTreeNode SBiTree [ MAX_TREE_SIZE ]; //静态二叉链表 *注意：元素 0 不放数据，其左(下标)指针指向根结点元素 指针为 0 表示：空 根结点 1 2 3 4 5 6 7 8 9 … 99 A B D C E H F G I data left right SBiTree 练习：画出以上数组所示二叉树。 2019/1/14

二叉树基本操作 I (P127) 辅助：初始化 / 销毁 / 清空 / 空树判定 数据值：取值 / 赋值 InitBiTree / DestoryBiTree / ClearBiTree / BiTreeEmpty 数据值：取值 / 赋值 Value / Assign 导航：取根/父/左子/右子/左兄弟/右兄弟结点 Root/Parent/LeftChild/RightChild/LeftSibling/RightSibling 结点：插/删子结点 InsertChild / DeleteChild 2019/1/14

计数：树高度 / 结点数 / 叶子数 创建 / 输出 遍历：前序 / 中序 / 后序 / 层序 Depth / Count / LeafCount 创建 / 输出 CreateBiTree / PrintBiTree 遍历：前序 / 中序 / 后序 / 层序 PreOrderTraverse / InOrderTraverse / PostOrderTraverse / LevelOrderTraverse 2019/1/14

Depth( T )：树高度/深度，最大结点层次 Depth(T) = 0，T = NULL 2019/1/14

Depth (T) = Max ( Depth (T->lchild ) , Depth (T->rchild ) ) + 1 T (非空树，T 指向根结点) lchild rchild Depth(T->rchild) Depth(T->lchild) Depth (T) = Max ( Depth (T->lchild ) , Depth (T->rchild ) ) + 1 2019/1/14

int BiTreeDepth( BiTree *T ) { if ( T == NULL) //空树，高度=0 return 0; Depth(T)＝ 0 ，T＝NULL Max ( Depth(T->lchild) , Depth(T->rchild) ) + 1，T≠NULL int BiTreeDepth( BiTree *T ) { if ( T == NULL) //空树，高度=0 return 0; else { //非空树 lDepth = BTHeight( T->lchild ); //左子树高度 rDepth = BTHeight( T->rchild ); //右子树高度 if (lDepth > rDepth ) return lDepth + 1; //左子树更高 else return rDepth + 1; //右子树更高 2019/1/14

Count(T->lchild) + Count(T->rchild) + 1，T≠NULL lchild rchild Count(T->rchild) Count(T->lchild) Count(T)= 0 ，T＝NULL Count(T->lchild) + Count(T->rchild) + 1，T≠NULL 2019/1/14

Count(T->lchild) + Count(T->rchild) + 1, T≠NULL int Count( BiTree T) { if ( T == NULL) //空树 return 0; else { //非空树 lCount = Count( T->lchild ); //左子树结点数 rCount = Count( T->rchild ); //右子树结点数 return ( lCount + rCount +1); } 2019/1/14

(3) 二叉树叶子数：LeafCount(T) lchild rchild LeafCount(T->lchild) LeafCount(T->rchild) LeafCount(T) 0 , T = NULL LeafCount(T->lchild)+LeafCount(T->rchild), 其它 1 , T 为叶子 2019/1/14

LeafCount(T->lchild)+LeafCount(T->rchild), 其它 1 , T 为叶子 0 , T = NULL LeafCount(T->lchild)+LeafCount(T->rchild), 其它 1 , T 为叶子 int LeafCount( BiTree T ) { if ( T == NULL ) //空树 return 0; else if( T->lchild == NULL && T->rchild == NULL) //叶子 return 1; else { //非叶子结点 lCount = LeafCount( T->lchild); rCount = LeafCount( T->rchild); return (lCount + rCount); } 2019/1/14

^ ^ ^ (4) 用括号表示法描述二叉树：根 ( 左子树, 右子树 ) Ex1. 空树 空串 Ex2. 叶子（左右子树均为空） A A(B) Ex4. 左右子树均非空 A( B , C) A ^ B ^ C ^ 2019/1/14

^ (4) 用括号表示法描述二叉树：根 ( 左子树, 右子树 ) Ex1. 空树 空串 Ex2. 叶子（左右子树均为空） A A(B) Ex4. 左右子树均非空 A( B , C) Ex5. 只有右子树 A( , C) A ^ C 2019/1/14

A( B( C, D( E( ,G), F) )) ^ 先序遍历结果序列的另类表示法！ 练习：用括号表示法描述左图的二叉树 A B C D T A( B( C, D( E( ,G), F) )) 先序遍历结果序列的另类表示法！ 2019/1/14

(4) 用括号表示法输出二叉树：PrintBiTree(T) ① 若树不空则执行 ②，否则停止 ② 输出树的根结点值(字符) ③ 若根结点有孩子则执行 ④，否则停止 ④ 输出左括号："(" ⑤ 递归处理左子树，完成后返回 ⑥ ⑥ 若存在右孩子则输出逗号："," ⑦ 递归处理右子树，完成后返回 ⑧ ⑧ 输出右括号：")" ⑨ 结束 A B C D E F G ^ T 2019/1/14

(4) 用括号表示法输出二叉树：PrintBiTree(T) void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 } 2019/1/14

(4) 用括号表示法输出二叉树：PrintBiTree(T) void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 cout<<T ->data; //输出根结点的值 //若根结点有孩子则执行，否则停止 if ( T->lchild != NULL || T->rchild != NULL) { } 2019/1/14

(4) 用括号表示法输出二叉树：PrintBiTree(T) void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 cout<<T ->data; //输出根结点的值 //若根结点有孩子则执行，否则停止 if ( T->lchild != NULL || T->rchild != NULL) { cout<<“(”; //输出左括号 PrintBiTree( T->lchild ); //递归处理左子树 } 2019/1/14

(4) 用括号表示法输出二叉树：PrintBiTree(T) void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 cout<<T ->data; //输出根结点的值 //若根结点有孩子则执行，否则停止 if ( T->lchild != NULL || T->rchild != NULL) { cout<<“(”; //输出左括号 PrintBiTree( T->lchild ); //递归处理左子树 if (T->rchild != NULL) cout<<","; //输出逗号 } 2019/1/14

(4) 用括号表示法输出二叉树：PrintBiTree(T) void PrintBiTree ( BiTree T) { // T 是指向根的指针 if ( T != NULL) { //若树不空则执行，否则停止 cout<<T ->data; //输出根结点的值 //若根结点有孩子则执行，否则停止 if ( T->lchild != NULL || T->rchild != NULL) { cout<<“(”; //输出左括号 PrintBiTree( T->lchild ); //递归处理左子树 if (T->rchild != NULL) cout<<","; //输出逗号 PrintBiTree( T->rchild ); //递归处理右子树 cout<<“)”; } 2019/1/14

？ ^ (5) 用括号表示法创建二叉树：CreatBiTree(T) 已知括号表示字符串，创建二叉链表 已知：A( B( C, D( E( ,G), F))) 要求：创建对应的二叉链表 ？ A B C D E F G ^ T 2019/1/14

从左到右逐个读入字符串，根据字符类型确定动作 (5) 已知括号表示字符串，创建二叉链表 从左到右逐个读入字符串，根据字符类型确定动作 A( B( C, D( E( ,G), F) ) ) 2019/1/14

^ (5) 已知括号表示字符串，创建二叉链表 从左到右逐个读入字符串，根据字符类型确定动作 A ( B( C, D( E( ,G), F) ) ) 字符 1=A，数据值 T 创建根结点，填入数据值，左右指针为空 设置根指针 T，指向根结点 A ^ 2019/1/14

^ (5) 已知括号表示字符串，创建二叉链表 从左到右逐个读入字符串，根据字符类型确定动作 A ( B( C, D( E( ,G), F) ) ) 字符 2= ( ，有左孩子，需要递归处理，需要栈！ 根结点入栈，开始处理左孩子 1 2 3 4 5 A ^ T A top 2019/1/14

^ (5) 从左到右逐个读入字符串，根据字符类型确定动作 A ( B( C, D( E( ,G), F) ) ) 有右孩子，为区分左右，引入标志 k＝1(左)、2(右) A ^ T B C 遇到 ‘(‘，k = 1 (左子树) 遇到 ‘,’，k = 2 (右子树) 1 2 3 4 5 A top B 2019/1/14

^ (5) 从左到右逐个读入字符串，根据字符类型确定动作 A ( B( C, D( E( ,G), F) ) ) T 遇到 ‘)‘，左右子树都处理完，根结点出栈 1 2 3 4 5 A top B D E 2019/1/14

^ (5) 从左到右逐个读入字符串，根据字符类型确定动作 A ( B( C, D( E( ,G), F) ) ) 字符 14=, (逗号) 又遇到 ‘,‘，后面字符表示右子树，根结点在栈顶 A B C D E G ^ T 1 2 3 4 5 A top B D 2019/1/14

^ (5) 从左到右逐个读入字符串，根据字符类型确定动作 A ( B( C, D( E( ,G), F) ) ) T F 连续的 ‘)‘，连续的出栈，最终栈空且字符串结束，二叉链表创建完成！ 1 2 3 4 5 A top B D 2019/1/14

BiTree CreateBiTree(char *str) { // str: 括号表示串 (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char *str) { // str: 括号表示串 } //end = A ( B( C, D( E( ,G), F) ) ) 2019/1/14

BiTree CreateBiTree(char * str) { BiTree T; (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str) { BiTree T; BiTNode *st[MaxSize]; //简单栈 int top = 0; //栈顶指针 } //end T 1 2 3 4 5 top st 2019/1/14

BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈 (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈 int top = -1; //栈顶指针 BiTNode *p = NULL; //新结点指针 int k ; //左右子树标志 } //end P k = 1 (左子树) k = 2 (右子树) 2019/1/14

BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈 (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈 int top = -1; //栈顶指针 BiTNode *p = NULL; //新结点指针 int k ; //左右子树标志 int j = 0; //当前字符下标 (初始 = 0 ) char ch; //当前字符 } //end j = 8 str = A ( B ( C , D ( E ( , G ) , F ) ) ) ch = str [j] 2019/1/14

BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈 (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ BiTree T; BiTNode *st[MaxSize]; //简单栈 int top = -1; //栈顶指针 BiTNode *p = NULL; //新结点指针 int k ; //左右子树标志 int j = 0; //当前字符下标 (初始 = 0 ) char ch; //当前字符 bt = NULL; //根指针初始为空 ch = str [j]; //读入第 1 个字符 2019/1/14

BiTree CreateBiTree(char * str){ (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 j ++; //字符下标递增 ch = str [j]; //读入下一字符 } //end while } //end 2019/1/14

BiTree CreateBiTree(char * str){ (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 } //end switch j++; //字符下标递增 ch = str [j]; //读入下一字符 } //end while } //end 2019/1/14

BiTree CreateBiTree(char * str){ …… (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 case ‘(‘: //左括号，结点入栈，准备处理左子树 top ++; st [top] = p; k=1 ; break; } //end switch j++; //字符下标递增 ch = str [j]; //读入下一字符 } //end while } //end 2019/1/14

BiTree CreateBiTree(char * str){ …… (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 case ‘(‘: //左括号，结点入栈，准备处理左子树 top ++ ; st [top] = p ; k=1 ; break; case ‘)’: //右括号，左右子树都处理完，出栈 top -- ; break; } //end switch j++; //字符下标递增 ch = str [j]; //读入下一字符 2019/1/14

BiTree CreateBiTree(char * str){ …… (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 case ‘(‘: //左括号，结点入栈，准备处理左子树 top ++ ; st [top] = p ; k=1 ; break; case ‘)’: //右括号，左右子树都处理完，出栈 top -- ; break; case ‘,’: //逗号，准备处理右子树 k=2 ; break; } //end switch 2019/1/14

BiTree CreateBiTree(char * str){ …… (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… while( ch != ‘\0’) { //逐个读入字符，直到括号表示串结束 switch (ch) { //根据当前字符类型确定动作 default: //其它字符(即数据) p = (BiTNode *)malloc (sizeof (BiTNode)); //创建结点 p->data = ch; //保存数据 p->lchild = NULL; //初始化左右指针 p->rchild = NULL; } //end switch 2019/1/14

BiTree CreateBiTree(char * str){ …… default: //其它字符(即数据) (5) 用括号表示法创建二叉树： BiTree CreateBiTree(char * str){ …… default: //其它字符(即数据) //新结点与栈顶结点链接 if ( bt == NULL ) //空树，新结点是根 bt = p; else if ( k == 1 ) //新结点是栈顶结点的左孩子 st [ top ] -> lchild = p ; else if ( k == 2 ) //新结点是栈顶结点的右孩子 st [ top ] -> rchild = p; } //end switch 2019/1/14

6.3 遍历二叉树 树的遍历 遍历——按某条路径访问二叉树的每个结点，使每个结点被访问一次且仅被访问一次 常用方法 先根（序）遍历：访问根结点；依次先根遍历根的每棵子树 后根（序）遍历：依次后根遍历每棵子树；访问根结点 层次遍历：访问第一层结点；依次遍历第二层，…第n层结点 2019/1/14

二叉树遍历 先序：访问根结点；先序遍历左子树、右子树 中序：中序遍历左子树；访问根结点；中序遍历右子树 后序：后序遍历左、右子树；访问根结点 层次：从上到下、从左到右访问各层结点 D L R LDR、LRD、DLR RDL、RLD、DRL 2019/1/14

先序遍历: 先序遍历序列：A B D C D L R D L R A D L R A D B C B > D L R C > 2019/1/14

中序遍历: 中序遍历序列：B D A C L D R A L D R A D B C L D R > L D R B > C 2019/1/14

后序遍历: 后序遍历序列： D B C A L R D A A L R D L R D C B D > B > > C 2019/1/14

- + a * b - c d / e f a + b * c - d - e / f a b c d - * + e f / - 先序遍历： a + b * c - d - e / f 中序遍历： a b c d - * + e f / - 后序遍历： 2019/1/14

二叉树遍历（递归）算法 //二叉链表定义 typedef int TElemType ; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiNode , *BiTree ; lchild data rchild 2019/1/14

先序遍历（递归）算法 int PreOrderTraverse ( BiTree T ) { if ( T != NULL) { //遍历指针不空，指向某子树根结点 printf ( “%d\t” , T->data ); //根 PreOrderTraverse ( T->lchild ); //左 PreOrderTraverse ( T->rchild ); //右 } 2019/1/14

A > B C > > D > > T A printf(A); pre(T L); pre(T R); T int PreOrderTraverse ( BiTree T ) { if ( T != NULL) { printf ( “%d\t” , T->data ); PreOrderTraverse ( T->lchild ); PreOrderTraverse ( T->rchild ); } T A printf(A); pre(T L); A pre(T R); T B printf(B); pre(T L); T C printf(C); pre(T L); T > 左是空返回 B C pre(T R); T > 左是空返回 T > 右是空返回 T D printf(D); pre(T L); D 返回 T > 左是空返回 T > 右是空返回 主程序 pre( T ) 返回 pre(T R); 返回 返回 先序序列：A B D C pre(T R); 返回 2019/1/14

int InOrderTraverse ( BiTree T ) { if ( T != NULL) { /// 中序遍历 int InOrderTraverse ( BiTree T ) { if ( T != NULL) { InOrderTraverse ( T->lchild ); //左 printf ( “%d\t” , T->data ); //根 InOrderTraverse ( T->rchild ); //右 } 2019/1/14

int PostOrderTraverse ( BiTree T ) { if ( T != NULL) { /// 后序遍历 int PostOrderTraverse ( BiTree T ) { if ( T != NULL) { PostOrderTraverse ( T->lchild ); //左 PostOrderTraverse ( T->rchild ); //右 printf ( “%d\t” , T->data ); //根 } 2019/1/14

由先序和中序遍历结果可以唯一确定一棵二叉树。 由后序和中序遍历结果可以唯一确定一棵二叉树。 由先序和后序遍历结果不能唯一确定一棵二叉树。 说明：对于先序、中序、后序遍历序列中： 由先序和中序遍历结果可以唯一确定一棵二叉树。 由后序和中序遍历结果可以唯一确定一棵二叉树。 由先序和后序遍历结果不能唯一确定一棵二叉树。 若二叉树的先序、中序序列相同，则该二叉树的形态为： 空树、只有根结点、右单支 若二叉树的后序、中序序列相同，则该二叉树的形态为： 空树、只有根结点、左单支 若二叉树的先序、后序序列相同，则该二叉树的形态为： 空树、只有根结点 2019/1/14

例：二叉树的先序、中序遍历结果如下，画出该二叉树 先序：ABCDEFG 中序：CBDEAFG 2019/1/14

1、二叉树的后序、中序周游结果如下，画出该二叉树。 后序：43268751 （每位数字代表一个结点） 中序：24316578 练习： 1、二叉树的后序、中序周游结果如下，画出该二叉树。 后序：43268751 （每位数字代表一个结点） 中序：24316578 2、一个二叉树的先序、中序和后序分别如下，其中一部分未显示出来，试求出空格处的内容，并画出该二叉树。 先序：__B__F__ICEH__G 中序：D__KFIA__EJC__ 后序：__K__FBHJ__G__A 答: ABDFKICEHJG DBKFIAHEJCG DKIFBHJEGCA 2019/1/14

按先序遍历序列，建立二叉链表 A B C 0 0 D E 0 G 0 0 F 0 0 0 (0 表示空) A B C D E F G 2019/1/14

scanf(“%c”, &ch); //读入 1 个字符 if ( ch ==‘0’) //空 bt = NULL; else { 按先序遍历序列，递归建立二叉链表算法 BiTree createbt ( ) { BiTree *bt; char ch; scanf(“%c”, &ch); //读入 1 个字符 if ( ch ==‘0’) //空 bt = NULL; else { bt = (BiTree) malloc ( sizeof ( BiNode )); bt->data = ch; bt->lchild = createbt (); //递归读入左子树 bt->rchild = createbt (); //递归读入右子树 } 2019/1/14

6.3.2 线索二叉树 定义： 二叉树遍历序列中两个相邻结点互称为前驱与后继 指向前驱或后继结点的指针称为线索 加上线索的二叉树叫线索二叉树 按遍历序列使二叉树变为线索二叉树的过程叫线索化 2019/1/14

6.3.2 线索二叉树 实现 n 个结点的二叉链表中，必有 n+1 个空链域 扩展二叉链表结点：标志域 LTag、RTag LTag： 表示 lchild 指针的含义，0—左孩子；1—前驱 RTag： 表示 rchild 指针的含义，0—右孩子；1—后继 lchild LTag data RTag rchild 2019/1/14

Ex.1 先序线索二叉树 A B C D E A B D C E T 先序序列：ABCDE 先序线索二叉树 1 1 1 1 1 1 ^ 1 1 1 1 1 1 ^ 2019/1/14

Ex.2 中序线索二叉树 A B C D E A B D C E T 中序序列：BCAED 中序线索二叉树 ^ 1 1 ^ 1 1 1 1 ^ 1 1 ^ 1 1 1 1 2019/1/14

Ex.3 后序线索二叉树 A B C D E A B D C E T 后序序列：CBEDA 后序线索二叉树 1 1 ^ 1 1 1 1 1 1 ^ 1 1 1 1 2019/1/14

6.3.2 线索二叉树 二叉树线索化的目的 遍历时，不再需要栈 2019/1/14

6.4 树和森林 树 vs. 二叉树 森林 相同点：层次结构、唯一根结点 差异点：树结点允许 2 个以上的子结点；二叉树结点最多 2 个子结点 森林 不相交的树集合 2019/1/14

6.4.1 树的存储结构 双亲表示法 孩子表示法 多重链表 孩子链表 孩子兄弟表示法 2019/1/14

6.4 树和森林 6.4.1 树的存储结构 双亲表示法：子结点保存父结点位置信息 //结点结构 数据域：存放结点本身信息 双亲域：指示双亲结点在数组中位置 //结点结构 typedef struct PTNode { TElemType data; int parent; } PTNode; data parent 数据域 双亲域 2019/1/14

6.4 树和森林 6.4.1 树的存储结构 双亲表示法 …… 1 2 data parent // 双亲表示的树结构 1 2 MAX_TREE_SIZE data parent …… 结点数组 // 双亲表示的树结构 typedef struct { PTNode nodes[MAX_TREE_SIZE]; int r, n; } PTree; 根结点位置 结点个数 2019/1/14

双亲表示法示例 如何找孩子结点 如何找兄弟结点 6 1 2 3 4 5 7 8 9 data parent a b c d e f h g 1 2 3 4 5 7 8 9 data parent a b c d e f h g i a c d e f g h i b 1 1 2 2 3 5 如何找孩子结点 如何找兄弟结点 5 根结点放在 位置 1 5 1 9 结点数＝9 2019/1/14

6.4.1 树的存储结构 孩子表示法(多重链表) 每个结点有多个指针域，分别指向其子树的根 结点同构： 结点指针个数相等 ＝ 树的度 D data child1 child2 ………. childD 树的度 ＝ D 结点不同构：结点指针个数不等 ＝ 结点的度 d data degree child1 child2 ………. childd 结点的度 ＝ d 2019/1/14

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

6.4.1 树的存储结构 带双亲的孩子链表 int parent; parent：指示父结点位置 firstchild：孩子链表头指针 //表头数组元素结点 typedef struct { TElemType data; int parent; ChildPtr firstchild; //孩子链表头指针 } CTBox ; 父结点在数组中的位置 2019/1/14

^ 带双亲的孩子链表法示例 a b c d e f h g i 6 1 2 3 4 5 7 8 9 a c d e f g h i b data ^ parent firstchild 2019/1/14

6.4.1 树的存储结构 孩子兄弟表示法(二叉链表) 左指针  自己的第 1 个孩子结点 右指针  自己的下一个兄弟 typedef struct CSNode { TElemType data; struct CSNode *firstchild, //第一个孩子 *nextsibling; //下一个兄弟 } CSNode, *CSTree; 2019/1/14

^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 孩子兄弟表示法示例 问题：破坏了树的层次关系 a b c d e f h g i a b c d e 2019/1/14

孩子兄弟表示法的另类解释！ 二叉链表即可表示树 也可表示二叉树 ^ a b c d e f h g i a b c d e f h g i 2019/1/14

树与二叉树之间可以一一对应！ 可以相互转换 ^ 二叉链表即可表示树，也可表示二叉树 a b c d e f h g i a b c d e 2019/1/14

将树转换成二叉树 6.4.2 森林与二叉树的转换 加线 抹线 旋转 兄弟之间加连线 除左孩子外，去除与其余孩子之间的连线 以根结点为轴心，整树顺时针旋转 45° 2019/1/14

树转换成二叉树示例 加线、抹线、旋转 转换得到的二叉树其右子树一定为空 A B C D E F G H I A B C D E F G H 2019/1/14

二叉树转换成树 加线 若结点 p 是其父结点的左孩子，则将 p 的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p 的父结点连线 抹线 抹掉原二叉树中父结点与右孩子之间的连线 调整 将结点按层次排列，形成树结构 2019/1/14

二叉树转换成树示例 加线、抹线、调整 A B C D E F G H I A B C D E F G H I A B C D E F G H 2019/1/14

森林转换成二叉树 6.4.2 森林与二叉树的转换 （树）转换 （根）连线 旋转 各棵树分别转换成二叉树 每棵树根结点用线相连 第一棵树根结点为二叉树根 以根结点为轴顺时针旋转，构成二叉树型结构 2019/1/14

森林转换成二叉树示例 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J 树转换 A B C D E F G H I J A B C D E F G H I J 旋转 根连线 2019/1/14

二叉树转换成树或森林 6.4.2 森林与二叉树的转换 加线 抹线 还原 若结点是左孩子，则将该结点的右孩子、右孩子的右孩子，…都与该结点的父结点连线 抹线 抹去原二叉树中所有父结点与右孩子之间的连线 还原 整理上两步的结果，使之结构层次分明 2019/1/14

二叉树转换成树或森林 加线、抹线、还原 A B C D E F G H I J A B C D E F G H I J A B C D E 调整 A B C D E F G H I J 2019/1/14

6.6 赫夫曼树及其应用 Huffman树 结点带权路径长度：根到该结点的路径长度与该结点权值的乘积 树带权路径长度：所有叶结点的带权路径长度之和 Huffman树 设有 n 个权值 {w1,w2,……wn} 构造有 n 个叶结点的二叉树，其叶子结点的权值＝wi WPL 最小的二叉树叫 Huffman 树 2019/1/14

例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树 a b c d 7 5 2 4 d c a b 2 4 7 5 WPL=7*2+5*2+2*2+4*2=36 a b c d 7 5 2 4 WPL=7*3+5*3+2*1+4*2=46 树的带权路径长度最短 WPL=7*1+5*2+2*3+4*3=35 2019/1/14

Huffman 树的构造 给定 n 个权值 {w1,w2,……wn} [1] 初始化：构造 n 棵只有根结点的二叉树，权值为 wj [2] 迭代选择(贪心)：森林中选取 2 棵根结点权值最小的树作左右子树，构造一棵新二叉树 新二叉树根结点权值 ＝ 左右子树根结点权值和 [3] 重复步骤[2]，直到只剩一棵树时，算法结束 2019/1/14

练习：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 8 7 15 14 29 23 3 5 11 11 3 5 8 19 14 29 23 7 15 11 3 5 8 19 29 23 14 7 15 29 14 8 7 15 11 3 5 19 23 42 2019/1/14

练习：w = { 5, 29, 7, 8, 14, 23, 3, 11 } 271 Huffman 树可以不唯一！ 29 14 8 7 15 19 23 42 11 3 5 8 19 23 42 29 14 7 15 58 11 3 5 8 19 23 42 29 14 7 15 58 100 WPL=？ 271 Huffman 树可以不唯一！ 2019/1/14

Huffman 树的应用：Huffman 编码 数据通信，压缩电文用的二进制编码 Ex. 设要传送的字符串＝ABACCDA (定长)编码：A—00 B—01 C—10 D—11 00010010101100 14位 若采用不等长编码，让出现次数较多的字符尽可能用短编码 则转换的二进制字符串便可能减少 2019/1/14

若编码为： A—0 B—00 ABACCDA C—1 D---01 000011010 9位 但： 0000 AAAA ABA BB 但： 0000 AAAA ABA BB 重码 000011010 9位 关键：不等长编码方案中，必须使任一字符的编码都不是另一个字符的编码的前缀，即前缀编码 2019/1/14

前缀编码 A C B D 1 编码方案 ：A—0 B—110 C—10 D—111 要传送的字符串＝ABACCDA 0110010101110 A C B D 1 规定： 左分支用“0”表示 右分支用“1”表示 前缀编码二叉树 2019/1/14

前缀编码 译码：从根出发，逐个接收字符，遇“0”向左、遇“1”向右，到达叶子、译出一个字符 A C B D 1 0 1 1 0 0 1 0 1 0 1 1 1 0 A B A C C D A 2019/1/14

练习 电文由字母 S, W, P, U, C, T, E, D 组成，字母出现频率(%)为 5, 25, 3, 6, 10, 11, 36, 4 画出 Huffman 树，给出 Huffman 编码 求出平均码长 给出电文 swpucsse 的对应编码串 给出编码串 0001011001011 的对应电文 2019/1/14

画出 Huffman 树，给出 Huffman 编码 字母{ S, W, P, U, C, T, E, D }, 频率{ 5, 25, 3, 6, 10, 11, 36, 4 } 画出 Huffman 树，给出 Huffman 编码 100 61 39 36 25 22 17 7 10 11 4 3 6 5 P D C T S U W E 1 S W P U C T E D 0110 10 0000 0111 001 010 11 0001 2019/1/14

字母{ S, W, P, U, C, T, E, D }, 频率{ 5, 25, 3, 6, 10, 11, 36, 4 } 求出平均码长 (4×5＋2×25＋4×3＋4×6＋3×10＋3×11＋2×36＋4 ×4)/100 2.57 2019/1/14

字母{ S, W, P, U, C, T, E, D }, 频率{ 5, 25, 3, 6, 10, 11, 36, 4 } 给出电文 swpucsse 的对应编码串 0110 10 0000 0111 001 0110 0110 11 S W P U C T E D 0110 10 0000 0111 001 010 11 0001 2019/1/14

字母{ S, W, P, U, C, T, E, D }, 频率{ 5, 25, 3, 6, 10, 11, 36, 4 } 给出编码串 0001011001011 的对应电文 DSTE 100 61 39 36 25 22 17 7 10 11 4 3 6 5 P D C T S U W E 1 2019/1/14

例 w={5, 29, 7, 8, 14, 23, 3, 11} typedef struct { unsigned int weight; 下标 weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 typedef struct { unsigned int weight; unsigned int parent , lchild , rchild ; } HTNode , *HuffmanTree ; 2019/1/14

int Huffman( HuffmanTree HT, int *w , int n ) { for( i = 1 ; i < 2*n ;i++) { // 初始化 HT[i].parent = HT[i].lchild = HT[i].rchild = 0; if (i <= n) HT[i].weight = w[i-1]; // 前 n 个结点赋权值 else HT[i].weight = 0; // 后 n-1 个结点预留 } //初始化结束 // 待续… 2019/1/14

int Huffman( HuffmanTree HT, int *w , int n ) { // …续 for ( i = n+1 ; i <=2*n-1 ; i++) { // 构造 HUFFMAN树 Select ( HT , i - 1 , &s1, &s2 ) ; // 最小及次小权元下标 HT[s1].parent = i; // 设置新根结点 HT[s2].parent = i; HT[i].weight = HT[s1].weight + HT[s2].weight ; // 权值和 HT[i].lchild = s1; // 根结点与子结点链接 HT[i].rchild = s2; } //结束构造 } 2019/1/14

Huffman树 频率={ 5, 29, 7, 8, 14, 23, 3, 11 } n = 8 存储静态 Huffman 树的数组尺寸： 下标 weight parent lchild rchild 1 5 2 29 3 7 4 8 14 6 23 11 9 10 12 13 15 频率={ 5, 29, 7, 8, 14, 23, 3, 11 } n = 8 存储静态 Huffman 树的数组尺寸： 2*n – 1 = 15 初始化 2019/1/14

i = n+1 = 9 在前 i -1 = 8 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 7 s2 = 1 构造新结点，存储于 下标为 i = 9 的元素中 权值=最小及次小权和 = 5 + 3 = 8 构造以元素9为根的子 二叉树 index weight parent lchild rchild 1 5 2 29 3 7 4 8 14 6 23 11 9 10 12 13 15 9 8 7 1 2019/1/14

i + 1 = 10 在前 i -1 = 9 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 3 s2 = 4 新结点存储于元素10 权值 = 7 + 8 = 15 构造元素10的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 6 23 11 15 12 13 2019/1/14

i + 1= 11 在前 i -1 = 10 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 9 s2 = 8 新结点存储于元素11 权值 = 8 + 11 = 19 构造元素11的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 6 23 11 15 19 12 13 2019/1/14

i + 1 = 12 在前 i -1 = 11 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 5 s2 = 10 新结点存储于元素12 权值 = 14 + 15 = 29 构造元素12的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 12 6 23 11 15 19 13 2019/1/14

i + 1= 13 在前 i -1 = 12 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 11 s2 = 6 新结点存储于元素13 权值 = 19 + 23 = 42 构造元素13的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 12 6 23 13 11 15 19 42 2019/1/14

i + 1 = 14 在前 i -1 = 13 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 2 s2 = 12 新结点存储于元素14 权值 = 29 + 29 = 58 构造元素14的子二叉树 no weight parent lchild rchild 1 5 9 2 29 14 3 7 10 4 8 12 6 23 13 11 15 19 42 58 2019/1/14

i + 1 = 15 在前 i -1 = 14 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 13 s2 = 14 新结点存储于元素15 权值 = 42 + 58 = 100 构造元素15的子二叉树 no weight parent lchild rchild 1 5 9 2 29 14 3 7 10 4 8 12 6 23 13 11 15 19 42 58 100 2019/1/14