85.7.1线索化的概念 【例55】中序线索化树 5 图中序线索树 中序:2541637
11 §5.7.1线索化的概念 • 【例5.5】中序线索化树。 1 2 3 4 5 6 7 图 - 中序线索树 中序：2 5 4 1 6 3 7
85.7.1线索化的概念 ·标志信息 图-中序线索树 00:左右链均为树结构信息; 中序:2541637 01:左为树结构信息,右为线索; 10:左为线索,右为树结构信息; 左右均为线索 12
12 §5.7.1线索化的概念 1 2 3 4 5 6 7 图 - 中序线索树 中序：2 5 4 1 6 3 7 • 标志信息 – 00：左右链均为树结构信息； – 01：左为树结构信息，右为线索； – 10：左为线索，右为树结构信息； – 11：左右均为线索；
§5.7.1线索化的概念 改写二叉树二指针存贮结构的描述, 增加关于线索的标志: struct TBin TreeNode Thread 图-中序线索树 中序:2541637 TElem info, struct tBin TreeNode *Ic * rc unsigned char thread Tag 13
13 §5.7.1线索化的概念 1 2 3 4 5 6 7 图 - 中序线索树 中序：2 5 4 1 6 3 7 改写二叉树二指针存贮结构的描述， 增加关于线索的标志： struct TBinTreeNodeThread { TElem info; struct TBinTreeNode *lc, *rc; unsigned char threadTag; … … };
85.7.1线索化的概念 该类/结构应是前面介绍的 TBintreenode的派生类: struct TBin TreeNode Thread: public tBin TreeNode insigned char thread iag, 图中序线索树 中序:2541637
14 §5.7.1线索化的概念 1 2 3 4 5 6 7 图 - 中序线索树 中序：2 5 4 1 6 3 7 该类/结构应是前面介绍的TBinTreeNode的派生类： struct TBinTreeNodeThread ： public TBinTreeNode { unsigned char threadTag; … … };
§572线索化算法 线索化过程实质上是一种特殊的遍历过程 在线索化中,“访问”结点就是要检查结点的 左右链是否为空,若空,则令其指向(遍历意 义下的)前趋或后继。 图中序线索树 中序:2541637 15
15 §5.7.2 线索化算法 1 2 3 4 5 6 7 图 - 中序线索树 中序：2 5 4 1 6 3 7 • 线索化过程实质上是一种特殊的遍历过程。 • 在线索化中，“访问”结点就是要检查结点的 左右链是否为空，若空，则令其指向（遍历意 义下的）前趋或后继