64遍历二叉树和线索二叉树 3 (1)结点结构 在二叉链表中增加1tag和rtag两个标志域 Child Itag data rtag rchild 若结点有左子树,则左链域1 child指示其左孩子 (ltag=0);否则,令左链域指示其前驱(1tag=1) 若结点有右子树,则右链域rchi1d指示其右孩子 (rtag=0);否则,令右链域指示其后继(rtag=·1)
6.4 遍历二叉树和线索二叉树 3. 线索二叉树： ⑴ 结点结构 在二叉链表中增加 ltag 和 rtag 两个标志域 lchild ltag data rtag rchild • 若结点有左子树，则左链域lchild指示其左孩子 （ltag=•0）；否则，令左链域指示其前驱（ltag=1）； • 若结点有右子树，则右链域rchild指示其右孩子 （rtag=•0）；否则，令右链域指示其后继（rtag=•1）；
64遍历二叉树和线索二叉树 二叉树的二叉线索链表存储表示 typedef enum LINK, THREAD] PointerTag /*LⅠNK值为0,表示指针; THREAD值为0,表示线索*/ typedef struct BiThrNode i TelemType data struct bithrNode *lchild. rchild PointerTag ltag, rtag; f BiThrNode, *BiThrTree
6.4 遍历二叉树和线索二叉树 二叉树的二叉线索链表存储表示 typedef enum {LINK,THREAD} PointerTag; /* LINK值为0,表示指针;THREAD值为0,表示线索*/ typedef struct BiThrNode { TelemType data; struct BiThrNode *lchild,*rchild; PointerTag ltag,rtag; } BiThrNode,*BiThrTree;
64遍历二叉树和线索二叉树 称这种结点结构为线索链表; 其中指示前驱和后继的链域称为线索; 加上线索的二叉树称为线索二叉树; 对二叉树以某种次房遍历使其变为线索二叉树 的过程称为线索化 按中序遍历得到的线索二叉树称为中序线索二 叉树;按先序遍历得到的线索二叉树称为先序线 索二叉树;按后序遍历得到的线索二叉树称为后 房序线索二叉树;
6.4 遍历二叉树和线索二叉树 • 称这种结点结构为线索链表； • 其中指示前驱和后继的链域称为线索； • 加上线索的二叉树称为线索二叉树； • 对二叉树以某种次序遍历使其变为线索二叉树 的过程称为线索化。 • 按中序遍历得到的线索二叉树称为中序线索二 叉树；按先序遍历得到的线索二叉树称为先序线 索二叉树；按后序遍历得到的线索二叉树称为后 序线索二叉树；
64遍历二叉树和线索二叉树 (2)整体结构 设一个买结点,令其 lchild指向二叉树的根 结点,1tag=0、rtag=1; ·并将该结点作为遍历访问的第一个结点的前驱 和最后一个结点的后继; 最后用头指针指示该头结点 0 01×01。 1a订b
6.4 遍历二叉树和线索二叉树 （2）整体结构 • 增设一个头结点，令其lchild指向二叉树的根 结点，ltag=0、rtag=1； • 并将该结点作为遍历访问的第一个结点的前驱 和最后一个结点的后继； • 最后用头指针指示该头结点。 a c b × － 0 1 0 － 0 0 × 0 1 c 1 1 a 1 1 b 1
64遍历二叉树和线索二叉树 4.遍历线索二又树 有了线索二叉树,就容易遍历二叉树了 只要 (1)先找要遍历的第一个结点 (2)然后依次找结点的后继; (3)重复(2)直到其后继为头结点 所有问题归为如何在线索二叉树中找结 点的后继?
6.4 遍历二叉树和线索二叉树 4. 遍历线索二叉树： 有了线索二叉树，就容易遍历二叉树了． 只要 （１）先找要遍历的第一个结点； （２）然后依次找结点的后继； （３）重复（２）直到其后继为头结点． 所有问题归为如何在线索二叉树中找结 点的后继？