线索化二叉树

我们知道一棵二叉树实际上可以由多个结点组成，每个结点都有一个左右指针，指向其左右孩子。我们在最后也讲解了二叉树的遍历，包括前序、中序、后序以及层序遍历。只不过在遍历时实在是太麻烦了，我们需要借助栈来帮助我们完成这项遍历操作。

一棵二叉树的某些结点会存在NULL的情况，我们可以利用这些为NULL的指针，将其线索化为某一种顺序遍历的指向下一个按顺序的结点的指针，这样我们在进行遍历的时候，就会很方便了。

线索化的规则为：

  • 结点的左指针，指向其当前遍历顺序的前驱结点。
  • 结点的右指针，指向其当前遍历顺序的后继结点。
    在线索化之后，G的指向情况如下：
    示意图
    这样，G原本两个为NULL的指针就被我们利用起来了，但是现在有一个问题，我们怎么知道，某个结点的指针到底是指向的其左右孩子，还是说某种遍历顺序下的前驱或是后继结点呢？所以，我们还需要分别为左右添加一个标志位，来表示左右指针到底指向的是孩子还是遍历线索：
1
2
3
4
5
6
7
8
typedef char E;

typedef struct TreeNode {
    E element;
    struct TreeNode * left;
    struct TreeNode * right;
    int leftTag, rightTag;   //标志位，如果为1表示这一边指针指向的是线索，不为1就是正常的孩子结点
} * Node;

接着是H结点，同样的，因为H结点的左右指针都是NULL，那么我们也可以将其线索化：
示意图
接着我们来看结点E，这个结点只有一个右孩子，没有左孩子，左孩子指针为NULL，我们也可以将其线索化：
示意图
最后，整棵二叉树完成线索化之后，除了遍历顺序的最后一个结点没有后续之外，其他为NULL的指针都被利用起来了：
示意图
在利用上那些为NULL的指针之后，当我们再次进行前序遍历时，我们不需要再借助栈了，而是可以一路向前。

线索化

前序遍历

这里我们弄一个简单一点的线索化二叉树，来尝试对其进行遍历：
示意图
首先我们要对这棵二叉树进行线索化，将其变成一棵线索化二叉树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Node createNode(E element){   //单独写了个函数来创建结点
    Node node = malloc(sizeof(struct TreeNode));
    node->left = node->right = NULL;
    node->rightTag = node->leftTag = 0;
    node->element = element;
    return node;
}

int main() {
    Node a = createNode('A');
    Node b = createNode('B');
    Node c = createNode('C');
    Node d = createNode('D');
    Node e = createNode('E');

    a->left = b;
    b->left = d;
    a->right = c;
    b->right = e;
}

进行线索化，我们只需要正常按照对应的遍历顺序进行即可，不过在遍历过程中需要留意那些存在空指针的结点，我们需要修改其指针的指向：

1
2
3
4
5
6
void preOrderThreaded(Node root){   //前序遍历线索化函数
    if(root == NULL) return;
  	//别急着写打印
    preOrderThreaded(root->left);
    preOrderThreaded(root->right);
}

首先还是老规矩，先把前序遍历写出来，然后我们需要进行判断，如果存在指针指向为NULL，那么就将其线索化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Node pre = NULL;  //这里我们需要一个pre来保存后续结点的指向
void preOrderThreaded(Node root){   //前序遍历线索化函数
    if(root == NULL) return;

    if(root->left == NULL) {   //首先判断当前结点左边是否为NULL，如果是，那么指向上一个结点
        root->left = pre;
        root->leftTag = 1;  //记得修改标记
    }
    if(pre && pre->right == NULL) {  //然后是判断上一个结点的右边是否为NULL，如果是那么进行线索化，指向当前结点.这里加入pre是为了避免第一个pre为NULL的情况下无法运行
        pre->right = root;
        pre->rightTag = 1;  //记得修改标记
    }
    
    pre = root;   //每遍历完一个，需要更新一下pre，表示上一个遍历的结点

  	if(root->leftTag == 0)   //注意只有标志位是0才可以继续向下，否则就是线索了
    	preOrderThreaded(root->left);
  	if(root->rightTag == 0)
    	preOrderThreaded(root->right);
}

现在我们成功得到了一棵线索化之后的二叉树，那么怎么对其进行遍历呢？我们只需要一个简单的循环就可以了：

1
2
3
4
5
6
7
8
9
void preOrder(Node root){  //前序遍历一棵线索化二叉树非常简单
    while (root) {   //到头为止
        printf("%c", root->element);   //因为是前序遍历，所以直接按顺序打印就行了
        if(root->leftTag == 0) 
            root = root->left;   //如果是左孩子，那么就走左边
        else
            root = root->right;   //如果左边指向的不是孩子，而是线索，那么就直接走右边，因为右边无论是线索还是孩子，都要往这边走了
    }
}

中序遍历

中序遍历需要重新线索化，线索化后长这样:
示意图

