第二十二讲 线索二叉树.pptVIP

第 二十二 讲 知 识 点 在二叉树上建立线索的方法与算法 难 点 各顶点线索的确定 线索化的递归算法中指针的返回 2、中序遍历的非递归算法2（P130 算法6.3) Status InOrder2 (BiTree T, Status (*Visit)(ElemTp)) {stack S; BiTree p; InitStack(S); p = T; while (p || !StackEmpty(S)) {if (p) { Push(S, p); p = p-lchild; } //非空指针进栈,继续左进 else // 上层指针退栈，访问其所指结点，再向右进 { Pop(S, p); if (!Visit(p-data)) return ERROR; p = p-rchild; } } return OK;} 4、创建二叉链表的递归算法（P131 算法6.4) BiTree Create (BiTree T) {// 按先序次序输入结点值，空格字符表示空树， char ch; scanf(%c,ch); if (ch==#) T = NULL; else {if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; T-data = ch; // 生成根结点 CreateBiTree(T-lchild); // 构造左子树 CreateBiTree(T-rchild); // 构造右子树 } return T; } 6．4 线索二叉树（指出每个结点的前驱和后继） 6．4 ．1 二叉树的线索化算法 1、定义结点的类型如下： typedef struct treenode {elemtype data; struct treenode *lchild, *rchild; int ltag, rtag; /*0：表示孩子指针；1：表示前驱或后继*/ } NODE, *PTR; 2、线索化 若结点有左孩子，则ltag=0，lchild指向 左孩子，否则ltag=1，建立前驱线索. 若结点有右孩子，则rtag=0，rchild指向 右孩子，否则rtag=1，建立后线索 （算法 6.6、 P135 ） 3、建立线索二叉树 例：画出下图的中序、前序线索树 4、按中序遍历建立线索树 建头结点，根结点T为其左孩子 对T为根的树线索化 返回的pre指针指向头结点，头结点的rchild指向pre (算法 6.7 134) Status InThreading(BiTree Thrt, BiTree T {//Thrt指向头结点。建头结点 if (!(Thrt=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW); Thrt-LTag = Link; // 右指针回指 Thrt-RTag =Thread; Thrt-rchild = Thrt; if (!T) Thrt-lchild = Thrt; // 若二叉树空，则左指针回指 else {Thrt-lchild = T; pre = Thrt; InThreading(T); // 中序遍历进行中序线索化 pre-rchild = Thrt; pre-RTag = Thread; // 最后一个结点线索化 Thrt-rchild = pre; } return OK; } 5、线索化 void InThreading(BiThrTree p) { if (p) { InThreading(p-lchild); // 左子树线索化 if (!p-lchild) // 建前驱线索 { p-LTag = Thread; p-lchild = pre;