数据结构课件树和叉树.pptVIP

(1) 算法思想 * 6.4.4 二叉线索树的操作 1. 在二叉线索树中求结点的中序前驱 0 1 0 A 1 0 B 0 1 C 1 1 D 0 1 E 1 bt Thrt p t = p-lchild p p = Thrt 出错 p p p p = Thrt 出错 q = p-lchild q = q-rchild q = q-rchild q * BiThrTree InPre( BiThrTree p ) { // p 指向中序线索树中某一结点，pre 返回此结点的前驱； if(p-Ltag==1) pre=p-Lchild; else {　　//在p的右子树中查找“最右下端”结点 q=p-Lchild; while(p-rtag==0) q=q-Rchild; // 顺着 t 的左孩子的右链域寻找，直到结点右标志是 1 为止 pre=q; return (pre); } // InPre (2) 算法实现 * (3) 算法分析 * 如果 t 所指向结点的左孩子有 k 层右孩子，则需要进行 k+1 次比较，因此 Inpre 算法的时间复杂度为 O(k)。 下面给出将值为 e 的新结点 r 插入到中序线索树中，作为结点 p 的右孩子。 (1) 算法思想 * 建立新结点 r，使其数据域的值为 e； 2. 在二叉线索树中插入结点 Thrt 0 1 0 A 1 1 B 0 0 C 0 1 E 1 1 F 1 * p r e e e 1 1 1 1 1 1 0 0 0 如果结点 p 无右孩子， if(p-rtag==1) //p无右孩子 r-rchild = p-rchild; r-rtag = p-rtag; r-lchild = p; r-ltag = 1; p-rchild = r; p-rtag = 0; r = ( BiThrTree ) malloc ( sizeof ( BiThrNode ) ) r-data = e; 0 0 0 Thrt 0 1 0 A 1 1 B 0 0 C 0 1 E 1 1 F 1 * p r e 1 s e e 1 1 r-rchild = p-rchild r-rtag = p-rtag r-lchild = p r-ltag = 1 p-rchild = r p-rtag = 0 判断 r-rtag 是否为 0 寻找 r 的后继 s-lchild = r 如果 p 有右孩子， int InsNode(BiThrTree Thrt, BiThrTree p, BiThrTree r) { // 将新结点r插入到中序线索树中作为结点 p的右孩子，并返回 OK if ( ! ( r = ( BiThrTree ) malloc ( sizeof ( BiThrNode ) ) ) ) exit ( OVERFLOW ); r-data = e; r-rchild = p-rchild; r-rtag = p-rtag; r-lchild = p; r-ltag = 1; p-rchild = r; p-rtag = 0; if ( r-rtag = 0 ) { InNext ( r, s ); s-lchild = r; } // 若 r 的右标志为 0，则寻找 r 的后继 s，并将 r 作为 s 的前驱 return OK } //InsNode (2) 算法实现 * (3) 算法分析 * InsNode 算法的执行时间主要取决于 InNext (r, s) 算法（求结点 r 的后继 s）。如果 r 的右孩子有 k 层左孩子，则寻找 r 的后继 s 需要进行 k+1 次比较，因此 Next_Thr 算法时间复杂度为 O(k)。故 InNext 算法的时间复杂度也为 O(k)。 同理，可以编写出将值为 e 的新结点 r 插入到中序线索树中，作为结点 p 的左孩子。 (1) 算法思想 令 p 指向根结点，且当二叉树为非空树或遍历未结束时，继续做如下操作； * 首先在中序线索树上求中序遍历的第一个结点 ⑴顺着 p 的左链域寻找，直