树和二叉树教学幻灯片讲义.ppt

void InOrderTraverse_Thr(BiThrTree T) { p = T-lchild; // p指向根结点 while (p != T) { // 空树或遍历结束时，p==T while (p-LTag==Link) p = p-lchild; //找第一个被访问的结点P printf(p-data); //访问P while (p-RTag==Thread p-rchild!=T) { p = p-rchild; printf (p-data); // 访问后继结点 } p = p-rchild; // p被赋为其右子树根 } } // InOrderTraverse_Thr 线索化的过程，实质上是在中序遍历过程中修改结点的左、右指针域的过程。为保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre, 始终使指针pre指向刚刚访问过的结点、指针p指当前正在访问的结点（即pre是p在遍历过程中的前驱）。 (5) 如何建立线索链表？ Status InOrderThreading(BiThrTree Thrt, BiThrTree T) { // 构建中序线索链表 if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOW); // 添加头结点 Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; if( ! T) Thrt-lchild = Thrt;//若二叉树为空，则左指针回指 else{ Thrt-lchild = T; pre = Thrt; // Thrt的左链指向树根 InThreading(T); //中序遍历进行中序线索化 △: pre-rchild = Thrt; // 处理最后一个结点 pre-RTag = Thread; Thrt-rchild = pre; } return OK; } // InOrderThreading void InThreading(BiThrTree p) { if (p) { // 对以p为根的非空二叉树进行线索化 InThreading(p-lchild); //线索化左子树 △1: if (!p-lchild) // 建前驱线索 { p-LTag = Thread; p-lchild = pre; } if (!pre-rchild) // 建后继线索 { pre-RTag = Thread; pre-rchild = p; } pre = p;// 保持 pre 指向 p 的前驱（p变成刚刚访问过的结点） InThreading(p-rchild); // 右子树线索化 △2: } // if } // InThreading (5) 对先序线索链表的遍历算法 6.4.1 树的存储结构 1、双亲表示法 2、孩子链表表示法 3、树的二叉链表(孩子-兄弟)存储表示法 6.4 树和森林 A B C D E F G r=0 n=7 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 data parent 1、双亲表示法(顺序存储） typedef struct PTNode {//结点结构: TElemType data; int parent; // 双亲位置域 } PTNode; #define MAX_TREE_SIZE 100 data parent 结点结构: //------------树的双亲表存储表示-------------- typedef struct { //树结构 PTNode nodes[MAX_TREE_SIZE]; int r, n; // 根结点的位置和结点个数