我们接着来看看中序遍历的线索化二叉树，整个线索化过程我们只需要稍微调整位置就行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Node pre = NULL;  //这里我们需要一个pre来保存后续结点的指向
void inOrderThreaded(Node root){   //前序遍历线索化函数
    if(root == NULL) return;
    if(root->leftTag == 0)
        inOrderThreaded(root->left);
  
    //------  线索化 -------  现在放到中间去，其他的还是一样的
    if(root->left == NULL) {
        root->left = pre;
        root->leftTag = 1;
    }
    if(pre && pre->right == NULL) {
        pre->right = root;
        pre->rightTag = 1;
    }
    pre = root;
    //--------------------
  
    if(root->rightTag == 0)
        inOrderThreaded(root->right);
}

那么像这样的一棵树，我们怎么对其进行遍历呢？中序遍历要稍微麻烦一些：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void inOrder(Node root){
    while (root) {   //因为中序遍历需要先完成左边，所以说要先走到最左边才行
        while (root && root->leftTag == 0)    //如果左边一直都不是线索，那么就一直往左找，直到找到一个左边是线索的为止，表示到头了
            root = root->left;

        printf("%c", root->element);   //到最左边了再打印，中序开始

        while (root && root->rightTag == 1) {   //打印完就该右边了，右边如果是线索化之后的结果，表示是下一个结点，那么就一路向前，直到不是为止
            root = root->right;
            printf("%c", root->element);   //注意按着线索往下就是中序的结果，所以说沿途需要打印
        }
        root = root->right;  //最后继续从右结点开始，重复上述操作
    }
}

后序遍历

最后我们来看看后序遍历的线索化，同样的，我们只需要在线索化时修改为后序就行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Node pre = NULL;  //这里我们需要一个pre来保存后续结点的指向
void inOrderThreaded(Node root){   //前序遍历线索化函数
    if(root == NULL) return;
    if(root->leftTag == 0)
        inOrderThreaded(root->left);
    if(root->rightTag == 0)
        inOrderThreaded(root->right);
    //------  线索化 -------   现在这一坨移到最后，就是后序遍历的线索化了
    if(root->left == NULL) {
        root->left = pre;
        root->leftTag = 1;
    }
    if(pre && pre->right == NULL) {
        pre->right = root;
        pre->rightTag = 1;
    }
    pre = root;
    //--------------------
}

线索化完成之后，变成一棵后续线索化二叉树：
示意图
后序遍历的结果看起来有点怪怪的，但是这就是后序，那么怎么对这棵线索化二叉树进行后续遍历呢？这就比较复杂了。因此要完成后续遍历，我们只能对结点进行改造：

1
2
3
4
5
6
7
typedef struct TreeNode {
    E element;
    struct TreeNode * left;
    struct TreeNode * right;
    struct TreeNode * parent;   //指向双亲（父）结点
    int leftTag, rightTag;
} * Node;

现在每个结点都保存其父结点，这样就可以顺利地找上去了。现在我们来编写一下吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Node pre = NULL;  //这里我们需要一个pre来保存后续结点的指向
void postOrderThreaded(Node root){   //前序遍历线索化函数
    if(root == NULL) return;
    if(root->leftTag == 0) {
        postOrderThreaded(root->left);
        if(root->left) root->left->parent = root;  //左边完事之后，如果不为空，那么就设定父子关系
    }
    if(root->rightTag == 0) {
        postOrderThreaded(root->right);
        if(root->right) root->right->parent = root;   //右边完事之后，如果不为空，那么就设定父子关系
    }
    //------  线索化 -------
    if(root->left == NULL) {
        root->left = pre;
        root->leftTag = 1;
    }
    if(pre && pre->right == NULL) {
        pre->right = root;
        pre->rightTag = 1;
    }
    pre = root;
    //--------------------
}

后序遍历代码如下：

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
void postOrder(Node root){
    Node last = NULL, node = root;  //这里需要两个暂存指针，一个记录上一次遍历的结点，还有一个从root开始
    while (node) {
        while (node->left != last && node->leftTag == 0)    //依然是从整棵树最左边结点开始，和前面一样，只不过这里加入了防无限循环机制，看到下面就知道了
            node = node->left;
        while (node && node->rightTag == 1) {   //左边完了还有右边，如果右边是线索，那么直接一路向前，也是跟前面一样的
            printf("%c", node->element);   //沿途打印
            last = node;
            node = node->right;
        }
        if (node == root && node->right == last) {
            //上面的操作完成之后，那么当前结点左右就结束了，此时就要去寻找其兄弟结点了，我们可以
            //直接通过parent拿到兄弟结点，但是如果当前结点是根结点，需要特殊处理，因为根结点没有父结点了
            printf("%c", node->element);
            return;   //根节点一定是最后一个，所以说直接返回就完事
        }
        while (node && node->right == last) {    //如果当前结点的右孩子就是上一个遍历的结点，那么一直向前就行
            printf("%c", node->element);   //直接打印当前结点
            last = node;
            node = node->parent;
        }
        //到这里只有一种情况了，是从左子树上来的，那么当前结点的右边要么是线索要么是右子树，所以直接向右就完事
        if(node && node->rightTag == 0) {  //如果不是线索，那就先走右边，如果是，等到下一轮再说
            node = node->right;
        }
    }
}

这里记得在上面的createNode函数中将父节点初始化为NULL，否则可能会报错。

说些什么吧！

twikoo