《线索二叉树+习题(2学时)》由会员分享，可在线阅读，更多相关《线索二叉树+习题(2学时)（7页珍藏版）》请在金锄头文库上搜索。
1、知识回顾遍历二叉树结果是:求得结点的一个线性序列(前驱 后继),前驱或后继在二叉树上体现线性关系?二叉树线性结构(前驱.后继 )遍历过程?线索过程6.3.2 线索二叉树1. 基本概念2. 二叉树线索链表存储结构3. 在线索链表上遍历二叉树(中序为例)4. 建立线索链表总结1. 基本概念线索:指向前驱或后继的指针要求:带箭头的虚线,左右分明!线索链表:含线索的存储结构线索二叉树:用线索链表作为存储结构,相应的二叉树.2. 二叉树线索链表存储结构(利用n+1个空链域)lchildltagdatartagrchild用C语言描述如下:Typedef enum PointerTag Link,Thre
2、ad;/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作业:
