线索化二叉树

【道德经·第八章】上善若水。水善利万物而不争，处众人之所恶（wù），故几（jī）于道。居善地，心善渊，与善仁，言善信，正善治，事善能，动善时。夫唯不争，故无尤。

线索二叉树

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

线索二叉树结构

struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag; // 左、右线索标志：0：孩子；1：前驱
    ThreadNode(int x) : data(x), lchild(nullptr), rchild(nullptr), ltag(0), rtag(0) {

    }
};

typedef ThreadNode* ThreadTree;

中序线索化二叉树

中序线索化

void InThread(ThreadTree& p, ThreadTree& pre) {
    // 线索化左子树
    InThread(p->lchild, pre);  
    // 左子树为空，建立前驱索引
    if(p->lchild == nullptr) {
        p->lchild = pre;
        p->ltag = 1;
    }
    // 建立前驱索引的后继索引
    if(pre != nullptr && pre->rchild==nullptr) {
        pre->rchild = p;   
        pre->rtag = 1;
    }
    // 标记当前节点为刚访问过得节点
    pre = p;  
    // 线索化右子树
    InThread(p->rchild, pre);
}

建立线索化二叉树

void CreateInThread(ThreadTree T) {
    ThreadTree pre = nullptr;
    if(T != nullptr) {
        InThread(T, pre);
        pre->rchild = nullptr;
        pre->rtag = 1;
    }
}

求第一个节点

ThreadNode* FirstNode(ThreadTree p) {
    while(p->ltag == 0) p = p->lchild; // 最左下节点，不一定是叶节点
    return p;
}

求后继节点

ThreadNode* NextNode(ThreadNode* p) {
    if(p->rtag == 0) return FirstNode(p->rchild);
    else return p->rchild;  // rtag=1 直接返回后继线索
}

不含头结点的中序线索二叉树的中序遍历

void InOrder(ThreadTree T) {
    for(ThreadNode *p = FirstNode(T); p != nullptr; p = NextNode(p))
        printf("%d ", p->data);
}

中序线索化二叉树上实现前序遍历的算法

void PreOrder(ThreadNode* node) {
    while(node != nullptr) {
        printf("%d ", node->data);  // 先访问根节点

        if(node->ltag == 0) {  
            // 有左子树，即为后继
            node = node->lchild;
        } else if(node->rtag == 0) {
            // 有柚子树，即为后继
            node = node->rchild;
        } else {
            // 无左右子树
            while(node!=nullptr && node->rtag==1) // 检测后继线索 直到找到有右子树的结点
                node = node->rchild;
            if(node != nullptr){
                node =node->rchild;  //该结点的右子树为后继
            }
        }
    }
}