C语言中序线索二叉树的建立及遍历

有n个节点的二叉树共有2*n个指针域，但是实际用到的只有n-1（总分支数=总指针域数）个，故剩余n+1个指针域被浪费。现将空闲指针域利用，使其指向节点前驱或后继，并做如下规定：

1、若节点有左（右）孩子，则左（右）指针指向其左右孩子；否则左指针指向前驱，右指针指向后继
2、为标明其左右指针是指向左（右）孩子还是前驱（后继），设标志域LTag（RTag）
LTag = { 0 : lchild 域指示结点的左孩子； 1 : lchild 域指示结点的前驱 }
RTag = { 0 : rchild 域指示结点的右孩子； 1 : rchild 域指示结点的后继 }

1.中序线索二叉树

1.1 示意图

dot tree.dot -Tpng -o tree.png

digraph G {
    // edge [arrowhead=vee]
    node [shape=plaintext]
        comment [label="this is head node"]
	node [shape=record,height=.3];
		node0 [style="invis", label = "<f0> |<f1> |<f2> |<f3> |<f4> "];
		nodeh [label = "<f0> |<f1> 0|<f2> |<f3> 1|<f4> "];
		nodeA [label = "<f0> |<f1> 0|<f2> A|<f3> 0|<f4> "];
		nodeB [label = "<f0> |<f1> 0|<f2> B|<f3> 0|<f4> "];
		nodeC [label = "<f0> |<f1> 0|<f2> C|<f3> 0|<f4> "];
		nodeD [label = "<f0> |<f1> 0|<f2> D|<f3> 0|<f4> "];
		nodeE [label = "<f0> |<f1> 0|<f2> E|<f3> 1|<f4> "];
		nodeF [label = "<f0> |<f1> 1|<f2> F|<f3> 1|<f4> "];
		nodeG [label = "<f0> |<f1> 1|<f2> G|<f3> 1|<f4> "];
		nodeH [label = "<f0> |<f1> 1|<f2> H|<f3> 1|<f4> "];
		nodeI [label = "<f0> |<f1> 1|<f2> I|<f3> 1|<f4> "];
		nodeJ [label = "<f0> |<f1> 1|<f2> J|<f3> 1|<f4> "];
		nodeh -> comment [arrowhead=curve]
		node0:f2 -> nodeh:f2 [label="head pointer"]
		nodeh:f0 -> nodeA:f2 [arrowhead=vee, style="bold,dotted", color=blue, label="1"]
		nodeA:f0 -> nodeB:f2
		nodeA:f4 -> nodeC:f2
		nodeB:f0 -> nodeD:f2
		nodeB:f4 -> nodeE:f2
		nodeC:f0 -> nodeF:f2
		nodeC:f4 -> nodeG:f2
		nodeD:f0 -> nodeH:f2
		nodeD:f4 -> nodeI:f2
		nodeE:f0 -> nodeJ:f2
		nodeH:f0 -> nodeh:f0 [arrowhead=vee, style="bold,dotted", color=red, label="3"]
		nodeG:f4 -> nodeh:f4 [arrowhead=vee, style="bold,dotted", color=red, label="4"]
		nodeh:f4 -> nodeG:f2 [arrowhead=vee, style="bold,dotted", color=blue, label="2"]
}

1.2 关于头节点、中序首节点、中序尾节点的几点声明

设中序遍历第一个节点、最后一个节点分别为first、last；头节点为ThrHead
1、头节点非根节点
2、ThrHead->lchild：指向根节点
3、ThrHead->rchild：指向last
4、first->lchild：指向ThrHead
5、last->rchild：指向ThrHead

以上图为例，示例代码如下所示

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>

typedef char elemType;
typedef struct BiTNode {
    elemType data;
    struct BiTNode *lchild, *rchild;
    int LTag, RTag;
} BiThreadNode, *BiThreadTree;

