[学科竞赛]第6章树和二叉树.ppt

⑴ 先根遍历： ① 访问树的根结点 ② 依次先根遍历根的各子树 6.4 树和森林 1. 树的遍历 四、树与森林的遍历 ⑴ 先根遍历： ① 访问树的根结点 ② 依次先根遍历根的各子树 6.4 树和森林 1. 树的遍历 四、树与森林的遍历 先根遍历序列：R A D E B C F G H K ⑵ 后根遍历： ① 依次后根遍历根的各子树 ② 访问树的根结点 6.4 树和森林 1. 树的遍历 四、树与森林的遍历 ⑵ 后根遍历： ① 依次后根遍历根的各子树 ② 访问树的根结点 6.4 树和森林 1. 树的遍历 四、树与森林的遍历 后根遍历序列：D E A B G H K F C R ⑶ 层次遍历： 按层次自左向右遍历 6.4 树和森林 1. 树的遍历 四、树与森林的遍历 ⑶ 层次遍历： 按层次自左向右遍历 6.4 树和森林 1. 树的遍历 四、树与森林的遍历 层次遍历序列：R A B C D E F G H K ⑴ 先序遍历： ① 访问森林中第一棵树的根结点 ② 先序遍历第一棵树中根的子树 ③ 先序遍历剩余的树构成的森林 6.4 树和森林 2. 森林的遍历 四、树与森林的遍历 ⑵ 后序遍历： ① 后序遍历第一棵树中根的子树 ② 访问第一棵树的根结点 ③ 后序遍历剩余的树构成的森林 6.4 树和森林 2. 森林的遍历 四、树与森林的遍历 ⑶ 层次遍历： 按层次自左向右遍历 6.4 树和森林 2. 森林的遍历 四、树与森林的遍历 第6章 树和二叉树 6.5 赫夫曼树及其应用 6.5 赫夫曼树及其应用 1. 路径： 一、基本概念 路径上的分支数目 2. 路径长度： 从树的根结点到每一结点的路径长度之和 3. 树的路径长度： 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 6.5 赫夫曼树及其应用 1. 路径： 一、基本概念 路径上的分支数目 2. 路径长度： 从树的根结点到每一结点的路径长度之和 3. 树的路径长度： 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 6.5 赫夫曼树及其应用 1. 路径： 一、基本概念 路径上的分支数目 2. 路径长度： 从树的根结点到每一个结点的路径长度之和 3. 树的路径长度： 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 该结点到根之间的路径长度与结点权的乘积。 6.5 赫夫曼树及其应用 4. 结点的带权路径长度： 一、基本概念 树中所有叶子结点的带权路径长度之和。 5. 树的带权路径长度： 6.5 赫夫曼树及其应用 4. 结点的带权路径长度： 一、基本概念 5. 树的带权路径长度： 该结点到根之间的路径长度与结点权的乘积。 树中所有叶子结点的带权路径长度之和。 5. 树的带权路径长度： 树中所有叶子结点的带权路径长度之和。 6.5 赫夫曼树及其应用 一、基本概念 通常记作 WPL： 其中：n —— 叶子结点数 Wi —— 第 i 个叶子结点的权值 Li —— 根到该叶子结点间的路径长度 6.4 树和森林 二、树与二叉树的转换 ⑴ 加线 ⑵ 抹线 ⑶ 调整 2. 二叉树还原成树 6.4 树和森林 二、树与二叉树的转换 ⑴ 加线 ⑵ 抹线 ⑶ 调整 2. 二叉树还原成树 ⑴ 加线：将某结点的右孩子及其下的所有右孩子，与该结点的双亲间加连线； 6.4 树和森林 二、树与二叉树的转换 ⑴ 加线 ⑵ 抹线 ⑶ 调整 2. 二叉树还原成树 ⑴ 加线：将某结点的右孩子及其下的所有右孩子，与该结点的双亲间加连线； 6.4 树和森林 二、树与二叉树的转换 2. 二叉树还原成树 ⑴ 加线 ⑵ 抹线 ⑶ 调整 ⑵ 抹线：抹去双亲与右孩子间的连线； 6.4 树和森林 二、树与二叉树的转换 2. 二叉树还原成树 ⑴ 加线 ⑵ 抹线 ⑶ 调整 ⑵ 抹线：抹去双亲与右孩子间的连线； 6.4 树和森林 二、树与二叉树的转换 2. 二叉树还原成树 ⑴ 加线 ⑵ 抹线 ⑶ 调整 ⑶ 调整：将二叉树调整成树的结构。 6.4 树和森林 二、树与二叉树的转换 2. 二叉树还原成树 ⑴ 加线 ⑵ 抹线 ⑶ 调整 ⑶ 调整：将二叉树调整成树的结构。 6.4 树和森林 树与二叉树之间可以相互转换，和树对应的二叉树，其左、右子树的实际含义是：左为孩子，右为兄弟。 二、树与二叉树的转换 6.4 树和森林 三、森林与二叉树的转换 6.4 树和森林 1. 森林转换成二叉树