[工作范文]第6章_树和二叉树.ppt

树的定义和基本术语 二叉树 遍历二叉树和线索二叉树 树和森林 赫夫曼树及其应用 树 的 定 义 树 的 表 示 （一） 树 的 表 示 （二） 树的实例（二） ADT树的 定 义 树的 基本术语 二叉树的概念 二叉树的性质 二叉树的链式存储表示：表示二叉树的链 表中的结点至少包含三个域：数据域和左、右指针域。 遍历二叉树 森林与二叉树的转换 二、应用举例 赫夫曼编码 Status InOrderThreading(BiThrTree Thrt, BiThrTree T) { if (!(Thrt = (BiThrTree)malloc(sizeof( BiThrNode)))) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; // 添加头结点 建立中序线索化链表的算法6.6 if (!T) Thrt-lchild = Thrt; else { Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; pre-RTag = Thread; Thrt-rchild = pre; } // 处理最后一个结点 return OK; } // InOrderThreading 0 E 1 Thrt void InThreading(BiThrTree p) { if (p) {// 对以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 建立中序线索化链表的算法6.7 Thrt E D G root B A F C 0 E 1 pre Status InOrderThreading(BiThrTree Thrt, BiThrTree T) { if (!(Thrt = (BiThrTree)malloc(sizeof( BiThrNode)))) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; // 添加头结点 建立中序线索化链表的算法6.6 if (!T) Thrt-lchild = Thrt; else { Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; pre-RTag = Thread; Thrt-rchild = pre; } // 处理最后一个结点 return OK; } // InOrderThreading Thrt E D G root B A F C 0 E 1 pre 中序遍历线索二叉树结构示例 ◆若根的左子树不空，侧其最左下角的结点为中序遍历的第一个结点，否则根为中序遍历的第一个结点。 ◆若根的右子树不空，侧其最右下角的结点为中序遍历的最后一个结点，否则根为中序遍历的最后一个结点。 E D G root B A F C NULL NULL 0 E 0 0 B 0 1 F 0 0 D 1 1 G 1 1 C 1 1 A 1 ? root 0 E 1 Thrt 一、双亲表示法 二、孩子链表表示法 三、树的二叉链表(孩子-兄弟） 存储表示法 树和森林 树的三种存储结构 A C B D E F G 一、双亲表示法 ( 顺序存储结构 ) 利用每个非根结点有一个双亲的性质,在每个结点附设指示