数据结构课件C版第六章

1、Data StructureCh6 Tree 2022-5-25mayan 第六章 树树树二叉树二叉树线索二叉树线索二叉树树与森林树与森林HuffmanHuffman树树Data StructureCh6 Tree2022-5-25mayan 树 -树的定义和术语 树树：一棵树 T，简称为树，它是n (n0) 个结点的有限集合。当n = 0时，T 称为空树空树；否则，T 是非空树非空树，记作其中，r 是一个特定的称为根根(root)的结点，它没有直接前驱；根以外的其他结点划分为 m (m 0) 个互不相交的有限集合T1, T2, , Tm，每个集合又是一棵树，并且称之为根的子树子树。00n,T

2、,.,T,Tr,n,Tm21Data StructureCh6 Tree2022-5-25mayan 树 -树的定义和术语 相关术语子女子女：若结点的子树非空，结点子树的根即为该结点的子女。双亲：双亲：若结点有子女，该结点是子女双亲。兄弟兄弟：同一结点的子女互称为兄弟。度：度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度树的度。分支结点：分支结点：度不为0的结点即为分支结点，亦称为非终端结点。Data StructureCh6 Tree2022-5-25mayan 树 -树的定义和术语 叶结点叶结点：度为0的结点即为叶结点，亦称为终端结点。祖先祖先：某结点到根结点的路径上的

3、各个结点都是该结点的祖先。子孙子孙：某结点的所有下属结点，都是该结点的子孙。结点的层次结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以此类推。深度深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度树的深度。Data StructureCh6 Tree2022-5-25mayan 树 -树的定义和术语 高度高度：规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。树的高度树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。有序树有序树：树中结点的各棵子树 T0, T1, 是有次序的，即为有序树。无序树无序树：树中结点的各棵子树之间的次序是不重要的，可

4、以互相交换位置。森林森林：森林是m（m0）棵树的集合。 Data StructureCh6 Tree2022-5-25mayan 树 -树的抽象数据类型教材教材 p118-120Data StructureCh6 Tree2022-5-25mayan 二叉树 -二叉树的定义 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 0,0nTTrnTRLData StructureCh6 Tree2022-5-25mayan 二叉树 -二叉树的性质 性质性质1 若二叉树结点的层次从 1 开始, 则在二叉树的第 i (i1)层最多

5、有 2i-1 个结点。 证明用数学归纳法性质性质2 深度为 k (k0) 的二叉树最少有 k 个结点，最多有 2k-1个结点。证明：因为每一层最少要有1个结点，因此，最少结点数为 k。最多结点个数借助性质1用求等比级数前k项和的公式20 +21 +22 + +2k-1 = 2k-1Data StructureCh6 Tree2022-5-25mayan 二叉树 -二叉树的性质 性质性质3 对任何一棵二叉树，如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有 n0n21证明：若设度为 1 的结点有 n1 个，总结点数为n，总边数为e，则根据二叉树的定义， n = n0+n1+n

6、2 , e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1则 n2 = n0-1 n0 = n2+1 Data StructureCh6 Tree2022-5-25mayan 二叉树 -二叉树的性质 定义定义1 满二叉树 (Full Binary Tree) ：深度为k的满二叉树是有2k-1个结点的二叉树。定义定义2 完全二叉树 (Complete Binary Tree)：若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。 Data StructureCh6

