数据结构第六章树

1、2021-12-152021-12-15v 6.1 树(tree)的(递归)定义v 树是 n(0) 个结点的有限集 T，在非空树中：v 有且仅有一个特定的结点，称为树的根(root)v n1时，其余结点可分为 m(0) 个互不相交的有限集 T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)树：非线性数据结构，以分支关系定义的层次结构树：非线性数据结构，以分支关系定义的层次结构A只有根结点的树只有根结点的树2021-12-15ABCDEFGHIJKLM有子树的树有子树的树根根子树子树子树子树子树子树2021-12-15v 基本术语v 结点(node)：树的元素v 含数

2、据项及若干指向其子树的分支v 结点的度(degree)：结点拥有的子树数v 叶子(leaf)：度为 0 的结点v 树的度：一棵树中最大的结点度数2021-12-15v 基本术语(cont.)v 孩子(child)：结点的子树的根v 双亲(parents)：孩子结点的上层结点v 兄弟(sibling)：同一双亲的孩子v 结点层次(level)：根为第 1 层，根的孩子为第 2 层v 树的深度/高度(depth)：树中结点的最大层次数2021-12-15v 基本术语(cont.)v 子孙：一个结点所有子树中的结点。v 祖先：从根结点到达某结点路径上的所有结点。v 有序树/无序树：如果树中结点的各子

3、树从左到右是有次序的，则称该树为有序树；否则称为无序树v 森林(forest)：m(0) 棵互不相交的树的集合2021-12-15ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G

4、的祖先的祖先2021-12-15v 6.2 二叉树v 定义：二叉树是 n0 个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左、右子树的互不相交的二叉树构成v 特点：v 每个结点至多有二棵子树(即不存在度大于 2 的结点)v 二叉树的子树有左、右之分，且其次序不能任意颠倒2021-12-15v 6.2 二叉树v 基本形态：A只有根结点只有根结点的二叉树的二叉树 空二叉树空二叉树AB右子树为空右子树为空AB左子树为空左子树为空ABC左、右子树左、右子树均非空均非空度为度为2的有序树的有序树2021-12-15练习：练习：给出给出 3 个结点个结点A、B和和C构成的所有形态的二叉

5、树（不构成的所有形态的二叉树（不考虑结点值的差异）考虑结点值的差异）ABCABCABCABCABC2021-12-15v二叉树性质 性质1：证明：证明：(归纳法归纳法) i=1时，只有一个根结点，时，只有一个根结点，2i-1=20=1，结论正确，结论正确 假设对所有假设对所有 j(1ji) 命题成立命题成立 即第即第 j 层上至多有层上至多有 2j-1 个结点个结点，则，则第第 i-1 层至多有层至多有 2i-2 个结点个结点 又二叉树每个结点的度至多为又二叉树每个结点的度至多为 2 第第 i 层上最大结点数是第层上最大结点数是第 i-1 层的层的 2 倍，即倍，即 22i-2=2i-1 故命

