0. 线索二叉树的由来

问题的引出：如何找到指定结点p，在中序遍历序列中的前驱？

思路：
对于一颗二叉树来说，用户只能拿到它的根节点，其余所有结点均需要通过遍历来完成。基于此：
从根节点出发，重新进行一次中序遍历，
      指针p为指定节点，指针q 为当前访问的结点，指针final为答案
      指针 pre 记录上一个被访问的结点
                              当q == p时，pre为前驱

如果是找后继？——>方法一样，只是修改一下判断条件：当pre == p时，q为后继

缺点：找特定结点的前驱、后继很不方便；遍历操作必须从根开始，于是就有了线索二叉树

---

1. 线索二叉树的基本概念

为了充分利用空间和保存特定遍历情况下前后结点的关系，我们用指针指向某个结点的前驱和后继，这样的指针称之为线索，加上线索的二叉链表称之为线索链表，相应的二叉树就称之为线索二叉树（Threaded Binary Tree）

通过上面的描述我们可以感受到，线索二叉树等于是把一棵二叉树变成了一个双向链表。因此我们对二叉树以某种次序遍历使其变为线索二叉树的过程称作为线索化

---

2. 线索二叉树的存储结构体【有二叉链表、线索链表的概念】

---

3. 手画线索二叉树

3.1 画中序线索二叉树【其余同理】

3.2 概念：中序前驱/中序后继 【其余同理——先序前驱/先序后继；后序前驱/后序后继】

---

4. 二叉树线索化

4.1 中序线索化

王道书上的代码【实际上和上面的ppt图片代码一样】：

typedef struct ThreadNode{
    ElemType data;  
    struct ThreadNode *lchild, *rchild;   
    int ltag, rtag;
}ThreadNode, *ThreadTree;

// 中序遍历线索化二叉树
void InThread(ThreadTree &p, ThreadTree &pre) {
	if (p != NULL) {
		InThread(p->lchild, pre);
		-------------------------这部分相当于visit（）-------------------------
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
		---------------------------------------------------------------------
		InThread(p->rchild, pre);
	}
}

// 创建线索二叉树T
void CreateInThread(ThreadTree T) {
	ThreadNode *pre = NULL;
	if (T != NULL) {
		InThread(T, pre);
		//处理最后一个结点
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

---

4.2 先序线索化【需多加个：if(p->ltag == 0)】

王道书上的代码【实际上和上面的ppt图片代码一样】：

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;

// 先序遍历线索化二叉树
void PreThread(ThreadTree &p, ThreadTree &pre){
    if (p != NULL) {
        -------------------------这部分相当于visit（）-------------------------
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
		---------------------------------------------------------------------

		if(p->ltag == 0)//如果指针指向的是孩子，目的是防止转圈
        		PreThread(p->lchild, pre);
		PreThread(p->rchild, pre);
	}
}

// 创建线索二叉树
void CreatePreThread(ThreadTree T){
    ThreadNode *pre = NULL;
	if (T != NULL) {
		PreThread(T, pre);
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

4.3 后序线索化【和中序线索化代码一样，只是visit( ) 位置不同】

王道书上的代码【实际上和上面的ppt图片代码一样】：

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;

// 后序遍历线索二叉树
void PostThread(ThreadTree &p, ThreadTree &pre){
    PostThread(p->lchild, pre);
	PostThread(p->rchild, pre);
	-------------------------这部分相当于visit（）-------------------------
    if (p != NULL) {
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
	}
	---------------------------------------------------------------------
}

// 后序线索化二叉树T
void CreatePostThread(ThreadTree T){
    ThreadNode *pre = NULL;
	if (T != NULL) {
		PostThread(T, pre);
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

5. 线索二叉树找前驱/后继

5.1 中序线索二叉树

①找后继

// 找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode *FirstNode(ThreadNode *p){
    // 循环找到最左下结点（不一定是叶结点）
    while(p->ltag==0)
        p=p->lchild;
    return p;
}

// 在中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p){
    // 右子树中最左下的结点
    if(p->rtag==0)
        return FirstNode(p->rchild);
    else
        return p->rchild;
}

// 对中序线索二叉树进行中序循环（非递归方法实现）
void InOrder(ThreadNode *T){
    for(ThreadNode *p=FirstNode(T); p!=NULL; p=NextNode(p)){
        visit(p);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

②找前驱

// 找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p){
    // 循环找到最右下结点（不一定是叶结点）
    while(p->rtag==0)
        p=p->rchild;
    return p;
}

// 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *PreNode(ThreadNode *p){
    // 左子树中最右下的结点
    if(p->ltag==0)
        return LastNode(p->lchild);
    else
        return p->lchild;
}

// 对中序线索二叉树进行中序循环（非递归方法实现）
void RevOrder(ThreadNode *T){
    for(ThreadNode *p=LastNode(T); p!=NULL; p=PreNode(p))
        visit(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

5.2 先序线索二叉树

①找后继

②找前驱【没有】

zhe

---

5.3 后序线索二叉树

①找后继【没有】

②找前驱

---