中序线索二叉树的构造和遍历

中序线索二叉树的构造

结构体

typedef struct ThreadNode{
    int data;
    int lTag, rTag;
    struct ThreadNode *lChild, *rChild;
}ThreadNode, *ThreadTree;

递归算法

void inThread(ThreadTree &p, ThreadTree &pre){
    while(p){
        inThread(p->lChild, pre); //线索化左子树
        if(p->lChild == NULL){
            p->lChild = pre;
            pre->lTag = 1;
        }
        if(pre != NULL && pre->rChlld == NULL){
            pre->rChild = p;
            pre->rTag = 1;
        }
        pre = p;
        inThread(p->rChild, pre);
    }
}

通过中序遍历线索化二叉树主过程

void createThreadTree(ThreadTree root){
    ThreadTree pre = NULL;
    if(p){
        inThread(root, pre);
        pre -> rChild = NULL;
        pre -> rTag = 1;
    }
}

中序线索二叉树的遍历

求线索二叉树的第一个结点

ThreadNode* FirstNode(ThreadTree root){
    while(root->lTag == 0) root = root->lChild;
    return root;
}   

给定结点，求线索二叉树的后一个结点

ThreadNode* nextNode(ThreadNode p){
    if(p->rTag == 1) return p->rChild;
    return FirstNode(p->rChild);
}

求线索二叉树的最后一个结点

ThreadNode* lastNode(ThreadTree root){
    if(root->rChild == NULL) return root;
    ThreadNode *pre, *p;
    while(p != NULL){
        pre = p;
        p = NextNode(p);
    }
    return pre;
}

给定结点p，求结点的前驱

ThreadNode* preNode(ThreadNode *p){
    if(p->lTag == 1) return p->lChild;
    ThreadNode *pre, *q= NextNode(p->lChild);
    while(q != p){
        pre = q;
        q = NextNode(q);
    }
    return pre;
}   

遍历中序二叉树

void inOrder(ThreadTree root){
    while(ThreadNode *p = FirstNode(root); p != NULL; p = NextNode(p)) cout << p->data << " ";
    cout << endl;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接