6、题得证故命题得证二叉树的第二叉树的第 i(1) 层上至多有层上至多有 2i-1 个结点个结点2021-12-15v 二叉树性质 性质2：证明：由性质证明：由性质1，可得深度为，可得深度为k 的二叉树最大结点数是的二叉树最大结点数是1-22)(111 -kkikiii层最大结点数第深度为深度为 k(1) 的二叉树至多有的二叉树至多有 2k-1 个结点个结点2021-12-15 性质3：任何一棵二叉树 T，如果其叶子数为 n0，度为 2 的结点数为 n2，则 n0=n2+1证明：设证明：设 n1 为二叉树为二叉树 T 中度为中度为 1 的结点数的结点数 因为：二叉树中所有结点的度均小于或等于因为：

7、二叉树中所有结点的度均小于或等于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+1v 二叉树性质2021-12-15v 二叉树特殊形式 满二叉树：深度为 k 且有 2k-1 个结点的二叉树 特点：每层上的结点数都是最大值 完全二叉树：深度为 k、有 n 个结点的完

8、全二叉树当且仅当，其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应 特点 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为 l，则其左分支下子孙的最大层次必为 l 或 l+12021-12-15证明：设二叉树深度为证明：设二叉树深度为 k，根据性质，根据性质 2 和完全二叉树的定义，和完全二叉树的定义，前前 k-1 层都是满的，最后一层可以满，也可以不满，则：层都是满的，最后一层可以满，也可以不满，则： 2k-11n2k1 即：即： 2k-1n+12k k1log2(n+1)k log2 (n+1)klog2(n+1)+1 因因 k 为整

9、数，所以为整数，所以 k= 1log2n 性质4：有 n 个结点的完全二叉树深度1log2n2021-12-15证明：设二叉树深度为证明：设二叉树深度为 k，根据性质，根据性质 2 和完全二叉树的定义，和完全二叉树的定义，前前 k-1 层都是满的，最后一层可以满，也可以不满，则：层都是满的，最后一层可以满，也可以不满，则： 2k-1n2k 则：则：k1log2nk 即：即：log2nklog2n+1 因因 k 为整数，故为整数，故 k= 性质4：有 n 个结点的完全二叉树深度1log2n1log2n2021-12-1512311458912136710141512311458912671012

10、34567123456哪个是完全二叉树？哪个是完全二叉树？2021-12-15 性质5：对有 n 个结点的完全二叉树按层编号，则对任一结点 i(1in)，有： (1) 若 i=1，则结点 i 是二叉树的根，无双亲；若 i1，则其双亲编号i/2 (2) 若 2in，则结点 i 无左孩子；如果 2in，则其左孩子编号2i (3) 若 2i+1n，则结点 i 无右孩子；如果2i+1n，则其右孩子编号2i+12021-12-15 理想平衡二叉树理想平衡二叉树 / 理想平衡树理想平衡树 / 理想二叉树理想二叉树在一棵二叉树中，若除最后一层外，其余层都是满的，在一棵二叉树中，若除最后一层外，其余层都是满的

11、，而最后一层上的结点可以任意分布而最后一层上的结点可以任意分布显然！理想平衡树包括满二叉树和完全二叉树显然！理想平衡树包括满二叉树和完全二叉树2021-12-15练习：练习：任意一个有任意一个有 n 个结点的二叉树，已知它有个结点的二叉树，已知它有 m 个叶子，个叶子，请证明非叶结点中有请证明非叶结点中有 m-1 个结点的度为个结点的度为 2、其余度为、其余度为 1证明：设度为证明：设度为 1 的结点有的结点有 n1 个，度为个，度为 2 的有的有 n2 个个 则总结点则总结点 nn1n2m 又：又：nB1，B为分支数为分支数 且：且：Bn12n2 则：则：nn12n21 又：又：n1n2mn

12、12n21 n2m12021-12-15练习：练习：已知二叉树有已知二叉树有 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 个结点个结点2

13、021-12-15v 二叉树的存储结构v 顺序存储结构v 按满二叉树结点的层次编号，依次存放二叉树的数据元素v 特点：v 结点间关系蕴含在其存储位置中v 浪费空间，适于存满二叉树和完全二叉树12345671 2 3 4 5 0 0 0 0 6 7 0 1 2 3 4 5 6 7 8 9 102021-12-15练习：练习： 假设二叉树的存储结构如下，画出对应的二叉树假设二叉树的存储结构如下，画出对应的二叉树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 N0 1 2 3 4 5 6 7 8 9 10 11 12

14、2021-12-15#define MAX_TREE_SIZE 100typedef TElemType SqBiTree MAX_TREE_SIZE;SqBiTree bt;二叉树顺序存储结构的类型定义：二叉树顺序存储结构的类型定义：注：下标为注：下标为 0 的元素存储的元素存储根结点根结点2021-12-15v 结点v 数据域：数据本身v 左指针：左孩子结点v 右指针：右孩子结点v 二叉链表v 由如上结点链接而成v 二叉树v BiTNode bt; /二叉树根结点v BiTree T; /指向二叉树根结点的指针v 二叉树的链式存储结构（二叉链表）typedef struct BiTNode

15、 BTElemType data ; struct BiTNode *lchild, *rchild; BiTNode , *BiTree ;lchild data rchild 2021-12-15v 二叉树的链式存储结构（二叉链表）示例ABCDEFG AB C D E F GT (指向根结点的指针指向根结点的指针)2021-12-15v 二叉树的链式存储结构（二叉链表）示例 AB C D E F GT2021-12-15静态静态二叉链表：数组存储结点及父子关系二叉链表：数组存储结点及父子关系#define MAX_TREE_SIZE 100 /存储结点最大个数存储结点最大个数0123456

16、789992021-12-15静态静态二叉链表：数组存储结点及父子关系二叉链表：数组存储结点及父子关系#define MAX_TREE_SIZE 100 /存储结点最大个数存储结点最大个数/结点结点struct SBiTreeNode TElemType data; /数据数据 int left , right ; /左、右孩子对应数组元素左、右孩子对应数组元素下标下标 ;012345678999dataleftright2021-12-15静态静态二叉链表：数组存储结点及父子关系二叉链表：数组存储结点及父子关系#define MAX_TREE_SIZE 100 /存储结点最大个数存储结点最大

17、个数struct SBiTreeNode /结点结点 TElemType data; /数据数据 int left , right ; /左、右孩子对应数组元素左、右孩子对应数组元素下标下标 ;typedef SBiTreeNode SBiTree MAX_TREE_SIZE ; /静态二叉链表静态二叉链表999876543210dataleftrightSBiTree2021-12-15静态静态二叉链表：数组存储结点及父子关系二叉链表：数组存储结点及父子关系012345678999ABDCEHFGI12450700000306089000dataleftrighttypedef SBiTre

18、eNode SBiTree MAX_TREE_SIZE ; /静态二叉链表静态二叉链表*注意：元素注意：元素 0 不放数据，其不放数据，其左左(下标下标)指针指针指向指向根结点根结点元素元素 指针为指针为 0 表示：空表示：空SBiTree根结点根结点练习：练习：画出以上数组所示二叉树。画出以上数组所示二叉树。2021-12-15二叉树基本操作二叉树基本操作 I (P127)v辅助：初始化 / 销毁 / 清空 / 空树判定vInitBiTree / DestoryBiTree / ClearBiTree / BiTreeEmptyv数据值：取值 / 赋值vValue / Assignv导航：取

19、根/父/左子/右子/左兄弟/右兄弟结点vRoot/Parent/LeftChild/RightChild/LeftSibling/RightSiblingv结点：插/删子结点vInsertChild / DeleteChild2021-12-15v 计数：树高度 / 结点数 / 叶子数v Depth / Count / LeafCountv 创建 / 输出v CreateBiTree / PrintBiTreev 遍历：前序 / 中序 / 后序 / 层序v PreOrderTraverse / InOrderTraverse / PostOrderTraverse / LevelOrderTr

20、averse2021-12-15(1) 二叉树高度：二叉树高度：Depth(T) Depth(T) = 0，T = NULLT (指向根结点的指针指向根结点的指针)Depth( T )：树高度：树高度/深度，最大结点层次深度，最大结点层次T (空树空树)2021-12-15(1) 二叉树高度：二叉树高度：Depth(T) Depth (T) = Max ( Depth (T-lchild ) , Depth (T-rchild ) ) + 1T (非空树，非空树，T 指向根结点指向根结点)lchild rchildDepth(T-lchild)Depth(T-rchild)2021-12-15

21、Depth(T)0 ，TNULL Max ( Depth(T-lchild) , Depth(T-rchild) ) + 1，TNULLint 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 rD

22、epth + 1; /右子树更高右子树更高2021-12-15(2) 二叉树结点总数：二叉树结点总数：Count(T)Count(T)=0 ，TNULL Count(T-lchild) + Count(T-rchild) + 1，TNULLT (非空树，非空树，T 指向根结点指向根结点)lchild rchildCount(T-lchild)Count(T-rchild)2021-12-15Count(T)=0 , T=NULL Count(T-lchild) + Count(T-rchild) + 1, TNULLint Count( BiTree T) if ( T = NULL) /空树

23、空树 return 0; else /非空树非空树 lCount = Count( T-lchild ); /左子树结点数左子树结点数 rCount = Count( T-rchild ); /右子树结点数右子树结点数 return ( lCount + rCount +1); 2021-12-15(3) 二叉树叶子数：二叉树叶子数：LeafCount(T)LeafCount(T)0 , T = NULL LeafCount(T-lchild)+LeafCount(T-rchild), 其它其它1 , T 为叶子为叶子T (非空树，非空树，T 指向根结点指向根结点)lchild rchildL

24、eafCount(T-lchild)LeafCount(T-rchild)2021-12-15LeafCount(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); r

25、Count = LeafCount( T-rchild); return (lCount + rCount); 2021-12-15(4) 用括号表示法描述二叉树：根用括号表示法描述二叉树：根 ( 左子树左子树, 右子树右子树 )Ex1. 空树空树空串空串Ex2. 叶子（左右子树均为空）叶子（左右子树均为空）AEx3. 只有左子树只有左子树A(B)Ex4. 左右子树均非空左右子树均非空A( B , C) AB C2021-12-15(4) 用括号表示法描述二叉树：根用括号表示法描述二叉树：根 ( 左子树左子树, 右子树右子树 )Ex1. 空树空树空串空串Ex2. 叶子（左右子树均为空）叶子（左

26、右子树均为空）AEx3. 只有左子树只有左子树A(B)Ex4. 左右子树均非空左右子树均非空A( B , C)Ex5. 只有右子树只有右子树A( , C) A C2021-12-15练习：练习：用括号表示法描述左图的二叉树用括号表示法描述左图的二叉树 AB C D E F GTA( B( C, D( E( ,G), F) )先序遍历结果序列先序遍历结果序列的另类表示法！的另类表示法！2021-12-15 AB C D E F GT(4) 用括号表示法输出二叉树：用括号表示法输出二叉树：PrintBiTree(T) 若树不空则执行若树不空则执行 ，否则停止，否则停止 输出树的根结点值输出树的根结

27、点值(字符字符) 若根结点有孩子则执行若根结点有孩子则执行 ，否则停止，否则停止 输出左括号：输出左括号：( 递归递归处理左子树，完成后返回处理左子树，完成后返回 若存在右孩子则输出逗号：若存在右孩子则输出逗号：, 递归递归处理右子树，完成后返回处理右子树，完成后返回 输出右括号：输出右括号：) 结束结束2021-12-15(4) 用括号表示法输出二叉树：用括号表示法输出二叉树：PrintBiTree(T)void PrintBiTree ( BiTree T) / T 是指向根的指针是指向根的指针 if ( T != NULL) /若树不空则执行，否则停止若树不空则执行，否则停止 2021-

28、12-15(4) 用括号表示法输出二叉树：用括号表示法输出二叉树：PrintBiTree(T)void PrintBiTree ( BiTree T) / T 是指向根的指针是指向根的指针 if ( T != NULL) /若树不空则执行，否则停止若树不空则执行，否则停止 coutdata; /输出根结点的值输出根结点的值 /若根结点有孩子则执行，否则停止若根结点有孩子则执行，否则停止 if ( T-lchild != NULL | T-rchild != NULL) 2021-12-15(4) 用括号表示法输出二叉树：用括号表示法输出二叉树：PrintBiTree(T)void PrintB

29、iTree ( BiTree T) / T 是指向根的指针是指向根的指针 if ( T != NULL) /若树不空则执行，否则停止若树不空则执行，否则停止 coutdata; /输出根结点的值输出根结点的值 /若根结点有孩子则执行，否则停止若根结点有孩子则执行，否则停止 if ( T-lchild != NULL | T-rchild != NULL) coutlchild ); /递归处理左子树递归处理左子树 2021-12-15(4) 用括号表示法输出二叉树：用括号表示法输出二叉树：PrintBiTree(T)void PrintBiTree ( BiTree T) / T 是指向根的指

30、针是指向根的指针 if ( T != NULL) /若树不空则执行，否则停止若树不空则执行，否则停止 coutdata; /输出根结点的值输出根结点的值 /若根结点有孩子则执行，否则停止若根结点有孩子则执行，否则停止 if ( T-lchild != NULL | T-rchild != NULL) coutlchild ); /递归处理左子树递归处理左子树 if (T-rchild != NULL) cout,; /输出逗号输出逗号 2021-12-15(4) 用括号表示法输出二叉树：用括号表示法输出二叉树：PrintBiTree(T)void PrintBiTree ( BiTree T)

