遍历中序线索二叉树

/*
 * 2008/06/30 By Yao Jianming
 * */
#include
#include

struct node {
        bool left_thread;
        bool right_thread;
        node *left_child;
        node *right_child;
        char data;
}*root;

//插入右节点

void insert_right(node *parent, node *p)
{
        p->right_thread = p->left_thread = true;
        p->left_child = parent;
        p->right_child = parent->right_child;
        parent->right_thread = false;
        parent->right_child = p;
}

//插入左节点

void insert_left(node *parent, node *p)
{
        p->right_thread = p->left_thread = true;
        p->right_child = parent;
        p->left_child = parent->left_child;
        parent->left_thread = false;
        parent->left_child = p;
}

//找到当前节点的后节点

node* insucc(node *p)
{
        if(p->right_thread == true) {
                return p->right_child;
        }
        else {
                p = p->right_child;
                while(p->left_thread != true) {
                        p = p->left_child;
                }
                return p;
        }
}

//遍历线索二叉树

void order(node *head)
{
        while(head->right_child != head) {
                printf("%c\n", head->data);
                head = insucc(head);
        }
}

int main()
{
        root = (node*)malloc(sizeof(node));
        root->right_thread = false;
        root->right_child = root;
        root->left_thread = true;
        root->left_child = root;

        node *A = (node*)malloc(sizeof(node));
        A->data = 'A';
        insert_left(root, A);

        node *G = (node*)malloc(sizeof(node));
        G->data = 'G';
        insert_right(A, G);

        node *Add = (node*)malloc(sizeof(node));
        Add->data = '+';
        insert_left(A, Add);

        node *H = (node*)malloc(sizeof(node));
        H->data = 'H';
        insert_right(Add, H);

        node *Multi = (node*)malloc(sizeof(node));
        Multi->data = '*';
        insert_left(Add, Multi);

        node *I = (node*)malloc(sizeof(node));
        I->data = 'I';
        insert_right(Multi, I);

        node *Div = (node*)malloc(sizeof(node));
        Div->data = '/';
        insert_left(Multi, Div);

        node *J = (node*)malloc(sizeof(node));
        J->data = 'J';
        insert_right(Div, J);

        node *O = (node*)malloc(sizeof(node));
        O->data = 'O';
        insert_left(Div, O);

        order(O);
}

以上实现的线索树如下：