数据结构PPT(第6章 树和二叉树).ppt

(以中序遍历为例) 查找任意结点的前驱结点 如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。 中序线索二叉树 中序：DBGJEACHLKFI 四、 如何找结点的前驱和后继 B A C E F D G J H I K L 中序线索二叉树 中序：DBGJEACHLKFI 四、如何找结点的前驱和后继 (续) (以中序遍历为例) 查找任意结点的后继结点 对任意结点p，若右标志为1 ，则rchild指向该结点的后继；若右标志为0 ，则rchild指向该结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点s(Ltag=1)，则s就是p的后继，即后继是中序遍历右子树时，访问的第一个结点。 B A C E F D G J H I K L 按不同的方式遍历二叉树所得到的线索二叉树是不相同的。 B A D C E 五、遍历线索二叉树 A B D C E T 先序序列：ABCDE 先序线索二叉树 0 0 0 0 1 1 1 1 ^ 1 1 A B D C E T 中序序列：BCAED 中序线索二叉树 0 0 0 0 1 1 1 1 ^ 1 1 ^ A B D C E T 后序序列：CBEDA 后序线索二叉树 0 0 0 0 1 1 1 1 1 1 ^ B A D C E A B D C E T 0 0 0 0 1 1 1 1 1 1 0 1 中序序列：BCAED 中序线索二叉树 五、遍历线索二叉树 (续) 带头结点的线索二叉树 在存储线索二叉树时往往增设一头结点，其数据域不存放信息，其左指针域指向二叉树的根结点，右指针域指向某种遍历时访问的最后一个结点。而原二叉树在某序遍历下的第一个结点的前驱线索和最后一个结点的后继线索都指向该头结点。 注：可从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。 找遍历的第一个结点 左子树上处于“最左下”(没有左子树)的结点。 不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束 若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。 遍历线索二叉树步骤(以中序遍历为例) void InOrderTraverse_Thr(BiThrTree T) { p = T-lchild; while (p != T) { while (p-LTag==0) p = p-lchild; Visit(p-data)); while (p-RTag==1 p-rchild!=T) { p = p-rchild; Visit(p-data); } p = p-rchild; } } // InOrderTraverse_Thr 中序线索二叉树 中序：DBGJEACHLKFI 中序遍历线索二叉树算法实现 T B A C E F D G J H I K L 建立线索二叉树，或者说对二叉树线索化，实质上是遍历一棵二叉树。在遍历过程中访问结点操作visit()是检查当前结点的左、右指针域是否为空，如果为空，将空的lchild改为结点的直接前驱，将空的rchild改为结点的直接后继。而对于非空指针，仍然指向孩子结点。 为了记下遍历过程中访问结点的先后关系，附设指针pre始终指向刚刚被访问过的结点, 若p指针指向当前访问的结点，则pre指向它的前驱。 六、如何建立线索二叉树？ Status InOrderThreading(BiThrTree Thrt, BiThrTree T) { if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode) ) exit (OVERFLOW); Thrt-LTag = 0; Thrt-RTag =1; Thrt-rchild = Thrt;