31、 / T 是指向根的指针是指向根的指针 if ( T != NULL) /若树不空则执行，否则停止若树不空则执行，否则停止 coutdata; /输出根结点的值输出根结点的值 /若根结点有孩子则执行，否则停止若根结点有孩子则执行，否则停止 if ( T-lchild != NULL | T-rchild != NULL) coutlchild ); /递归处理左子树递归处理左子树 if (T-rchild != NULL) coutrchild ); /递归处理右子树递归处理右子树 coutdata = ch; /保存数据保存数据 p-lchild = NULL; /初始化左右指针初始化左右指

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

33、子 st top - rchild = p; /end switch(5) 用括号表示法创建二叉树：用括号表示法创建二叉树：2021-12-15v 6.3 遍历二叉树v 树的遍历v 遍历按某条路径访问二叉树的每个结点，使每个结点被访问一次且仅被访问一次v 常用方法v 先根（序）遍历：访问根结点；依次先根遍历根的每棵子树v 后根（序）遍历：依次后根遍历每棵子树；访问根结点v 层次遍历：访问第一层结点；依次遍历第二层，第n层结点2021-12-15v二叉树遍历v先序：访问根结点；先序遍历左子树、右子树v中序：中序遍历左子树；访问根结点；中序遍历右子树v后序：后序遍历左、右子树；访问根结点v层次：从

