7.6线索二叉树7.6.1线索二叉树的定义对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。线索二叉树分为先序、中序和后序线索二叉树。对二叉树以某种方式遍历使其变为线索二叉树的过程称为线索化。138
对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。 利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点 的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。 线索二叉树分为先序、中序和后序线索二叉树。 对二叉树以某种方式遍历使其变为线索二叉树的过程称为线索化。 1/38
图中虚线为线索。先序线索二叉树F二叉树先序序列：ABDCEF2/38
图中虚线为线索。 A B D C E F 二叉树 A B D C E F 先序序列：ABDCEF 先序线索二叉树 2/38
在原二叉链中增加了ltag和rtag两个标志域。表示1child指向结点的左孩子1tag=表示lchild指向结点的前驱结点即为线索表示rchild指向结点的左孩子rtag=表示rchild指向结点的后继结点即为线索ltaglchildrchilddatartag3/38
在原二叉链中增加了ltag和rtag两个标志域。 ltag= 0 表示lchild指向结点的左孩子 1 表示lchild指向结点的前驱结点即为线索 rtag= 0 表示rchild指向结点的左孩子 1 表示rchild指向结点的后继结点即为线索 ltag lchild data rchild rtag 3/38
以中序线索二叉树为例root头结点4/38
A B C D E F G 以中序线索二叉树为例 4/38 1 A 1 1 B 1 1 C 1 1 D 1 1 G 1 1 E 1 1 F 1 0 1 root 头结点
7.6.2线索化二叉树//线索二叉树结点类型class ThNode//存放结点值char data;//左、右孩子或线索的指针ThNode lchild,rchild;/1左、右标志int itag,rtag;1/默认构造方法public ThNode()lchild=rchild=null;ltag=rtag=0;//重载构造方法public ThNode(char d)data=d;lchild=rchild=null;ltag=rtag=0;5/38
class ThNode //线索二叉树结点类型 { char data; //存放结点值 ThNode lchild,rchild; //左、右孩子或线索的指针 int ltag,rtag; //左、右标志 public ThNode() //默认构造方法 { lchild=rchild=null; ltag=rtag=0; } public ThNode(char d) //重载构造方法 { data=d; lchild=rchild=null; ltag=rtag=0; } } 5/38