2叉树.pptVIP

树和二叉树 三、树的基本术语 二叉树 4.满二叉树和完全二叉树的定义 一般二叉树，若采用顺序存储结构，则浪费空间。 二、链式存储结构 遍历二叉树 例如：二叉树如下： 算法 先序遍历二叉树的递归算法 树和森林 二、孩子表示法（1） 二、孩子表示法（2） 森林与二叉树的转换 转换后的二叉树的特点： 3. 二叉树 森林 二叉排序树的定义 建立二叉排序树 二叉排序树的查找分析 赫夫曼树及其应用 最优二叉树 ( 赫夫曼树) 赫夫曼编码 设计赫夫曼编码 练习 * * 树型结构是一类非线性结构。其中树和二叉树最为常用。 树的定义和基本术语 一、树的递归定义 例如：图6.1 树的示例 二、树的其它三种表示法 A B C D E F G H I J K 结点 结点的度 树的度 叶子（或 终端结点） 分支结点（非终端结点） 双亲 子女 兄弟 祖先 子孙 结点的层次 树的深度 有序树 无序树 森林 A B C D E F G H I J K 二叉树的定义 其特点是每个结点最多有二棵子树，并且有左右子树之分。 二叉树的性质 1. 在二叉树的第i层至多有2i-1个结点(i=1)。 2. 深度为K的二叉树至多有2k -1个结点(k=1)。 3. 对任一棵二叉树，均有 n0=n2+1 5. 具有n个结点的完全二叉树的深度为 log2n +1 二叉树的存储结构 一、顺序存储结构 仅适合于完全二叉树。 A B D E F G I J K K J I G F E D B A 1 2 3 4 5 6 7 8 9 A B D E F G I J K 0 0 0 F 0 K J I G 0 E D B A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 二叉树的每个结点是由一个数据元素和两个分别指 向左、右子女的两个分支组成。 因此， 常用的二叉树链式存储结构： Rchild data Lchild Parent Rchild data Lchild 二叉链表 三叉链表 例如：图6.8 6.3.1 遍历二叉树 即按某种有哪些信誉好的足球投注网站路径访问树中的每个结点，且仅访问一次。 若规定必须先访问左子树，后访问右子树，则遍历二叉树有三种方式： (1) 先序遍历 （即 前序遍历） (2) 中序遍历 (3) 后序遍历 A B D E F G I J K 前序遍历： A B E J F D G I K 中序遍历： J E F B A G D K I 后序遍历： J F E B G K I D A procedure PreTravel(t:integer) begin if (t0) begin write(a[t].data); PreTravel(a[t].Lchild); PreTravel(a[t].Rchild); end end; 树的存储结构 一、双亲表示法 用一组连续的空间存放每个结点的值和其父结点的位置。 type node=record data:char; father:integer end; 对于d叉树，即树的度为d,树中的结点有两种格式： ①定长格式： ②不定长格式： …… child1 childd child2 data …… Degree=k childk child1 data 对于d叉树，若有n个结点，则建立n个孩子链表。 例如：图6.14 (p137) 三、孩子兄弟表示法 即二叉链表表示法，左链第一子女，右链下一个兄弟。 data next first 由于两者都可以采用二叉链表作为存储结构，故可导出两者之间的对应关系。 1. 树 二叉