34、上到下、从左到右访问各层结点DLRLDR、LRD、DLRRDL、RLD、DRL2021-12-15ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C先序遍历先序遍历:2021-12-15ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A C中序遍历中序遍历:2021-12-15ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列： D B C A后序遍历后序遍历:B2021-12-15-+/a*b-efcd先序遍历先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：- + a

35、 * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f2021-12-15二叉树遍历（递归）算法/二叉链表定义二叉链表定义typedef int TElemType ; typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiNode , *BiTree ;lchild data rchild 2021-12-15先序遍历（递归）算法int PreOrderTraverse ( BiTree T ) if ( T != NULL) /遍历指针不空，指向某子树根结点遍历指针不空，

36、指向某子树根结点 printf ( “%dt” , T-data ); /根根 PreOrderTraverse ( T-lchild ); /左左 PreOrderTraverse ( T-rchild ); /右右 2021-12-15主程序主程序pre( T )返回返回返回返回pre(T R);返回返回返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返

37、回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D Cint PreOrderTraverse ( BiTree T ) if ( T != NULL) printf ( “%dt” , T-data ); PreOrderTraverse ( T-lchild ); PreOrderTraverse ( T-rchild ); 2021-12-15/ 中序遍历中序遍历int InOrderTraverse ( BiTree T ) if ( T != NULL) InOrderTraverse ( T-lchild ); /左左 prin

