据结构二叉树的线索化

1、6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉二叉树树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.6 6.6 哈夫曼树及其应用哈夫曼树及其应用第六章第六章 树和二叉树树和二叉树 何谓线索二叉树？何谓线索二叉树？ 线索链表的遍历算法线索链表的遍历算法 如何建立线索链表？如何建立线索链表？6.3.2 二叉树的线索化二叉树的线索化6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、一、何谓线索二叉树？何谓线索二叉树？遍历二叉树的结果是， 求得结点的一个线性序列。abcdefghk例如:先序先序序列: a b c

2、 d e f g h k中序中序序列: b d c a h g k f e后序后序序列: d c b h k g f e a指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线线索索”与其相应的二叉树，称作 “线索二叉树线索二叉树”包含 “线索” 的存储结构，称作 “线索链线索链表表”a b c d e f g h k d c b e 对对线索链表线索链表中结点的约定：中结点的约定： 在二叉链表的结点中增加两个标志域增加两个标志域，并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则lchild域的指针指向其左子树， 且左标志域的值为“指针 link”； 否则，lchild域的

3、指针指向其“前驱”， 且左标志的值为“线索 thread” 。若该结点的右子树不空，若该结点的右子树不空，则rchild域的指针指向其右子树， 且右标志域的值为 “指针 link”；否则，rchild域的指针指向其“后继”， 且右标志的值为“线索 thread”。 如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”6.3.2 二叉树的线索化二叉树的线索化 当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列（先序、中序或后序序列）中的前驱和后继信息，这种接得到结点在

4、任一序列（先序、中序或后序序列）中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。为了保存这种在遍历过程中得到的信信息只有在遍历的动态过程中才能得到。为了保存这种在遍历过程中得到的信息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放结点的前驱和后继信息。结点的前驱和后继信息。作如下规定：作如下规定： 若结点有左子树，则其若结点有左子树，则其lchild域指示其左孩子，否则令域指示其左孩子，否则令lchild域指示其前驱；域指示其前驱； 若结点有右子树，则其若结点有右子树，则其rchild域指示其右孩

5、子，否则令域指示其右孩子，否则令rchild域指示其后继。域指示其后继。 （1）线索链表的结点结构）线索链表的结点结构lchild ltag data rtag rchild其中：其中：data：数据域；：数据域； lchild：左指针域，指向该结点的左孩子；：左指针域，指向该结点的左孩子； rchild：右指针域，指向该结点的右孩子；：右指针域，指向该结点的右孩子； 0 lchild域指示结点的左孩子域指示结点的左孩子 ltag = 1 lchild域指示结点的前驱域指示结点的前驱 0 rchild域指示结点的右孩子域指示结点的右孩子 rtag = 1 rchild域指示结点的后继域指示结点

6、的后继（2）线索链表的定义）线索链表的定义 线索链表线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之为线索链表。为线索链表。（3）相关术语）相关术语线索化线索化：对二叉树以某种次序遍历使其变为线性二叉树的过程。：对二叉树以某种次序遍历使其变为线性二叉树的过程。线索二叉树（线索二叉树（threaded binary tree）：加上线索的二叉树。：加上线索的二叉树。线索线索：在线索链表中指向结点前驱和后继的指针。：在线索链表中指向结点前驱和后继的指针。（4）图形表示）图形表示-+ /a * e fb -c d-+ /nil

7、nila * e fb -c d(a) ( a + b * (cd)e / f )表达式的二叉树表达式的二叉树(b) 中序线索二叉树中序线索二叉树图图6.11线索二叉树及其存储结构线索二叉树及其存储结构thrt 0 1bt0 0 0 0 0 / 0 1 a 1 0 * 0 1 e 1 1 f 10 01 b 11 c 11 d 1(c) 中序线索链表中序线索链表图中，实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。图中，实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。typedef struct bithrnod telemtype data; struct bithr

8、node *lchild, *rchild; / 左右指针 pointerthr ltag, rtag; / 左右标志 bithrnode, *bithrtree;线索链表的类型描述： typedef enum link, thread pointerthr; / link=0:指针，thread=1:线索二、线索链表的遍历算法二、线索链表的遍历算法: for ( p = firstnode(t); p; p = succ(p) ) visit (p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。例如例如: 对中序线索化链表的遍历算法对中序线索化链表的遍历

9、算法 中序遍历的第一个结点中序遍历的第一个结点 ？ 在中序线索化链表中结点的后继在中序线索化链表中结点的后继 ？左子树上处于“最左下最左下”（没有左子树）的结点若若无右子树，则为则为后继线索后继线索所指结点否则为否则为对其右子树右子树进行中序遍历遍历时访问的第一个结点第一个结点void inordertraverse_thr(bithrtree t, void (*visit)(telemtype e) /t指向结点，头结点的左链lchild指向根结点，可参照线索化算法。/中序遍历二叉线索树t的非递归算法，对每个数据元素调用函数visit p = t-lchild; / p指向根结点 whil

10、e (p != t) / 空树或遍历结束时，p=t while (p-ltag=link) p = p-lchild; / 第一个结点 if (!visit(p-data) return error;/访问其左子树为空的结点 while (p-rtag=thread & p-rchild!=t) p = p-rchild; visit(p-data); / 访问后继结点 p = p-rchild; / p进至其右子树根 / inordertraverse_thr 在中序遍历过程中修改结点的在中序遍历过程中修改结点的左、右指针域，以保存当前访问结左、右指针域，以保存当前访问结点的点的“前

11、驱前驱”和和“后继后继”信息。遍历过信息。遍历过程中，附设指针程中，附设指针pre, 并始终保持指并始终保持指针针pre指向当前访问的、指针指向当前访问的、指针p所指所指结点的前驱。结点的前驱。三、如何建立线索链表？三、如何建立线索链表？void inthreading(bithrtree p) if (p) / 对以p为根的非空二叉树进行线索化 inthreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-ltag = thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-rtag = thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 inthreading(p-rchild); / 右子树线索化 / if / inthreadingstatus inorderthreading(bithrtree &thrt, bithrtree t) / 构建中序线索链表 if (!(thrt = new bithrnode) ) exit (overflow); thrt-ltag = link; thrt-rtag =thread; thrt-rchild = th