线索二叉树

中序线索二叉树

先使用中序遍历二叉树得到数组

xxxxxxxxxx
1
1
[D,G,B,E,A,F,C]

根据数组中每个结点的前后，让没有子结点的指针指向数组中的前后结点

• D 结点没有左孩子，所以指向数组中的前边，也就是NULL；
• G 结点没有子结点，左结点指向数组中的前一个结点(前驱结点), D; 右结点指向数组中的后一个结点(后继结点), B 每个结点会新增两个状态ltag和rtag用来标记是指向子结点还是上面描述的前驱后继结点（0 表示是子结点，1 表示是前驱/后继）

其他线索二叉树

前序线索二叉树就是把数组改成前序遍历得到的数组 后序线索二叉树同理

二叉树线索化

二叉树线索化的实质就是遍历一次二叉树 先序线索二叉树找不到前驱 后序线索二叉树找不到后继 除非使用三叉链表或者从根开始遍历

中序线索二叉树

1. 设置全局变量pre，用于指向刚刚访问过的结点（p的前驱结点）
2. 指针p指向正在访问的结点
3. 检查p的左指针是否为空，为空就将它指向pre
4. 检查pre的右指针是否为空，为空就将它指向p

xxxxxxxxxx
20
1
ThreadNode *pre = NULL;//全局变量用于暂存当前访问结点的前驱
2
void visit(ThreadNode *q) {
3
    if (q->lchild == NULL) {//左子树为空，建立前驱线索
4
        q->lchild = pre;
5
        q->ltag = 1;
6
    }
7
    if (pre != NULL && pre->rchild == NULL) {//建立前驱结点的后继线索
8
        pre->rchild = q;
9
        pre->rtag = 1;
10
    }
11
    pre = q;//标记当前结点为前驱
12
}
13

14
void InThread(ThreadTree T) {
15
    if (T != NULL) {
16
        InThread(T->lchild);//线索化左子树
17
        visit(T);访问根结点
18
        InThread(T->rchild);//线索化右子树
19
    }
20
}

找前驱后继结点参考仓库代码

先序线索二叉树

线索化参考仓库代码 如果使用三叉链表（有指向父结点的指针）可以找到，不然找不到

后序线索二叉树

线索化参考仓库代码 和先序找前驱一样，可以使用三叉链表找到后继

最后一个结点rchild和lchild需要进行处理％