38、tf ( “%dt” , T-data ); /根根 InOrderTraverse ( T-rchild ); /右右 2021-12-15/ 后序遍历后序遍历int PostOrderTraverse ( BiTree T ) if ( T != NULL) PostOrderTraverse ( T-lchild ); /左左 PostOrderTraverse ( T-rchild ); /右右 printf ( “%dt” , T-data ); /根根 2021-12-15说明：说明：对于先序、中序、后序遍历序列中：对于先序、中序、后序遍历序列中： 由由先序先序和和中序中序遍历结果

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

40、、后序序列相同，则该二叉树的形态为： 空树、只有根结点空树、只有根结点2021-12-15例：例：二叉树的先序、中序遍历结果如下，画出该二叉树二叉树的先序、中序遍历结果如下，画出该二叉树 先序：先序：ABCDEFG 中序：中序：CBDEAFGABFCDEG2021-12-152、一个二叉树的先序、中序和后序分别如下，其中一部分未显示、一个二叉树的先序、中序和后序分别如下，其中一部分未显示出来，试求出空格处的内容，并画出该二叉树。出来，试求出空格处的内容，并画出该二叉树。 先序：先序：_B_F_ICEH_G 中序：中序：D_KFIA_EJC_ 后序：后序：_K_FBHJ_G_A答答: ABDFK

