文档详情

数据结构与算法--数和二叉树3.ppt

发布:2018-01-20约6.34千字共35页下载文档
文本预览下载声明
三、线索二叉树 在一个n结点的链式存储二叉树中,有n+1个指针域是空指针域,可以把每个空指针域用于存放分别指向某种遍历次序的前趋和后继结点的指针。 在结点的空指针域中存放的该结点在某遍历次序下的前趋结点和后继结点的指针叫做线索。 三、线索二叉树 把某结点原来空的左(右)指针域用于存放指向其前趋(后继)结点的指针,也叫左(右)线索。 对一个二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫作线索化,被线索化了的二叉树称作线索二叉树。 找前趋结点相应的原则如下: a) 如果某结点的左线索标志域为1,说明其左指针域是线索,这个线索所指的即是该结点的前趋结点; b) 如果某结点的左线索标志为0,则其左指针域是指向左儿子结点的指针,由此结点的左儿子结点起按右指针域指针逐结点向右查找,一直找到右线索标志域为1的结点,即是该结点的前趋结点。 中序线索树求前驱结点 a)先由根结点指针找到根结点,从根结点起沿左指针逐结点一直向左查找,找到左线索标志为1的结点(“最左”的结点)即为遍历中需首先访问的结点。 b)由此结点开始,反复进行寻找后继结点的过程,并陆续访问这些结点,直至结束。 中序遍历线索树 void InThreadBinTreeElemType::InOrder(void (*Visit)(const ElemType )) const // 操作结果:二叉树的中序遍历 { if (root != NULL) { ThreadBinTreeNodeElemType *cur = root; // 从根开始遍历 while (cur-leftTag == CHILD_PTR) cur = cur-leftChild; // 查找最左侧的结点,此结 // 点为中序序列的第一个结点 while (cur != NULL) { (*Visit)(cur-data); if (cur-rightTag == THREAD_PTR) { // 右链为线索 cur = cur-rightChild; } else { cur = cur-rightChild; while (cur-leftTag == CHILD_PTR) cur = cur-leftChild; } } } } 本讲小结 (1)二叉树的遍历的应用 (2)中序线索二叉树 不积跬步无以至千里! 不积小流无以成江海! * P129,char String::operator [](int pos) const; 修改为 char operator [](int pos) const; * c 华中农业大学理学院 章 英 zy@mail.hzau.edu.cn 数据结构与算法 第15讲 线索二叉树 本讲知识点: (1)掌握二叉树的显示和求宽度的算法 (2)掌握二叉树的层次遍历 (3)理解线索二叉树的意义 (4)掌握中序线索二叉树的操作 重点:二叉树的遍历的应用 难点:中序线索二叉树 1、二叉树的显示 template class ElemType void DisplayBTWithTreeShapeHelp(BinTreeNode ElemType *r, int level) { if(r != NULL) { // 空树不显式,只显式非空树 DisplayBTWithTreeShapeHelpElemType(r-rightChild, level + 1);//显示右子树 cout endl; for(int i = 0; i level - 1; i++) cout ; cout r-data; DisplayBTWithTreeShapeHelpElemType(r-leftChild, level + 1);//显示左子树 } } 一、遍历的应用 1 2 3 4 5 level=1 (1)显示1右 (2)换行 (3)空格 (4)根1 (5)显示1左 level=2 (1)显示3右 (2)换行 (3)空格1 (4)根3 (5)显示3左 level=3 (1)显示5右 (2)换行 (3)空格2 (4)根5 (5)显示5左 _ 3 _ _ 5 level=1 (1)显示1右 (2)换行 (3)空格 (4)根1 (5)显示1左 level=2 (1)显示2右 (2)换行 (3)空格1 (4)根2 (5)显示2左 level=3 (1)显示4右 (2)换行 (3)空格2 (4)根4 (5)显示4左 _ 3 _ _ 5 1 _ 2 _ _ 4 1 2 3 4 5 te
显示全部
相似文档