资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
知识回顾遍历二叉树结果是:求得结点的一个线性序列(前驱 后继),前驱或后继在二叉树上体现线性关系?二叉树线性结构(前驱.后继 )遍历过程?线索过程6.3.2 线索二叉树1. 基本概念2. 二叉树线索链表存储结构3. 在线索链表上遍历二叉树(中序为例)4. 建立线索链表总结1. 基本概念线索:指向前驱或后继的指针要求:带箭头的虚线,左右分明!线索链表:含线索的存储结构线索二叉树:用线索链表作为存储结构,相应的二叉树.2. 二叉树线索链表存储结构(利用n+1个空链域)lchildltagdatartagrchild用C语言描述如下:Typedef enum PointerTag Link,Thread;/Link=0; Thread=1Typedef struct BiThrNode TElemType data;struct BiThrNode *lchild,*rchild;PointerTag ltag,rtag; BiThrNode ,*BiThrTreeltag=0时,lchild指向左孩子;ltag=1时, lchild指向前驱rtag=0时,rchild指向右孩子;rtag=1时, rchild指向后继求出下面二叉树的( ? )线索二叉树(链表)ABDGCEFH中序后继二叉树?ABDGCEFH第一. 按中序遍历二叉树,序列是: D G B A E C H F第二. 找出没有右孩子的结点,并标出:第三.在没有右孩子的结点处连上后继NULL3. 在线索链表上遍历二叉树(中序为例) (1) 中序遍历的第一个结点? (2) 在中序线索化链表中结点的后继? (使用栈?)P=T-lchild;While (p!=T) while (p-ltag=Link) p=p- lchild;if (!visit(p-data) return ERROR;while (p-rtag=Thread)visit(p-data); p=p-rchild; Return OK;010 A 01 B 01 D 11 C 1T作业:
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号