41、ICEHJG DBKFIAHEJCG DKIFBHJEGCA练习：练习：1、二叉树的后序、中序周游结果如下，画出该二叉树。、二叉树的后序、中序周游结果如下，画出该二叉树。 后序：后序：43268751 （每位数字代表一个结点）（每位数字代表一个结点） 中序：中序：243165782021-12-15ABCDEFG按先序遍历序列，建立二叉链表按先序遍历序列，建立二叉链表A B C 0 0 D E 0 G 0 0 F 0 0 0 (0 表示空表示空) 2021-12-15BiTree createbt ( ) BiTree *bt; char ch; scanf(“%c”, &ch); /

42、读入读入 1 个字符个字符 if ( ch =0) /空空 bt = NULL; else bt = (BiTree) malloc ( sizeof ( BiNode ); bt-data = ch; bt-lchild = createbt (); /递归读入左子树递归读入左子树 bt-rchild = createbt (); /递归读入右子树递归读入右子树 按先序遍历序列，递归建立二叉链表算法按先序遍历序列，递归建立二叉链表算法2021-12-15v 6.3.2 线索二叉树v 定义：v 二叉树遍历序列中两个相邻结点互称为前驱与后继v 指向前驱或后继结点的指针称为线索v 加上线索的二叉树

43、叫线索二叉树v 按遍历序列使二叉树变为线索二叉树的过程叫线索化2021-12-15v 6.3.2 线索二叉树v 实现v n 个结点的二叉链表中，必有 n+1 个空链域v 扩展二叉链表结点：标志域 LTag、RTagv LTag： 表示 lchild 指针的含义，0左孩子；1前驱v RTag： 表示 rchild 指针的含义，0右孩子；1后继 lchild LTag data RTag rchild2021-12-15ABCDE A B D C ET先序序列：先序序列：ABCDE先序线索二叉树先序线索二叉树00001111 11v Ex.1 先序线索二叉树2021-12-15ABCDE A B

44、D C ET中序序列：中序序列：BCAED中序线索二叉树中序线索二叉树0000111111v Ex.2 中序线索二叉树2021-12-15 A B D C ET后序序列：后序序列：CBEDA后序线索二叉树后序线索二叉树0000111111v Ex.3 后序线索二叉树ABCDE2021-12-156.3.2 线索二叉树v 二叉树线索化的目的v 遍历时，不再需要栈2021-12-156.4 树和森林v 树 vs. 二叉树v 相同点：层次结构、唯一根结点v 差异点：树结点允许 2 个以上的子结点；二叉树结点最多 2 个子结点v 森林v 不相交的树集合2021-12-156.4.1 树的存储结构v 双

45、亲表示法v 孩子表示法v 多重链表v 孩子链表v 孩子兄弟表示法2021-12-156.4.1 树的存储结构 双亲表示法：子结点保存父结点位置信息v 数据域：存放结点本身信息v 双亲域：指示双亲结点在数组中位置v 6.4 树和森林/结点结构结点结构typedef struct PTNode TElemType data; int parent; PTNode;dataparent数据域数据域双亲域双亲域2021-12-156.4.1 树的存储结构 双亲表示法v 6.4 树和森林/ 双亲表示的树结构双亲表示的树结构typedef struct PTNode nodesMAX_TREE_SIZE;

46、 int r, n; PTree;012MAX_TREE_SIZEdataparent结点数组结点数组根结点位置根结点位置结点个数结点个数2021-12-15abcdefhgiacdefghib0122355516012345789dataparent如何找孩子结点如何找孩子结点如何找兄弟结点如何找兄弟结点v双亲表示法示例19根结点放在根结点放在位置位置 1结点数结点数92021-12-15 孩子表示法(多重链表)v 每个结点有多个指针域，分别指向其子树的根v 结点同构： 结点指针个数相等 树的度 Ddata child1 child2 . childDdata degree child1 c

47、hild2 . childd6.4.1 树的存储结构v 结点不同构：结点指针个数不等 结点的度 d结点的度结点的度 d树的度树的度 D2021-12-15abcdefhgi 2 3 4 5 9 7 8 6如何找双亲结点如何找双亲结点孩子表示法示例6012345789acdefghibdata firstchild192021-12-15/表头数组元素结点表头数组元素结点typedef struct TElemType data; int parent; ChildPtr firstchild; /孩子孩子链表头指针链表头指针 CTBox ;父结点在数组中的位置父结点在数组中的位置带双亲的孩子链

48、表parent：指示父结点位置firstchild：孩子链表头指针6.4.1 树的存储结构2021-12-15abcdefhgi612345789acdefghibdata 2 3 4 5 9 7 8 6012235551parent firstchild带双亲的孩子链表法示例2021-12-15孩子兄弟表示法(二叉链表)v左指针 自己的第 1 个孩子结点v右指针 自己的下一个兄弟typedef struct CSNode TElemType data; struct CSNode *firstchild, /第一个孩子第一个孩子 *nextsibling; /下一个兄弟下一个兄弟 CSNod

49、e, *CSTree;6.4.1 树的存储结构2021-12-15 孩子兄弟表示法示例abcdefhgi a b c d e f g h i 问题：破坏了树的层次关系2021-12-15 孩子兄弟表示法的另类解释！abcdefhgi a b c d e f g h i二叉链表即可表示树二叉链表即可表示树也可表示二叉树也可表示二叉树abcdefhgi2021-12-15abcdefhgi a b c d e f g h i二叉链表即可表示树，也可表示二叉树二叉链表即可表示树，也可表示二叉树树与二叉树之间可以一一对应！树与二叉树之间可以一一对应！可以相互转换可以相互转换abcdefhgi2021-

50、12-15v 将树转换成二叉树v 加线v 兄弟之间加连线v 抹线v 除左孩子外，去除与其余孩子之间的连线v 旋转v 以根结点为轴心，整树顺时针旋转 456.4.2 森林与二叉树的转换2021-12-15v 树转换成二叉树示例v 加线、抹线、旋转ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI转换得到的二叉树其右子树一定为空转换得到的二叉树其右子树一定为空加线加线抹线抹线旋转旋转2021-12-15v 二叉树转换成树v 加线v 若结点 p 是其父结点的左孩子，则将 p 的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p 的父结点连线v 抹线v 抹掉

51、原二叉树中父结点与右孩子之间的连线v 调整v 将结点按层次排列，形成树结构2021-12-15v 二叉树转换成树示例v 加线、抹线、调整ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI加线加线抹线抹线调整调整2021-12-15v 森林转换成二叉树v （树）转换v 各棵树分别转换成二叉树v （根）连线v 每棵树根结点用线相连v 旋转v 第一棵树根结点为二叉树根v 以根结点为轴顺时针旋转，构成二叉树型结构6.4.2 森林与二叉树的转换2021-12-15v 森林转换成二叉树示例ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHI

52、J树转换树转换根连线根连线旋转旋转2021-12-15v 二叉树转换成树或森林v 加线v 若结点是左孩子，则将该结点的右孩子、右孩子的右孩子，都与该结点的父结点连线v 抹线v 抹去原二叉树中所有父结点与右孩子之间的连线v 还原v 整理上两步的结果，使之结构层次分明6.4.2 森林与二叉树的转换2021-12-15v 二叉树转换成树或森林v 加线、抹线、还原ABCDEFGHIJABCDEFGHIJ加线加线抹线抹线调整调整ABCDEFGHIJABCDEFGHIJABCDEFGHIJ2021-12-15v 6.6 赫夫曼树及其应用叶结点到根的路径长度叶结点权值其中：记作：kknkkklwlwWPL1

53、v Huffman树v 设有 n 个权值 w1,w2,wnv 构造有 n 个叶结点的二叉树，其叶子结点的权值wiv WPL 最小的二叉树叫 Huffman 树结点带权路径长度结点带权路径长度：根到该结点的路径长度与该结点权值的乘积树带权路径长度树带权路径长度：所有叶结点的带权路径长度之和2021-12-15例例 有有4个结点，权值分别为个结点，权值分别为7，5，2，4，构造有，构造有4个叶子结点的二叉树个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=

54、35树的带权路径树的带权路径长度最短长度最短2021-12-15v Huffman 树的构造v 给定 n 个权值 w1,w2,wn1 初始化：构造 n 棵只有根结点的二叉树，权值为 wj2 迭代选择(贪心)：森林中选取 2 棵根结点权值最小的树作左右子树，构造一棵新二叉树v 新二叉树根结点权值 左右子树根结点权值和3 重复步骤2，直到只剩一棵树时，算法结束2021-12-15练习：练习：w = 5, 29, 7, 8, 14, 23, 3, 11 51429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231

55、48715292914871529113581923422021-12-152914871529113581923421135819234229148715295811358192342291487152958100WPL=？271Huffman 树可树可以不唯一！以不唯一！练习：练习：w = 5, 29, 7, 8, 14, 23, 3, 11 2021-12-15v Huffman 树的应用：Huffman 编码v 数据通信，压缩电文用的二进制编码v Ex. 设要传送的字符串ABACCDA(定长定长)编码：编码：A00 B01 C10 D1100010010101100 14位位若采用不等

56、长编码，让若采用不等长编码，让出现次数较多的字符尽可能用短编码出现次数较多的字符尽可能用短编码则转换的二进制字符串便可能减少则转换的二进制字符串便可能减少2021-12-15若编码为：若编码为： A0 B00 C1 D-01 关键：关键：不等长编码方案中，必须使任一字符的编码不等长编码方案中，必须使任一字符的编码都不是另一个字符的编码的前缀，即都不是另一个字符的编码的前缀，即前缀编码前缀编码 ABACCDA 000011010 9位位但：但： 0000AAAA ABA BB重码重码2021-12-15编码方案 ：A0B110C10D1110110010101110前缀编码前缀编码二叉树二叉树A

57、CBD000111规定：规定：左分支用左分支用“0”表示表示右分支用右分支用“1”表示表示前缀编码前缀编码要传送的字符串ABACCDA2021-12-15译码：从根出发，逐个接收字符，遇“0”向左、遇“1”向右，到达叶子、译出一个字符0 1 1 0 0 1 0 1 0 1 1 1 0ACBD000111A前缀编码前缀编码BA CCDA2021-12-15练习练习v 电文由字母 S, W, P, U, C, T, E, D 组成，字母出现频率(%)为 5, 25, 3, 6, 10, 11, 36, 4v 画出 Huffman 树，给出 Huffman 编码v 求出平均码长v 给出电文 swpu

58、csse 的对应编码串v 给出编码串 0001011001011 的对应电文2021-12-15v字母字母 S, W, P, U, C, T, E, D , 频率频率 5, 25, 3, 6, 10, 11, 36, 4 v 画出画出 Huffman 树，给出树，给出 Huffman 编码编码10061393625221771011114365PDCTSUWE00000001111111 S WPUCTED 0110 10 0000 0111 001 010 11 0001 2021-12-15v字母字母 S, W, P, U, C, T, E, D , 频率频率 5, 25, 3, 6, 1

59、0, 11, 36, 4 v 求出平均码长求出平均码长(4522543463103112364 4)/1002.572021-12-15v字母字母 S, W, P, U, C, T, E, D , 频率频率 5, 25, 3, 6, 10, 11, 36, 4 v 给出电文给出电文 swpucsse 的对应编码串的对应编码串v 0110 10 0000 0111 001 0110 0110 11 S WPUCTED 0110 10 0000 0111 001 010 11 0001 2021-12-15v字母字母 S, W, P, U, C, T, E, D , 频率频率 5, 25, 3,

60、6, 10, 11, 36, 4 v 给出编码串给出编码串 0001011001011 的对应电文的对应电文v DSTE10061393625221771011114365PDCTSUWE000000011111112021-12-15typedef struct unsigned int weight; unsigned int parent , lchild , rchild ; HTNode , *HuffmanTree ;下标weightparentlchildrchild123456789101112131415例例 w=5, 29, 7, 8, 14, 23, 3, 112021-12-15int Huffma