爱站程序员基地实现下面这棵树：
先序遍历: A B C D E F
中序遍历: C B D A E F
代码
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <unistd.h>typedef enum {links, thread} TAG;typedef struct treeNode {char name;struct treeNode *lchild, *rchild;TAG ltag;TAG rtag;}TREENODE, *TREE;void createTree(TREE *);void traverse(TREE);void traverse_middle(TREE);void traverse_middle_detail(TREE);// 线索化二叉树,相比普通的中序遍历，这里把输出节点数据的步骤改为了判断指针域的逻辑void inThread(TREE, TREE *, TREE);void traverse_inThread_by_rchild(TREE);// 调用此函数时需要传入headvoid traverse_inThread_by_rchild(TREE head){printf(\"中序正向遍历二叉链表:\\n\");printf(\"self %p - lc %10p, lt %u, %c, rt %u, rc %10p\\n\", head, head->lchild, head->ltag, head->name, head->rtag, head->rchild);TREE p = head->lchild;while (p->lchild != head) {p = p->lchild;//usleep(100000);}while (p) {printf(\"self %p - lc %10p, lt %u, %c, rt %u, rc %10p\\n\", p, p->lchild, p->ltag, p->name, p->rtag, p->rchild);p = p->rchild;}}void inThread(TREE p, TREE *pre, TREE head){if (! p)return;inThread(p->lchild, pre, head);printf(\"pre p %p - lc %10p, lt %u, %c, rt %u, rc %10p\\n\", (*pre), (*pre)->lchild, (*pre)->ltag, (*pre)->name, (*pre)->rtag, (*pre)->rchild);// 判断自身是否有左孩子，如果没有指向前驱节点if (! p->lchild) {p->ltag = thread;p->lchild = *pre;}/** 因为遍历(中序)时，路径只走到当前节点，并不知道后继是否有，* 所以每个节点都只处理自己的前驱和前驱的后继* head节点rchild在第1个节点处理时指向了第1个节点*/if (! (*pre)->rchild) {(*pre)->rtag = thread;(*pre)->rchild = p;}printf(\" inThread p %p - lc %10p, lt %u, %c, rt %u, rc %10p\\n\", p, p->lchild, p->ltag, p->name, p->rtag, p->rchild);// 本节点处理完后，更新pre指向自身，作为中序遍历下一个节点的前驱*pre = p;// 头指针rchild指向当前节点，最终线索化完成后，头节点的右孩子必定指向中序最后1个节点head->rchild = p;inThread(p->rchild, pre, head);}void traverse_middle(TREE p){if (p) {traverse_middle(p->lchild);printf(\"%c \", p->name);traverse_middle(p->rchild);}}void traverse_middle_detail(TREE p){if (p) {traverse_middle_detail(p->lchild);printf(\"self %p - lc %10p, lt %u, %c, rt %u, rc %10p\\n\", p, p->lchild, p->ltag, p->name, p->rtag, p->rchild);traverse_middle_detail(p->rchild);}}void traverse(TREE p){if (p) {printf(\"%c \", p->name);traverse(p->lchild);traverse(p->rchild);}}// 前序初始化树的各节点void createTree(TREE *p){char c;scanf(\"%c\", &c);if (c == \'_\') {*p = NULL;}else {*p = (TREE)malloc(sizeof(TREENODE));(*p)->name = c;// 无论是否会有左右孩子，都先把tag标识为links(*p)->ltag = (*p)->rtag = links;createTree(&(*p)->lchild);createTree(&(*p)->rchild);}}int main(void){// 头指针，指向线索二叉树的头节点(该节点的lchild指向root)TREE head = NULL;TREE tree;head = (TREE)malloc(sizeof(TREENODE));head->lchild = head->rchild = NULL;head->ltag = head->rtag = thread;// 为了方便确认头节点head->name = \'H\';TREE pre = head;createTree(&tree);// 头节点lchild手动指向tree根节点(rchild已经在线索化完成后指向了中序最后1个节点)head->lchild = tree;printf(\"先序遍历: \");traverse(tree);putchar(\'\\n\');printf(\"中序遍历: \");traverse_middle(tree);putchar(\'\\n\');printf(\"中序遍历(detail):\\n\");traverse_middle_detail(tree);putchar(\'\\n\');// 线索化二叉树(把空闲的lchild, rchild指向各自的前驱和后继)inThread(tree, &pre, head);// 使用rchild遍历中序线索化的二叉链表traverse_inThread_by_rchild(head);/** 目前中序最后1个节点的rchild依然是NULL，但是已经可以实现根据头节点正反向遍历二叉链表* 如果按照其它教程里的需要把中序尾节点rchild的指向头节点，则中序遍历记住最后1个指针操作一下就可以。。。(如果需要判断空树等情况可以参考网上其它教程)*/return 0;}
output
[root@8be225462e66 c]# gcc thrTree.c && ./a.outABC__D__E_F__先序遍历: A B C D E F中序遍历: C B D A E F中序遍历(detail):self 0x1a83740 - lc (nil), lt 0, C, rt 0, rc (nil)self 0x1a83710 - lc 0x1a83740, lt 0, B, rt 0, rc 0x1a83770self 0x1a83770 - lc (nil), lt 0, D, rt 0, rc (nil)self 0x1a836e0 - lc 0x1a83710, lt 0, A, rt 0, rc 0x1a837a0self 0x1a837a0 - lc (nil), lt 0, E, rt 0, rc 0x1a837d0self 0x1a837d0 - lc (nil), lt 0, F, rt 0, rc (nil)pre p 0x1a832a0 - lc 0x1a836e0, lt 1, H, rt 1, rc (nil)inThread p 0x1a83740 - lc 0x1a832a0, lt 1, C, rt 0, rc (nil)pre p 0x1a83740 - lc 0x1a832a0, lt 1, C, rt 0, rc (nil)inThread p 0x1a83710 - lc 0x1a83740, lt 0, B, rt 0, rc 0x1a83770pre p 0x1a83710 - lc 0x1a83740, lt 0, B, rt 0, rc 0x1a83770inThread p 0x1a83770 - lc 0x1a83710, lt 1, D, rt 0, rc (nil)pre p 0x1a83770 - lc 0x1a83710, lt 1, D, rt 0, rc (nil)inThread p 0x1a836e0 - lc 0x1a83710, lt 0, A, rt 0, rc 0x1a837a0pre p 0x1a836e0 - lc 0x1a83710, lt 0, A, rt 0, rc 0x1a837a0inThread p 0x1a837a0 - lc 0x1a836e0, lt 1, E, rt 0, rc 0x1a837d0pre p 0x1a837a0 - lc 0x1a836e0, lt 1, E, rt 0, rc 0x1a837d0inThread p 0x1a837d0 - lc 0x1a837a0, lt 1, F, rt 0, rc (nil)中序正向遍历二叉链表:self 0x1a832a0 - lc 0x1a836e0, lt 1, H, rt 1, rc 0x1a837d0self 0x1a83740 - lc 0x1a832a0, lt 1, C, rt 1, rc 0x1a83710self 0x1a83710 - lc 0x1a83740, lt 0, B, rt 0, rc 0x1a83770self 0x1a83770 - lc 0x1a83710, lt 1, D, rt 1, rc 0x1a836e0self 0x1a836e0 - lc 0x1a83710, lt 0, A, rt 0, rc 0x1a837a0self 0x1a837a0 - lc 0x1a836e0, lt 1, E, rt 0, rc 0x1a837d0self 0x1a837d0 - lc 0x1a837a0, lt 1, F, rt 0, rc (nil)[root@8be225462e66 c]#
