线索二叉树（C语言详解）

实现下面这棵树：

先序遍历: 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);

// 调用此函数时需要传入head

void 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.out

ABC__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  0x1a83770

self 0x1a83770 - lc      (nil), lt 0, D, rt 0, rc      (nil)

self 0x1a836e0 - lc  0x1a83710, lt 0, A, rt 0, rc  0x1a837a0

self 0x1a837a0 - lc      (nil), lt 0, E, rt 0, rc  0x1a837d0

self 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  0x1a83770

pre p 0x1a83710 - lc  0x1a83740, lt 0, B, rt 0, rc  0x1a83770

    inThread 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  0x1a837a0

pre p 0x1a836e0 - lc  0x1a83710, lt 0, A, rt 0, rc  0x1a837a0

    inThread p 0x1a837a0 - lc  0x1a836e0, lt 1, E, rt 0, rc  0x1a837d0

pre p 0x1a837a0 - lc  0x1a836e0, lt 1, E, rt 0, rc  0x1a837d0

    inThread p 0x1a837d0 - lc  0x1a837a0, lt 1, F, rt 0, rc      (nil)

中序正向遍历二叉链表:

self 0x1a832a0 - lc  0x1a836e0, lt 1, H, rt 1, rc  0x1a837d0

self 0x1a83740 - lc  0x1a832a0, lt 1, C, rt 1, rc  0x1a83710

self 0x1a83710 - lc  0x1a83740, lt 0, B, rt 0, rc  0x1a83770

self 0x1a83770 - lc  0x1a83710, lt 1, D, rt 1, rc  0x1a836e0

self 0x1a836e0 - lc  0x1a83710, lt 0, A, rt 0, rc  0x1a837a0

self 0x1a837a0 - lc  0x1a836e0, lt 1, E, rt 0, rc  0x1a837d0

self 0x1a837d0 - lc  0x1a837a0, lt 1, F, rt 0, rc      (nil)

[root@8be225462e66 c]#

-----------------------------------