1 /* 2  * 枚举类型定义     NO -> 没有线索化    YES -> 线索化了的 3  */ 4 enum Thread { NO, YES } 5  6 /* 7  * 线索二叉树的结点类型定义 8  */ 9 struct Node10 {11     ElementType data;                   // 数据域12     Thread leftTag;                     // 左指针标志域13     Thread rightTag;                    // 右指针标志域14     struct Node *leftChild;             // 左指针域15     struct Node *rightChild;            // 右指针域16 };

 1 /* 2  * 为二叉树加前序线索   递归实现 3  */ 4 void PreorderThread(Node *root) 5 { 6     static Node *prev = NULL;                               /* 指向当前结点的后序前件，用以记忆刚访问过的结点 */ 7     if(root != NULL) {                                      // 若二叉树为空，结束递归 8         if(prev != NULL && prev->rightTag = YES)            // 若当前结点的前序前件需要加线索 9             prev->rightChild = root;                        // 对当前结点的前序前件加指向后件(当前结点)的线索10         if(root->leftChild == NULL) {                       // 若当前结点的左指针为空11             root->leftTag = YES;                            // 将其修改为指向前件的线索12             root->leftChild = prev; 13         }   14         if(root->rightChild == NULL)                        // 若当前结点的右指针域为空，修改右指针标志15             root->rightTag = YES;   16         prev = root;                                        // 将当前结点置为前件，后件将成为当前结点17     18         PreorderThread(root->leftChild);                    // 递归对左子树加前序线索19         PreorderThread(root->rightChild);                   // 递归对右子树加前序线索20     }21 }22 23 /*24  * 为二叉树加中序线索   递归实现25  */26 void InorderThread(Node *root)27 {28     static Node *prev = NULL;                               /* 指向当前结点的后序前件，用以记忆刚访问过的结点 */29     if(root != NULL) {                                      // 若二叉树为空，结束递归30         InorderThread(root->leftChild);                     /* 递归对左子树加中序线索 */31     32         if(prev != NULL && root->rightTag == YES)           // 若当前结点的中序前件需要加线索33             prev->rightChild = root;                        // 对当前结点的中序前件加指向后件(当前结点)的线索34         if(root->leftChild == NULL) {                       // 若当前结点的左指针为空35             root->leftTag = YES;                            // 将其修改为指向前件的线索36             root->leftChild = prev;     37         }38         if(root->rightChild == NULL)                        // 若当前结点的右指针域为空，修改右指针标志39             root->rightTag = YES;40         prev = root;                                        // 将当前结点置为前件，后件将成为当前结点41 42         InorderThread(root->rightChild);                    /* 递归对右子树加中序线索 */43     }44 }45 46 /*47  * 为二叉树加后序线索   递归实现 */48 void PostorderThread(Node *root)49 {    50     static Node *prev = NULL;                               /* 指向当前结点的后序前件，用以记忆刚访问过的结点 */51     if(root != NULL) {                                      // 若二叉树为空，结束递归52         PostorderThread(root->leftChild);                   // 递归对左子树后序线索化53         PostorderThread(root->rightChild);                  // 递归对右子树后序线索化54 55         if(prev != NULL && root->rightTag == YES)           // 若当前结点的后序前件需要加线索56             prev->rightChild = root;                        // 对当前结点的后序前件加指向后件(当前结点)的线索57         if(rot->leftChild == NULL) {                        // 若当前结点的左指针为空58             root->leftTag = YES;                            // 将其修改为指向前件的线索59             root->rightChild = prev;60         }61         if(root->rightChild == NULL)                        // 若当前结点的右指针域为空，修改右指针标志62             root->rightTag = YES;63         prev = root;                                        // 将当前结点置为前件，后件将成为当前结点64     }65 }

 1 /* 2  * 利用   前序线索树   遍历二叉树 3  */ 4 void preorderThreadTreeTraversal(Node *root) 5 { 6     Node *currentNode = root; 7     if(currentNode != NULL) { 8         while(currentNode != NULL) { 9             cout << currentNode->data;10             if(currentNode->leftTag == NO)                      // 当前结点有左孩子，则使其左孩子变为当前结点11                 currentNode = currentNode->leftChild;12             else                                                // 若当前结点没有左孩子，则currentNode指向当前结点的前序后件13                 currentNode = currentNode->rightChild;14         }15     }16 }17 18 /*19  * 利用   中序线索树   遍历二叉树20  */21 void inorderThreadTreeTraversal(Node *root)22 {23     Node *currentNode = root;                                   // 设定currentNode初始指向中序线索二叉树的根结点24     if(currentNode != NULL) {                                   // 二叉树为空，结束遍历25         while(currentNode->leftTag == NO)                       // 找到中序遍历的第一个结点26             currentNode = currentNode->leftChild;27         do {                                                    /* 依次找出每个结点的后件，直到输出中序线索二叉树的最右边一个结点 */28             cout << currentNode->data;                           /* 输出当前结点数据 */29             if(currentNode->rightTag == YES)                    // 若当前结点的右指针是线索，其指示为中序后件30                 currentNode = currentNode->rightNode;31             else {                                              /* 若当前结点的右指针指向右孩子 */32                 currentNode = currentNode->rightChild;          // 从右孩子结点出发找中序后件33                 while(currentNode->leftTag == NO)               // 找到右子树的最左边一个结点，即为中序后件34                     currentNode = currentNode->leftChild;35             }36         } while(currentNode != NULL); 37     }38 }39 40 /*41  * 利用   后序线索树   遍历二叉树42  */43 void postorderThreadTreeTraversal( Node *root)44 {45     46 }