数据结构(C语言版) 第6章 树.ppt

线索二叉树的存储表示 typedef enum PointerTag { Link, Thread }; // Link == 0：指针，Thread == 1：线索 typedef struct BiThrNode {  TElemType data;  struct BiThrNode *lchild, *rchild; // 左右指针  PointerTag LTag, RTag; // 左右标志 } BiThrNode, *BiThrTree; 线索链表的遍历算法（中序找后继法）： Status InOrderTraverse_Thr(BiThrTree T, Visit) { p = T － lchild;  while (p != T)  { while (p － LTag == 0) p = p － lchild; if ( ! Visit(p － data)) return ERROR;  while ( p － RTag == 1 p － rchild != T)  { p = p － rchild; Visit(p － data); }  p = p － rchild; }  return OK;} // InOrderTraverse_Thr － ＋ a × b － c d ／ e f 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 T 按中序建立线索链表（按中序线索化二叉树） 1、若结点没有左子树，则令其左指针指向它的“前驱”并将 左指针类型标志改为 “1”； 2、若结点没有右子树，则令其右指针指向它的“后继”并将 右指针类型标志改为 “1”； 3、为了获取“前驱” 的信息，需要在遍历过 程中添加一个指针 pre， 令其始终指向刚刚访问 过的结点。若指针 p 指 向当前访问的结点，则 pre 指向它的前驱。 － ＋ a × b － c d ／ e f T Status InOrderThreading(BiThrTree Thrt, BiThrTree T) {  if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOW); Thrt－LTag = 0; Thrt－RTag = 1; // 建头结点  Thrt － rchild = Thrt; // 右指针回指  if (!T) Thrt － lchild = Thrt; // 若二叉树空，则左指针回指 else { Thrt － lchild = T; pre = Thrt;  InThreading(T); // 中序遍历进行中序线索化  pre－ rchild = Thrt; pre－ RTag = 1; // 最后一个结点线索化  Thrt － rchild = pre; } return OK;} // InOrderThreading void InThreading(BiThrTree p) { if (p) { InThreading(p－ lchild); // 左子树线索化  if (!p－ lchild) { p－ LTag = 1; p－ lchild = pre; }  if (!pre－ rchild) { pre－ RTag = 1; pre－ rchild = p; } pre = p; // 保持 pre 指向 p 的前驱 InThreading(p－ rchild); } // 右子树线索化 }} // InThreading － ＋ a × b － c d ／ e f 1 1 1 1 1