第6章 树形结构 (31).ppt

1、称采用这种结构存储的叫线索链表，二叉树的第三种存储方式。 其中指示前驱和后继的链域称为线索（也就是lchild 、 rchild 如果指向的不是左右孩子而是前驱和后继那么就称为线索）图中指向的是线索用虚线来画，否则用实线。 加上线索的二叉树称为线索二叉树 对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化 中序线索二叉树 先序线索二叉树 后序线索二叉树,整体结构：增设一个头结点，使其lchild指向二叉树的根结点，并将该结点作为遍历访问的第一个结点的前驱和最后一个访问结点的后继。,最后用头指针指向头结点，通过这个头指针找到该棵线索二叉树,0,0,0,0,1,1,1,1,1,1,0,1,6

2、.6.2 线索化二叉树 为了实现线索化二叉树,将前面二叉树结点的类型定义修改如下： typedef struct node ElemType data;/*结点数据域*/ int ltag,rtag; /*增加的线索标记*/ struct node *lchild;/*左孩子或线索指针*/ struct node *rchild;/*右孩子或线索指针*/ TBTNode;/*线索树结点类型定义*/,6.6.2 线索化二叉树 算法设计 typedef struct node ElemType data; int ltag,rtag; /增加的线索标记 struct node *lchild; s

3、truct node *rchild; TBTNode; TBTNode * CreateTBTNode(char *str) /建立二叉树（二叉链表的方式） TBTNode * CreaThread(TBTNode *b) /线索化二叉树,算法设计,TBTNode *CreaThread(TBTNode *b) /线索化二叉树,增加一个头结点，将整棵树作为他的左孩子,选择一种遍历方式，将二叉树线索化，生成某种访问顺序的线索化二叉树。,TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树*/ TBTNode *root; root=(TBTNode *)mall

4、oc(sizeof(TBTNode); /*创建头结点*/ root-ltag=0;root-rtag=1; root-lchild=b; pre=root; Thread(b); pre-rchild=root; pre-rtag=1; root-rchild=pre; return root; ,pre,1,Thread(p)算法思路是： *p 指向当前访问的结点 *pre指向前一访问的结点 采用中序遍历的方式 Thread (b-lchild); printf(%c ,b-data); Thread (b-rchild);,当前访问结点没有左孩子，就设置为线索，指向前驱 如果访问过的结点

5、没有右孩子，则设置为线索，指向后继,TBTNode *pre; /*全局变量*/ void Thread(TBTNode * /*递归调用右子树线索化*/ ,中序遍历(递归),6.6.3 遍历线索化二叉树 要遍历的第一个结点 依次找结点的后继 直到回到头结点,所有的问题归结为如何找后继结点？,D结点的后继：rtag=1,rchild指向后继,1,B结点的后继：rtag=0,rchild指向右孩子，从右孩子开始从左指针的方向找到第一个没有左孩子的结点S,if(p-rtag=1)p=p-rchild; else p=p-rchild; while(p-ltag=0) p=p-lchild; ,6.6.3 遍历线索化二叉树 从根结点开始找遍历的第一个结点,1,tb,P=tb-lchild,p,while(p-lchild!=tb) p=p-lchild;,6.6.3 遍历线索化二叉树 1、 要遍历的第一个结点 2、 依次找结点的后继 3、直到回到头结点,if(p-rtag=1)p=p-rchild; else p=p-rchild; while(p-ltag=0) p=p-lchild; ,void ThInOrder(TBTNode *tb) TBTNode *p=tb-lchild;/指向根结点 while(p-lchild!=tb) p=p-lchild; while (p!=