考研笔记

板子：中序线索化

★ 级：会画线索、认得代码就行。中序遍历时用 pre 记住上一个访问的结点：**自己的左指针为空，就指向 pre；pre 的右指针为空，就指向自己。**原理和手算见 5.3.2 线索二叉树。

代码

typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;                          // 0：指针指向孩子；1：指针是线索（指向前驱或后继）
} ThreadNode, *ThreadTree;                   // 建树时 ltag、rtag 都要初始化为 0
 
void InThread(ThreadTree p, ThreadNode *&pre) {   // 中序遍历，同时加线索；pre：上一个访问的结点
    if (p == NULL) return;
    InThread(p->lchild, pre);                // 先线索化左子树
    if (p->lchild == NULL) {                 // 自己的左指针为空：指向前驱 pre
        p->lchild = pre;
        p->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL) {    // 前驱的右指针为空：指向后继，也就是自己
        pre->rchild = p;
        pre->rtag = 1;
    }
    pre = p;                                 // 访问完 p，p 成为下一个结点的前驱
    InThread(p->rchild, pre);                // 再线索化右子树
}
 
void CreateInThread(ThreadTree T) {
    ThreadNode *pre = NULL;
    if (T != NULL) {
        InThread(T, pre);
        pre->rchild = NULL;                  // 收尾：最后一个结点没有后继，这两行不能漏
        pre->rtag = 1;
    }
}
 
ThreadNode *Firstnode(ThreadNode *p) {       // 以 p 为根的子树中，中序遍历的第一个结点
    while (p->ltag == 0) p = p->lchild;      // 一路向左，直到左指针是线索（不一定是叶子）
    return p;
}
 
ThreadNode *Nextnode(ThreadNode *p) {        // p 在中序下的后继
    if (p->rtag == 0) return Firstnode(p->rchild);   // 有右子树：后继是右子树的第一个结点
    return p->rchild;                        // 右指针是线索：直接就是后继
}
 
void InorderThread(ThreadTree T) {           // 不用栈的中序遍历
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
        printf("%d ", p->data);
}

复杂度：线索化时间 ，空间 （递归）；遍历时间 ，空间 。

关键边界

位置为什么
pre 写成引用 ThreadNode *&pre递归里改了 pre，外层要能看到。教材写的是 ThreadTree &pre，是同一个意思
判断 pre != NULL访问第一个结点时还没有前驱，不能访问 pre->rchild
CreateInThread 的收尾两行最后一个结点的右指针没有人来处理，要手动置空并把 rtag 设为 1
ltag、rtag 初始化为 0Firstnode 靠 ltag == 0 往左走，没初始化就会乱走

BST 删除、AVL 旋转

这两项同样是 ★ 级，只考手算，不考写代码：

链接

反向链接