5树与二叉树2教学课件.pptVIP

B C D E F G H I J K 1．森林中第一棵树的根结点(D)； 2．森林中第一棵树的子树森林(L)； 3．森林中其它树构成的森林(R)。 森林由三部分构成： 注意下面的RGB三种颜色 二、森林的遍历 1. 先序遍历（森林） 若森林不空，则 访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林； 先序遍历森林中(除第一棵树之外)其 余树构成的森林。 即：依次从左至右对森林中的每一棵树进行先根遍历(DLR)。 ２．中序遍历（森林） 若森林不空，则 中序遍历森林中第一棵树的子树森林； 访问森林中第一棵树的根结点； 中序遍历森林中(除第一棵树之外)其 余树构成的森林。 即：依次从左至右对森林中的每一棵树进行后根遍历(LDR)。 树、森林的遍历 和 二叉树遍历的对应关系 ？ 先序遍历 后序遍历 树 二叉树 森林 先序遍历 先序遍历 中序遍历 中序遍历 小结 树、森林与二叉树的转换方法，树与森林的常用遍历方法 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 数据结构---树和二叉树 5 树与二叉树(2) 掌握二叉树的基本概念、性质和存储结构。 熟练掌握二叉树的前、中、后序遍历方法和算法 了解线索化二叉树的思想。 基本掌握树、森林与二叉树的转换方法，树与森林的常用遍历方法。 熟练掌握哈夫曼树的概念和实现方法，掌握构造霍夫曼编码的方法。 教学目标 5.1 树的类型定义 5.2 二叉树的类型定义 5.3 二叉树的存储结构 5.4 二叉树的遍历 5.5 线索二叉树 5.6 树和森林的表示方法 5.7 树和森林的遍历 5.8 哈夫曼树与哈夫曼编码 教学内容 5.6 树和森林的表示方法 树的三种存储结构 双亲表示法 孩子链表表示法 树的二叉链表(孩子-兄弟）存储表示法 A B C D E F G 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 root=0 n=7 data parent 一、双亲表示法(相当有价值): 还记得并查集吗？ struct PTNode { Elem data; int parent; // 双亲位置 } ; data parent const int MaxTreeSize = 100; 结点结构: C++语言的类型描述: struct PTree{ PTNode nodes[MaxTreeSize]; int root, n; //根的位置和结点个数 }; 树结构: A B C D E F G 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4 root=0 n=7 firstchild 1 2 3 4 5 6 二、孩子链表表示法(带双亲) data parent struct CTNode { int child; CTNode *next; }; 孩子结点结构: child next C++语言的类型描述: struct CTBox{ Elem data; int parent; // 双亲位置 CTNode *firstchild;// 孩子链的头指针 }; 双亲结点结构 data parent firstchild struct CTree{ CTBox nodes[MaxTreeSize]; int n, root; // 结点数和根的位置 }; 树结构: A B C D E F G A B C E D F G root A B C E D