数和叉树.pptVIP

树和森林（本节概述） 树的存储结构 森林与二叉树的转换 树和森林的遍历 树的存储结构 一、双亲表示法 二、孩子链表表示法 三、树的二叉链表(孩子-兄弟）存储表示法 双亲表示法 因为树中的每个结点都有唯一的一个双亲结点，可用一个一维数组来存储树中的各个结点，其中包括结点本身的信息以及结点的双亲结点在数组中的序号。其结点表示可描述为： Typedef struct PtNode { ElemType data； int parent； }PTNode； 求某个结点的双亲结点是非常容易的，但要查找某一个结点的孩子时，则要访问整个数组。 A B C D E F G H I J 0 1 7 2 3 4 5 6 A -1 B 0 C 0 D 1 E 1 F 2 I 2 J 2 G 4 H 4 8 9 孩子链表表示法 将每个结点的孩子用链表连接起来，构成一个单链表。单链表的结构由两个域组成，一个存放孩子结点在一维数组中的序号，另一个域指向下一个孩子。 1 2 ∧ 3 4 ∧ 5 8 9 ∧ 0 1 7 2 3 4 5 6 A B C D ∧ E F ∧ I ∧ J ∧ G ∧ H ∧ 6 7 ∧ 9 8 孩子-兄弟表示法 这种表示法以二叉链表作为树的存储结构，其结点结构为：一个数据域和两个指针域，其中一个指针指向它的第一个孩子结点，另一个指针指向它的兄弟结点。 A ∧ ∧ G.. ∧ H ∧ B C ∧ ∧ D E ∧ ∧ F ∧ C ∧ C ∧ 森林与二叉树的转换 树和森林转换为二叉树 1、一般树转换为二叉树 （1）连线：在各兄弟之间用虚线相连。 （2）抹线：对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。 （3）旋转：以树的根结点为轴心，将整棵树顺时针转动45°度角，使之结构层次分明。 树和森林转换为二叉树 树和森林转换为二叉树 树和森林转换为二叉树 2、森林转换为二叉树 （1）将森林中的每棵树转换成相应的二叉树，形成二叉树的森林。 （2）按森林中的先后顺序，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子。 二叉树还原为树和森林 1、二叉树还原为一般树步骤: (1)加线。若某结点是双亲结点的左孩子，则将该结点的右孩子以及当且仅当连续地沿着右孩子的右链不断有哪些信誉好的足球投注网站到的所有右孩子，都分别与结点的双亲结点用虚线连接。 (2)抹线：把原二叉树中所有双亲结点与其右孩子连线抹去。 (3)整理、旋转：把虚线改为实线；把结点按层次排列。 二叉树还原为树和森林 2、二叉树还原为森林 （1）抹线; （2）还原。 森林的遍历 1．森林中第一棵树的根结点； 2．森林中第一棵树的子树森林； 3．森林中其它树构成的森林。 森林由三部分构成： A B C D E F G H I J 森林的遍历(先序) 若森林不空，则 (1)访问森林中第一棵树的根结点； (2)先序遍历森林中第一棵树的子树森林； (3)先序遍历森林中(除第一棵树之外)其 余树构成的森林。 中序、后序和先序类似 遍历方法小结 先根遍历 后根遍历 树 二叉树 森林 先序遍历 先序遍历 中序遍历 中序遍历 目 录 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 树与等价问题 6.6 赫夫曼树及其应用 赫夫曼树的定义 赫夫曼（Huffman）树，也称最优二叉树，是指一类带权路径最短的树。 1．赫夫曼树的基本概念 （1）路径、路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支个数称为路径长度。 （2）树的路径长度：从根结点到树中每个结点的路径长度之和。 赫夫曼树的定义 （3）结点的带权路径长度：从根结点到该结点的路径长度与该结点所带的权值的乘积。 （4）树的带权路径长度：树中所有叶子结点的带权路径长度之和。记为： 赫夫曼树的定义 （5）赫夫曼树：设有n个权值 { W1，W2，…，Wn }，构造一个具有n个叶子结点的二叉树，每个叶子结点带有权值Wi，在所有的二叉树中，带权路径长度WPL最小的二叉树称为赫夫曼树。 赫夫曼树 构造赫夫曼树 （1）根据给定的n个权值{W1，W2，…，Wn}构造n棵只有一个根结点的二叉树。从