数据结构第五章-21.ppt

5.5 线 索 树;2.线索的方法存储结构 ;中序遍历: H的前驱是D， G的前驱是B; X的前驱是A;思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？ ——我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。;线索二叉树的实现;图5.5.5 中序线索树;图5.5.6 二叉树;有关线索二叉树的几个术语：;例：【考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 ;二叉线索树的结点结构定义 ;二叉线索树的遍历 ;前序二叉线索树的遍历 ;中序二叉线索树的遍历InOrderThread ;BinaryTreeNode *p=BT; bool flag; while ( !p ){ while (!p -Lflag) //查找一棵子树的最左子孙 p = p - LChild; flag=true; while (flag !p ) { cout p -data ; //访问结点 p = p - RChild; //查找p的右子树的根或后继结点 if (!p - Rflag) //p结点存在右子树时，为强制退出作准备 flag = p - Rflag; }};二叉树转化为二叉线索树;3。中序二叉树线索树中结点的插入 ;中序线索树中插入的新结点T作为S的左孩子 ;S结点的最右子孙→;图5.5.12 中序线索二叉树中T结点作为S的右孩子插入;5.6 一般树的表示和遍历 ;树和森林与二叉树的转换;方法：加线—抹线—旋转 ;二叉树怎样还原为树？;A;A;5.6.3 一般树的遍历概念 ;树若采用“先转换，后遍历”方式，结果是否一样？;5.6.4 一般树的运算 ;2。一般树二叉树形式存储下层次遍历 ;树的应用一（族谱）;;树的应用二：利用树型结构的有哪些信誉好的足球投注网站算法模拟因特网域名的查询 ;5.7.1 分类二叉树 ;定义：;数据集合的关键字：｛15，23，12，8，13，9，25，21，18｝ ;15;2 分类二叉树运算1）分类二叉树中数据元素的查找 ;2。将结点插入到分类二叉树中 ;while (p) { parent = p; if (x.key p-data.key) p = p-LChild; else if (x.key p-data.key) p = p-RChild; else return false;//重复出现，即相等值结点出现 } ;// 找到插入点，为x申请一个空间填入其值，并将该结点连接至 parent;删除分类二叉树中的结点;;;;堆排序;1 堆树的定义 ;图5.7.5 最大树或最小树 ;2 堆树的意义 ;堆排序--数据排序的一种经典方法 ;52;1.初始化一个非空的最大堆 ;1 ;构造初始堆 ;构造N所指结点为根的堆算法思想：;for (int i = HeapSize/2; i = 1; i--) //从最后一个结点的根开始，直到第一个结点 1)i= HeapSize/2=10/2=5，heap[5]=72 2)i- -;i=5 ; heap[4]=53 …..;最大堆调整(1);最大堆调整(2);初始化一个非空的最大堆算法 ;while (son = HeapSize) {// 找左右孩子中较大结点 if (son HeapSize heap[son] heap[son +1]) son ++; // son HeapSize时，存在右孩子，如左孩子小于右孩子，son指向右孩子 if (heap[0] = heap[son]) // 大孩子再与工作空间中结点值再比较 break; //工作空间中值大，找到heap[0]的目标位置 heap[son /2] = heap[son]; // 将大孩子上移至双亲位置 son * = 2;// son下移一层到上移的结点（大孩子）位置 } heap[son /2] = heap[0]; //heap[0]存放到目标位置;4.堆排序 ;49;25;25*;21;16;利用分类二叉树查找及堆排序实现学生成绩管理 ;堆排序算法;Status MaxHeapDelete (EType a[], EType x) {// 插入x到最大堆中 Heap = a; if (HeapSize == 0) return ERROR; // 堆空 x = heap[1]; // 最大结点存放到x heap[0] = heap[HeapSize--]; // 最后一个结点存放 到heap[0]，调整堆中元素的个数