7、Tree2022-5-25mayan 二叉树 -二叉树的性质 性质性质4 具有 n (n0) 个结点的完全二叉树的深度为 log2(n+1)。证明：设完全二叉树的深度为k，则有2k-1-1 n 2k-1 即 2k-1 n+12k ，取对数 k-1 1, 则 i 的双亲为 i2；3)若2*i = n, 则 i 的左子女为 2*i；4)若2*i+1 data) if (PreOrderTraverse(T-lchild, Visit) if (PreOrderTraverse(T-rchild, Visit) return OK; return ERROR; else return OK; / P

8、reOrderTraverseData StructureCh6 Tree2022-5-25mayan 二叉树 -二叉树的遍历中序遍历二叉树T的非递归算法Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.2.采用二叉链表存储结构，Visit是对数据元/素操作的应用函数。中序遍历二叉树T的非递归算/法，对每个数据元素调用函数Visit。 Data StructureCh6 Tree2022-5-25mayan 二叉树 -二叉树的遍历 InitStack(S); Push(S, T); / 根指针进栈 while (!

9、StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); Pop(S, p); / 空指针退栈 if (!StackEmpty(S) / 访问结点，向右一步 Pop(S, p); if (!Visit(p-data) return ERROR; Push(S, p-rchild); return OK; / InOrderTraverseData StructureCh6 Tree2022-5-25mayan 二叉树 -二叉树的遍历中序遍历二叉树T的非递归算法Status InOrderTraverse(BiTree T, Status

10、 (*Visit)(ElemType) / 算法6.3.采用二叉链表存储结构，Visit是对数据/元素操作的应用函数。中序遍历二叉树T的非递归/算法，对每个数据元素调用函数Visit。Data StructureCh6 Tree2022-5-25mayan 二叉树 -二叉树的遍历 InitStack(S); p = T; while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; else Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InO

11、rderTraverseData StructureCh6 Tree2022-5-25mayan 二叉树 -以递归方式建立二叉树BiTree CreateBiTree(BiTree &T) / 算法6.4 / 按先序次序输入二叉树中结点的值（一个字/符），#字符表示空树，构造二叉链表表示的二/叉树T。 Data StructureCh6 Tree2022-5-25mayan 二叉树 -以递归方式建立二叉树 char ch; scanf(%c,&ch); if (ch=#) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) re

12、turn ERROR; T-data = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return T; / CreateBiTreeData StructureCh6 Tree2022-5-25mayan 二叉树 例1：给定一棵二叉树的先序序列EBADCFHGIKJ和中序序列ABCDEFGHIJK，画出这颗二叉树。Data StructureCh6 Tree2022-5-25mayan 二叉树 例2：给定一棵二叉树的中序序列DCBGEAHFIJK和后序序列DCEGBFHKJIA，画出这

13、颗二叉树。Data StructureCh6 Tree2022-5-25mayan 二叉树 例3：给定一棵二叉树的先序和后序序列不能确定一棵二叉树。Data StructureCh6 Tree2022-5-25mayan 线索二叉树 -线索二叉树的概念为什么提出线索二叉树？遍历的过程实质上是对一个非线性结构进行线性化的操作，使每个结点（除第一个和最后一个）在这个线性序列中有且仅有一个直接前驱和直接后继。二叉树中只存储了左右孩子的信息，因此，前驱和后继的信息无法直接找到。就提出了线索二叉树的概念。又因为n个结点的二叉链表中有n+1个空链域，从而得到线索二叉树的存储结构如下。Data Struct

14、ureCh6 Tree2022-5-25mayan 线索二叉树 -线索二叉树的概念规定：若结点有左子树，则lchild指示其左孩子，否则令lchild指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。为避免混淆，增加两个标志域：LTag为0（1）表示lchild指向左孩子（前驱），RTag为0（1）表示rchild指向右孩子（后继）。Data StructureCh6 Tree2022-5-25mayan 线索二叉树 -线索二叉树的概念其中，指向结点前驱和后继的指针叫做线索线索。加上线索的二叉树称为线索二叉树线索二叉树。对二叉树以某种次序遍历使其变为线索

15、二叉树的过程叫线索化。线索化。 Data StructureCh6 Tree2022-5-25mayan 线索二叉树 -线索二叉树的概念Data StructureCh6 Tree2022-5-25mayan 线索二叉树-二叉树的二叉线索存储表示typedef enum PointerTag Link, Thread ; / Link=0:指针，Thread=1:线索typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerTag LTag, RTag; / 左右标志 BiT

16、hrNode, *BiThrTree;Data StructureCh6 Tree2022-5-25mayan 线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱和后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。 线索二叉树-通过中序遍历建立中序线索化二叉树Data StructureCh6 Tree2022-5-25mayan 线索二叉树-通过中序遍历建立中序线索化二叉树Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 算法6.6 if (!(Thrt = (BiThrTree)

17、malloc(sizeof(BiThrNode) exit(OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 右指针回指 if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); / 算法6.7 pre-rchild = Thrt; pre-RTag = Thread; Thrt-rchild = pre; return OK; / InOrderThreadingData StructureCh6 Tree

18、2022-5-25mayan 线索二叉树-通过中序遍历建立中序线索化二叉树void InThreading(BiThrTree p) / 算法6.7 if (p) InThreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持pre指向p的前驱 InThreading(p-rchild); / 右子树线索化 / InThreadingDa

19、ta StructureCh6 Tree2022-5-25mayan 线索二叉树-中序遍历二叉线索链表表示的二叉树Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType) / 算法6.5p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; while (p-RTag=Thread & p-rchild!=T) p = p-rchild;

20、Visit(p-data); / 访问后继结点 p = p-rchild; / p进至其右子树根 return OK; / InOrderTraverse_ThrData StructureCh6 Tree2022-5-25mayan 线索二叉树-寻找当前结点在中序下的后继 寻找当前结点在中序下的后继 后继为右子女结点后继为当前结点右子树的中序下的第一个结点！=NULL无后继无此情况=NULL=1=0RTagrchildData StructureCh6 Tree2022-5-25mayan 线索二叉树-寻找当前结点在中序下的后继 寻找当前结点在中序下的前驱前驱为左子女结点前驱为当前结点左子树

21、中序下的最后一个结点！=NULL无前驱无此情况=NULL=1=0LTaglchildData StructureCh6 Tree2022-5-25mayan 树与森林 -树的存储表示 双亲表示法（父指针表示法） 以一组连续的存储单元来存放树中的结点，每个结点有两个域，一个是data域，用来存放数据元素，一个是parent域，用来存放指示其父结点位置的指针。这种存储表示适合经常需要寻找父结点的应用。Data StructureCh6 Tree2022-5-25mayan 树与森林 -树的存储表示 树的双亲表存储表示 #define MAX_TREE_SIZE 100typedef struct

22、PTNode /结点结构 TElemType data; int parent; / 双亲位置域 PTNode; typedef struct /树结构 PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;Data StructureCh6 Tree2022-5-25mayan 树与森林 -树的存储表示 孩子表示法（子女链表表示法）为树中每个结点设置一个子女链表，并将这些结点的数据和对应子女链表的头指针放在一个向量中，就构成了子女链表表示。这种存储表示适合需要频繁寻找子女的应用。无序树情形链表中各结点顺序任意，有序树必须自左向右链接

23、各个子女结点。Data StructureCh6 Tree2022-5-25mayan 树与森林 -树的存储表示 树的孩子链表存储表示typedef struct CTNode /孩子结点结构 int child; struct CTNode *next; *ChildPtr;typedef struct /双亲结点结构 TElemType data; ChildPtr firstchild; / 孩子链的头指针 CTBox;typedef struct /树结构 CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;Data Struc

24、tureCh6 Tree2022-5-25mayan 树与森林 -树的存储表示 孩子兄弟表示法（子女-兄弟链表表示法）子女-兄弟链表表示法也称为树的二叉树表示。他的每个结点的度为2 ，是最节省存储空间的树的存储表示。每个结点由三个域组成：firstChild 指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。nextSibling 指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。Data StructureCh6 Tree2022-5-25mayan 树与森林 -树的存储表示 孩子兄弟表示法（子女-兄弟链表表示法）Data StructureCh6 Tree2022-

25、5-25mayan 树与森林 -树的存储表示 树的二叉链表存储表示typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;Data StructureCh6 Tree2022-5-25mayan 树与森林 -森林与二叉树的转换将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。森林与二叉树表示的转换可以借助树的二叉树表示来实现。Data StructureCh6 Tree2022-5-25mayan 树与森林 -森林与二叉树的转换森林转化成二叉树的规则

26、若 F 为空，即 n = 0，则对应的二叉树 B 为空树。若 F 不空，则i.二叉树 B 的根是 F 第一棵树 T1 的根；ii.其左子树为B (T11, T12, , T1m)，其中，T11, T12, , T1m 是 T1 的根的子树；iii.其右子树为 B (T2, T3, , Tn)，其中，T2, T3, , Tn 是除 T1 外其它树构成的森林。Data StructureCh6 Tree2022-5-25mayan 树与森林 -森林与二叉树的转换二叉树转换为森林的规则如果 B 为空，则对应的森林 F 也为空。如果 B 非空，则i.F 中第一棵树 T1 的根为 B 的根；ii.T1

27、的根的子树森林 T11, T12, , T1m 是由 B 的根的左子树 LB 转换而来；iii.F 中除了 T1 之外其余的树组成的森林 T2, T3, , Tn 是由 B 的根的右子树 RB 转换而成的森林。Data StructureCh6 Tree2022-5-25mayan 树与森林 -森林与二叉树的转换Data StructureCh6 Tree2022-5-25mayan 树与森林 -树的遍历 深度优先遍历先根次序遍历：先访问树的根结点，然后先根遍历根的每棵子树。树的先根遍历结果与其对应二叉树表示的前序遍历结果相同。树的先根遍历可以借助对应二叉树的前序遍历算法实现。后根次序遍历：先

28、依次后根遍历每棵子树，然后访问根结点。树的后根遍历结果与其对应二叉树表示的中序遍历结果相同。树的后根遍历可以借助对应二叉树的中序遍历算法实现。Data StructureCh6 Tree2022-5-25mayan 树与森林 -森林的遍历森林的遍历也分为深度优先遍历和广度优先遍历，深度优先遍历又可分为先根次序遍历和后根次序遍历。 深度优先遍历给定森林 F，若 F = ，则遍历结束。否则若F = T1 = r1, T11, , T1k , T2, ., Tm，则可以导出先根遍历、后根遍历两种方法。其中，r1是第一棵树的根结点，T11, , T1k是第一棵树的子树森林，T2, .,Tm是除去第一棵

29、树之后剩余的树构成的森林。Data StructureCh6 Tree2022-5-25mayan 树与森林 -森林的遍历森林的先根次序遍历若森林F = ，返回；否则访问森林的根（也是第一棵树的根）r1；先根遍历森林第一棵树的根的子树森林T11, , T1k；先根遍历森林中除第一棵树外其他树组成的森林T2, .,Tm。森林的后根次序遍历若森林 F = ，返回；否则后根遍历森林 F 第一棵树的根结点的子树森林T11, , T1k；访问森林的根结点 r1；后根遍历森林中除第一棵树外其他树组成的森林T2, ., Tm。 Data StructureCh6 Tree2022-5-25mayan 树与森

30、林 -森林的遍历森林的先根次序遍历和后根次序遍历分别对应为二叉树的前序遍历和中序遍历。广度优先遍历若森林 F 为空，返回；否则依次遍历各棵树的根结点；依次遍历各棵树根结点的所有子女；依次遍历这些子女结点的子女结点；Data StructureCh6 Tree2022-5-25mayan Huffman树 -相关概念路径长度 (Path Length)两个结点之间的路径长度两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。树的外部路径长度树的外部路径长度是各叶结点（外结点）到根结点的路径长度之和 EPL。树的内部路径长度树的内部路径长度是各非叶结点（内结点）到根结点的路径长度之和 IP

31、L。树的路径长度树的路径长度 PL = EPL + IPL。Data StructureCh6 Tree2022-5-25mayan Huffman树 -相关概念n 个结点的二叉树的路径长度不小于下述数列前 n 项的和，即niiPL12log332222110Data StructureCh6 Tree2022-5-25mayan Huffman树 -相关概念其路径长度最小者为完全二叉树满足这个要求。带权路径长度 (Weighted Path Length, WPL)树的带权路径长度为树中所有叶子结点的带权路径长度之和。niiPL12logniiilwWPL1Data StructureCh6 Tree2022-5-25mayan Huffman树 -相关概念Data StructureCh6 Tree2022-5-25mayan Huffman树 -相关概念Huffman树假设有n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树为最优二叉树，即Huffman树。Data StructureCh6 Tree2022-5-25mayan Huffman树 -Huffman树的构造算法