void visit(elemType x);                        // 输出元素x
BiThreadTree createBiThreadTree();             // 先序输入节点的值，构造二叉树
BiThreadNode* CreateInThrTree(BiThreadTree T); // 创建中序线索二叉树
void InThreading(BiThreadTree T);              // 中序遍历线索化
void ThrInOrderTraverse(BiThreadTree T);       // 遍历中序线索二叉树

BiThreadNode* pre; // 当前访问节点的前驱

int main(void)
{
    BiThreadTree root;

    printf("请按先序顺序输入节点值，输入‘#’代表节点为空：\n");
    root = createBiThreadTree();
    BiThreadNode* ThrHead = CreateInThrTree(root);
    ThrInOrderTraverse(ThrHead);

    return 0;
}

void visit(elemType x) { printf("%c, ", x); }
BiThreadTree createBiThreadTree()
{
    BiThreadNode* T;
    char ch;

    if ((ch = getchar()) == '#') {
        T = NULL;
    } else {
        T = (BiThreadNode*)malloc(sizeof(BiThreadNode));
        T->data = ch;
        T->lchild = createBiThreadTree();
        T->rchild = createBiThreadTree();
    }

    return T;
}
void InThreading(BiThreadTree T)
{
    if (T != NULL) {
        InThreading(T->lchild); // 线索化左子树

        // 左孩子为空，则lchild指向前驱pre
        if (T->lchild == NULL) {
            T->LTag = 1;
            T->lchild = pre;
        } else {
            T->LTag = 0;
        }

        // 前驱pre右孩子为空，则当前节点为前驱pre的后继
        if (pre->rchild == NULL) {
            pre->RTag = 1;
            pre->rchild = T;
        } else {
            pre->RTag = 0;
        }

        pre = T;
        InThreading(T->rchild); // 线索化右子树
    }
}
BiThreadNode* CreateInThrTree(BiThreadTree T)
{
    BiThreadNode* ThrHead; // 中序线索二叉树头节点（非根节点）
    /*
     * 设中序遍历第一个节点、最后一个节点分别为first、last
     * 则：first->lchild指向ThrHead
     *     last->rchild指向ThrHead
     *     ThrHead->lchild：指向根节点
     *     ThrHead->rchild：指向last
     */

    ThrHead = (BiThreadNode*)malloc(sizeof(BiThreadNode));
    ThrHead->RTag = 1;
    ThrHead->rchild = ThrHead; // 先将ThrHead->rchild指向自身
    ThrHead->LTag = 0;

    if (T == NULL) {
        ThrHead->lchild = ThrHead; // 若根节点为空，则ThrHead->lchild指向自身
    } else {
        ThrHead->lchild = T;
        pre = ThrHead;         // 将ThrHead赋给pre，pre为中序线索树中first节点前驱
        InThreading(T);        // 二叉树线索化完毕，pre指向last节点
        pre->rchild = ThrHead; // 将ThrHead作为last节点后继
        pre->RTag = 1;
        ThrHead->rchild = pre; // 将ThrHead->rchild指向pre(last)
    }

    return ThrHead;
}
void ThrInOrderTraverse(BiThreadTree ThrHead)
{
    BiThreadNode* temp = ThrHead->lchild; // 让temp指向根节点

    while (temp != ThrHead) {
        while (temp->LTag == 0) {
            temp = temp->lchild; // 向左走到尽头
        }
        visit(temp->data);
        // 若当前节点无右子树且后继不是头节点，则输出后继的值
        while (temp->RTag == 1 && temp->rchild != ThrHead) {
            temp = temp->rchild;
            visit(temp->data);
        }
        temp = temp->rchild; // 遍历右子树
    }
}

请按先序顺序输入节点值，输入‘#’代表节点为空：
ABDH##I##EJ###CF##G##
H, D, I, B, J, E, A, F, C, G,
C:\Users\fy\Documents\workspace\visual_studio\CMakeProject1\out\build\x64-Debug\CMakeProject1.exe (进程 11472)已退出，代码为 0。
按任意键关闭此窗口. . .