数据结构课件C版第六章.ppt

Data StructureCh6 Tree 第六章 树 树 二叉树 线索二叉树 树与森林 Huffman树 * Data StructureCh6 Tree 树 -树的定义和术语 树：一棵树 T，简称为树，它是n (n0) 个结点的 有限集合。当n = 0时，T 称为空树；否则，T 是非 空树，记作 其中，r 是一个特定的称为根(root)的结点，它 没有直接前驱；根以外的其他结点划分为 m (m 0) 个互不相交的有限集合T1, T2, , Tm，每个集合又是 一棵树，并且称之为根的子树。 Date Data StructureCh6 Tree 树 -树的定义和术语 相关术语 子女：若结点的子树非空，结点子树的根即为该 结点的子女。 双亲：若结点有子女，该结点是子女双亲。 兄弟：同一结点的子女互称为兄弟。 度：结点的子女个数即为该结点的度；树中各个 结点的度的最大值称为树的度。 分支结点：度不为0的结点即为分支结点，亦称为 非终端结点。 Date Data StructureCh6 Tree 树 -树的定义和术语 叶结点：度为0的结点即为叶结点，亦称为终端结 点。 祖先：某结点到根结点的路径上的各个结点都是 该结点的祖先。 子孙：某结点的所有下属结点，都是该结点的子 孙。 结点的层次：规定根结点在第一层，其子女结点 的层次等于它的层次加一。以此类推。 深度：结点的深度即为结点的层次；离根最远结 点的层次即为树的深度。 Date Data StructureCh6 Tree 树 -树的定义和术语 高度：规定叶结点的高度为1，其双亲结点的高度 等于它的高度加一。 树的高度：等于根结点的高度，即根结点所有子 女高度的最大值加一。 有序树：树中结点的各棵子树 T0, T1, 是有次序 的，即为有序树。 无序树：树中结点的各棵子树之间的次序是不重 要的，可以互相交换位置。 森林：森林是m（m0）棵树的集合。 Date Data StructureCh6 Tree 树 -树的抽象数据类型 教材 p118-120 Date Data StructureCh6 Tree 二叉树 -二叉树的定义 一棵二叉树是结点的一个有限集合，该集合或者 为空，或者是由一个根结点加上两棵分别称为左子 树和右子树的、互不相交的二叉树组成。 Date Data StructureCh6 Tree 二叉树 -二叉树的性质 性质1 若二叉树结点的层次从 1 开始, 则在二叉 树的第 i (i1)层最多有 2i-1 个结点。 证明用数学归纳法 性质2 深度为 k (k0) 的二叉树最少有 k 个结点 ，最多有 2k-1个结点。 证明：因为每一层最少要有1个结点，因此，最少 结点数为 k。最多结点个数借助性质1用求等比级数 前k项和的公式20 +21 +22 + +2k-1 = 2k-1 Date Data StructureCh6 Tree 二叉树 -二叉树的性质 性质3 对任何一棵二叉树，如果其叶结点有 n0 个 , 度为 2 的非叶结点有 n2 个, 则有 n0n21 证明：若设度为 1 的结点有 n1 个，总结点数 为n，总边数为e，则根据二叉树的定义， n = n0+n1+n2 , e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1则 n2 = n0-1 n0 = n2+1 Date Data StructureCh6 Tree 二叉树 -二叉树的性质 定义1 满二叉树 (Full Binary Tree) ：深度为k的满 二叉树是有2k-1个结点的二叉树。 定义义2 完全二叉树 (Complete Binary Tree)：若设 二叉树的深度为 k，则共有 k 层。除第 k 层外，其 它各层 (1k-1) 的结点数都达到最大个数，第k层 从右向左连续缺若干结点，这就是完全二叉树。 Date Data StructureCh6 Tree 二叉树 -二叉树的性质 性质4 具有 n (n0) 个结点的完全二叉树的深度为 log2(n+1)。 证明： 设完全二叉树的深度为k，则有2k-1-1 1, 则 i 的双亲为i2； 若2*i data) if (PreOrderTraverse(T-lchild, Visit) if (PreOrderTraverse(T-rchild, Visit) return OK; return ERROR; else return OK; / PreOrderTraverse Date Data StructureCh6 Tree 二叉树 -二叉树的遍历 中序遍历二叉树T的非递归算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.2.采用二叉链表存储结构，Visit是对数据元 /素操作的应用函数。中序遍历二叉树T的非递 归算 /法，对每个数据元素调用函数Visit。 Date Data StructureCh6 Tree 二叉树 -二叉树的遍历 InitStack(S); Push(S, T); / 根指针进栈 while (!StackEmpty(S) while (GetTop(S, p) Pop(S, p); / 空指针退栈 if (!StackEmpty(S) / 访问结点，向右一步 Pop(S, p); if (!Visit(p-data) return ERROR; Push(S, p-rchild); return OK; / InOrderTraverse Date Data StructureCh6 Tree 二叉树 -二叉树的遍历 中序遍历二叉树T的非递归算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.3.采用二叉链表存储结构，Visit是对数据 /元素操作的应用函数。中序遍历二叉树T的非递归 /算法，对每个数据元素调用函数Visit。 Date Data StructureCh6 Tree 二叉树 -二叉树的遍历 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; / InOrderTraverse Date Data StructureCh6 Tree 二叉树 -以递归方式建立二 叉树 BiTree CreateBiTree(BiTree scanf(“%c“, if (ch=#) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) return ERROR; T-data = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return T; / CreateBiTree Date Data StructureCh6 Tree 二叉树 例1：给定一棵二叉树的先序序列EBADCFHGIKJ 和中序序列ABCDEFGHIJK，画出这颗二叉树。 Date Data StructureCh6 Tree 二叉树 例2：给定一棵二叉树的中序序列DCBGEAHFIJK 和后序序列DCEGBFHKJIA，画出这颗二叉树。 Date Data StructureCh6 Tree 二叉树 例3：给定一棵二叉树的先序和后序序列不能确 定一棵二叉树。 Date Data StructureCh6 Tree 线索二叉树 -线索二叉树的 概念 为什么提出线索二叉树？ 遍历的过程实质上是对一个非线性结构进行线性 化的操作，使每个结点（除第一个和最后一个）在 这个线性序列中有且仅有一个直接前驱和直接后继 。二叉树中只存储了左右孩子的信息，因此，前驱 和后继的信息无法直接找到。就提出了线索二叉树 的概念。 又因为n个结点的二叉链表中有n+1个空链域，从 而得到线索二叉树的存储结构如下。 Date Data StructureCh6 Tree 线索二叉树 -线索二叉树的 概念 规定：若结点有左子树，则lchild指示其左孩子， 否则令lchild指示其前驱；若结点有右子树，则其 rchild域指示其右孩子，否则令rchild指示其后继。 为避免混淆，增加两个标志域：LTag为0（1）表示 lchild指向左孩子（前驱），RTag为0（1）表示 rchild指向右孩子（后继）。 Date Data StructureCh6 Tree 线索二叉树 -线索二叉树的 概念 其中，指向结点前驱和后继的指针叫做线索。加 上线索的二叉树称为线索二叉树。对二叉树以某种 次序遍历使其变为线索二叉树的过程叫线索化。 Date Data StructureCh6 Tree 线索二叉树 -线索二叉树的 概念 Date Data StructureCh6 Tree 线索二叉树-二叉树的二叉线索存储 表示 typedef enum PointerTag Link, Thread ; / Link=0:指针，Thread=1:线索 typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerTag LTag, RTag; / 左右标志 BiThrNode, *BiThrTree; Date Data StructureCh6 Tree 线索化的实质是将二叉链表中的空指针改为指向 前驱或后继的线索，而前驱和后继的信息只有在遍 历时才能得到，因此线索化的过程即为在遍历的过 程中修改空指针的过程。 线索二叉树 -通过中序遍历建立中序线索化二叉树 Date Data StructureCh6 Tree 线索二叉树 -通过中序遍历建立中序线索化二叉树 Status InOrderThreading(BiThrTree 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; / InOrderThreading Date Data StructureCh6 Tree 线索二叉树 -通过中序遍历建立中序线索化二叉树 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); / 右子树线索化 / InThreading Date Data StructureCh6 Tree 线索二叉树 -中序遍历二叉线索链表表示的二叉树 Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType) / 算法6.5 p = 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 Visit(p-data); / 访问后继结点 p = p-rchild; / p进至其右子树根 return OK; / InOrderTraverse_Thr Date Data StructureCh6 Tree 线索二叉树 -寻找当前结点在中序下的后继 寻找当前结点在中序下的后继 后继为右 子女结点 后继为当前结 点右子树的中序 下的第一个结点 ！=NULL 无后继无此情况=NULL =1=0 RTag rchild Date Data StructureCh6 Tree 线索二叉树 -寻找当前结点在中序下的后继 寻找当前结点在中序下的前驱 前驱为 左子女结 点 前驱为当前结点左 子树中序下的最后 一个结点 ！=NULL 无前驱无此情况=NULL =1=0 LTag lchild Date Data StructureCh6 Tree 树与森林 -树的存储表示 双亲表示法（父指针表示法） 以一组连续的存储单元来存放树中的结点，每个 结点有两个域，一个是data域，用来存放数据元素 ，一个是parent域，用来存放指示其父结点位置的 指针。 这种存储表示适合经常需要寻找父结点的应用。 Date Data StructureCh6 Tree 树与森林 -树的存储表示 树的双亲表存储表示 #define MAX_TREE_SIZE 100 typedef struct PTNode /结点结构 TElemType data; int parent; / 双亲位置域 PTNode; typedef struct /树结构 PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree; Date Data StructureCh6 Tree 树与森林 -树的存储表示 孩子表示法（子女链表表示法） 为树中每个结点设置一个子女链表，并将这些结 点的数据和对应子女链表的头指针放在一个向量中 ，就构成了子女链表表示。 这种存储表示适合需要频繁寻找子女的应用。无 序树情形链表中各结点顺序任意，有序树必须自左 向右链接各个子女结点。 Date Data StructureCh6 Tree 树与森林 -树的存储表示 树的孩子链表存储表示 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; Date Data StructureCh6 Tree 树与森林 -树的存储表示 孩子兄弟表示法（子女-兄弟链表表示法） 子女-兄弟链表表示法也称为树的二叉树表示。他 的每个结点的度为2 ，是最节省存储空间的树的存 储表示。每个结点由三个域组成： firstChild 指向该结点的第一个子女结点。无序树 时，可任意指定一个结点为第一个子女。 nextSibling 指向该结点的下一个兄弟。任一结点 在存储时总是有顺序的。 Date Data StructureCh6 Tree 树与森林 -树的存储表示 孩子兄弟表示法（子女-兄弟链表表示法） Date Data StructureCh6 Tree 树与森林 -树的存储表示 树的二叉链表存储表示 typedef struct CSNode TElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree; Date Data StructureCh6 Tree 树与森林 -森林与二叉树的转换 将一般树化为二叉树表示就是用树的子女-兄弟表 示来存储树的结构。 森林与二叉树表示的转换可以借助树的二叉树表 示来实现。 Date Data StructureCh6 Tree 树与森林 -森林与二叉树的转换 森林转化成二叉树的规则 若 F 为空，即 n = 0，则对应的二叉树 B 为空树 。 若 F 不空，则 二叉树 B 的根是 F 第一棵树 T1 的根； 其左子树为B (T11, T12, , T1m)，其中 ，T11, T12, , T1m 是 T1 的根的子树； 其右子树为 B (T2, T3, , Tn)，其中， T2, T3, , Tn 是除 T1 外其它树构成的森林。 Date Data StructureCh6 Tree 树与森林 -森林与二叉树的转换 二叉树转换为森林的规则 如果 B 为空，则对应的森林 F 也为空。 如果 B 非空，则 F 中第一棵树 T1 的根为 B 的根； T1 的根的子树森林 T11, T12, , T1m 是由 B 的根的左子树 LB 转换而来； F 中除了 T1 之外其余的树组成的森林 T2, T3, , Tn 是由 B 的根的右子树 RB 转 换而成的森林。 Date Data StructureCh6 Tree 树与森林 -森林与二叉树的转换 Date Data StructureCh6 Tree 树与森林 -树的遍历 深度优先遍历 先根次序遍历：先访问树的根结点，然后先根遍 历根的每棵子树。树的先根遍历结果与其对应二叉 树表示的前序遍历结果相同。树的先根遍历可以借 助对应二叉树的前序遍历算法实现。 后根次序遍历：先依次后根遍历每棵子树，然后 访问根结点。树的后根遍历结果与其对应二叉树表 示的中序遍历结果相同。树的后根遍历可以借助对 应二叉树的中序遍历算法实现。 Date Data StructureCh6 Tree 树与森林 -森林的遍历 森林的遍历也分为深度优先遍历和广度优先遍 历，深度优先遍历又可分为先根次序遍历和后根次 序遍历。 深度优先遍历 给定森林 F，若 F = ，则遍历结束。否则 若F = T1 = r1, T11, , T1k , T2, ., Tm，则可以 导出先根遍历、后根遍历两种方法。其中，r1是第 一棵树的根结点，T11, , T1k是第一棵树的子树 森林，T2, .,Tm是除去第一棵树之后剩余的树构 成的森林。 Date Data StructureCh6 Tree 树与森林 -森林的遍历 森林的先根次序遍历 若森林F = ，返回；否则访问森林的根（也是第 一棵树的根）r1；先根遍历森林第一棵树的根的子 树森林T11, , T1k；先根遍历森林中除第一棵树 外其他树组成的森林T2, .,Tm。 森林的后根次序遍历 若森林 F = ，返回；否则后根遍历森林 F 第一 棵树的根结点的子树森林T11, , T1k；访问森林 的根结点 r1；后根遍历森林中除第一棵树外其他 树组成的森林T2, ., Tm。 Date Data StructureCh6 Tree 树与森林 -森林的遍历 森林的先根次序遍历和后根次序遍历分别对应为 二叉树的前序遍历和中序遍历。 广度优先遍历 若森林 F 为空，返回； 否则依次遍历各棵树的根结点；依次遍历各棵树 根结点的所有子女；依次遍历这些子女结点的子女 结点； Date Data StructureCh6 Tree Huffman树 -相关概念 路径长度 (Path Length) 两个结点之间的路径长度 PL 是连接两 结点的路径上的分支数。 树的外部路径长度是各叶结点（外结 点）到根结点的路径长度之和 EPL。 树的内部路径长度是各非叶结点（内 结点）到根结点的路径长度之和 IPL。 树的路径长度 PL = EPL + IPL。 Date Data StructureCh6 Tree Huffman树 -相关概念 n 个结点的二叉树的路径长度不小于下述数列前 n 项的和，即 Date Data StructureCh6 Tree Huffman树 -相关概念 其路径长度最小者为 完全二叉树满足这个要求。 带权路径长度 (Weighted Path Length, WPL) 树的带权路径长度为树中所有叶子结点的带权路 径长度之和。 Date Data StructureCh6 Tree Huffman树 -相关概念 Date Data StructureCh6 Tree Huffman树 -相关概念 Huffman树 假设有n个权值w1,w2,wn，试构造一棵有n 个叶子结点的二叉树，每个叶子结点带权为wi，则 其中带权路径长度WPL最小的二叉树为最优二叉树 ，即Huffman树。 Date Data StructureCh6 Tree Huffman树 -Huffman树的构造算 法 1.根据给定的n个权值w1,w2,wn构造n棵二叉树的 集合F=T1，T2，Tn，其中每棵二叉树Ti中只 有一个带权为w