高级树结构之线索化二叉树

淩亂°似流年 2024-03-30 16:33 61阅读 0赞

#### 文章目录 ####

*  一 线索化二叉树简介
 *  二 线索化规则
 *  三 前序线索化
 *   *  3.1 代码演示
 *  四 中序线索化
 *   *  4.1 代码演示
 *  五 后序线索化
 *   *  5.1 代码演示

## 一 线索化二叉树简介 ##

*  线索化：将一颗二叉树的结点指向为空的指针，线索化为某一种顺序遍历的的指向下一个按顺序的结点的指针
 *  ***一颗为顺序化的二叉树的前序遍历顺序***  
    ![在这里插入图片描述][8337d13514d449a9a91912979341492b.png]
 *  对其前序遍历线索化后，遍历顺序依次为：  
    ![在这里插入图片描述][d7919cb4cd95467a86cc07120fdce7da.png]

## 二 线索化规则 ##

*  结点的左指针，指向当前遍历顺序的直接前驱结点。
 *  结点的右指针，指向当前遍历顺序的直接后继结点。
 *  上图前序遍历线索化之后的指向如下图：  
    ![在这里插入图片描述][ae7c6b4326c14a559eccdadcdff42b0d.png]
 *  为了区分某个结点的指针指向是其左右孩子？还是某种顺序遍历线索【直接前驱、直接后继结点】？
 *  需要在结点的结构体中增加一组标志位【左、右标志位】，来区分左右指针的指向代表的意义
    
     *  leftTag / rightTag为1，表示左 / 右指针指向的是前驱 / 后继结点
     *  leftTag / rightTag为0，表示左 / 右指针指向的是左孩子 / 右孩子

typedef char E;
    typedef struct TreeNode {
        
        E element;
        struct TreeNode *left;
        struct TreeNode *right;
        //左、右标志位
        // 为1表示：这一边指向的是线索；为0表示：正常的孩子结点
        int leftTag, rightTag;
        //为后序遍历准备，指向双亲结点
        struct TreeNode *parent;
    } *Node;

## 三 前序线索化 ##

*  二叉树结构  
    ![在这里插入图片描述][3cf6701d531d4ba29426a294018ea926.png]  
    ![在这里插入图片描述][1f3b528d593a47fea98f79ce0b8ae0cf.png]
 *  具体的实现代码，希望诸君认真阅读体会！

### 3.1 代码演示 ###

![在这里插入图片描述][33ae1bb5ef634aa2bddf39194a6ce1c3.png]

## 四 中序线索化 ##

*  二叉树中序线索化的结构  
    ![在这里插入图片描述][98bdb19367204c45a53f0e926930832b.png]  
    ![在这里插入图片描述][c4d7f778383e4f9cbc876423f4d4b231.png]
 *  中序遍历线索化相较于前序遍历线索化，只具体的线索化代码的位置即可。
 *  对二叉树进行中序便利的代码实现稍有复杂。

### 4.1 代码演示 ###

*  具体的实现代码，希望诸君认真阅读体会！

#include<iostream>
    using namespace std;
    typedef char E;
    typedef struct TreeNode {
        
        E element;
        struct TreeNode *left;
        struct TreeNode *right;
        //左、右标志位
        // 为1表示：这一边指向的是线索；为0表示：正常的孩子结点
        int leftTag, rightTag;
        //为后序遍历准备，指向双亲结点
        struct TreeNode *parent;
    } *Node;
    Node pre = NULL;//保存前一个结点
    
    Node createNode(E element) {
        
        Node node = (Node) malloc(sizeof(struct TreeNode));
        node->left = node->right = NULL;
        node->leftTag = node->rightTag = 0;
        node->element = element;
        return node;
    }
    
    //中序遍历线索化
    void inOrderThreaded(Node root) {
        
        if (root == NULL) return;
        //注意只有标志为0，才可以继续进行，否则，为线索
        if (root->leftTag == 0) {
        
            inOrderThreaded(root->left);
        }
    
        //---------线索化------------
        //判断当前结点的左边是否为空，如果是，就指向上一个结点
        if (root->left == NULL) {
        
            root->left = pre;
            //修改标志位
            root->leftTag = 1;
        }
        //判断上一个结点的右边是否为NULL
        // 如果为空，就进行线索化，指向当前结点
        if (pre && pre->right == NULL) {
        
            pre->right = root;
            pre->rightTag = 1;
        }
        pre = root;
        //-----------------------
    
        if (root->rightTag == 0) {
        
            inOrderThreaded(root->right);
        }
    }
    
    void inOrder(Node root) {
        
        while (root) {
        
            //先走到最左边结点
            //如果左边一直都不是线索，那就一直往左找，直到找到一个左边是线索为止
            while (root && root->leftTag == 0) {
        
                root = root->left;
            }
            //中序开始打印
            cout << root->element << " ";
            //左边打印完就该打印，右边 右边如果是线索化之后的结果表示 是下一个节点
            while (root && root->rightTag == 1) {
        
                root = root->right;
                cout << root->element << " ";
            }
            //最后继续向右节点开始 重复上述操作。
            root = root->right;
        }
    }
    
    int main() {
        
        Node a1 = createNode('A');
        Node b1 = createNode('B');
        Node c1 = createNode('C');
        Node d1 = createNode('D');
        Node e1 = createNode('E');
        a1->left = b1;
        b1->left = d1;
        a1->right = c1;
        b1->right = e1;
        pre = NULL;
        inOrderThreaded(a1);
        cout << "中序遍历的结果为：";
        inOrder(a1);
        cout << endl;
        return 0;
    }

![在这里插入图片描述][64f64edf96a843eebcc217a0e6f8f5f6.png]

## 五 后序线索化 ##

*  二叉树后序遍历线索化的结构：  
    ![在这里插入图片描述][2ac9182d4c5d45dba20097ffd1d492b3.png]  
    ![在这里插入图片描述][5528dd7d98cd45f09d28f928304334da.png]
 *  后序遍历，需要先完成左右子树的遍历。左边子树遍历完成后，并不一定能找到右子树的根结点。比如：在遍历完左子数根节点B之后，就无法找到右树的根结点C。所以需要在节点结构体中设置设置指向双亲节点的指针。

### 5.1 代码演示 ###

*  具体的实现代码，希望诸君认真阅读体会！

#include<iostream>
    using namespace std;
    typedef char E;
    typedef struct TreeNode {
        
        E element;
        struct TreeNode *left;
        struct TreeNode *right;
        //左、右标志位
        // 为1表示：这一边指向的是线索；为0表示：正常的孩子结点
        int leftTag, rightTag;
        //为后序遍历准备，指向双亲结点
        struct TreeNode *parent;
    } *Node;
    Node pre = NULL;//保存前一个结点
    
    Node createNode(E element) {
        
        Node node = (Node) malloc(sizeof(struct TreeNode));
        node->left = node->right = NULL;
        node->leftTag = node->rightTag = 0;
        node->element = element;
        return node;
    }
    
    //后序遍历线索化
    void postOrderThreaded(Node root) {
        
        if (root == NULL) return;
    
        //注意只有标志为0，才可以继续进行，否则，为线索
        if (root->leftTag == 0) {
        
            postOrderThreaded(root->left);
            //左边完事之后，如果不为空，那么设定父子关系
            if (root->left != NULL)
                root->left->parent = root;
        }
        if (root->rightTag == 0) {
        
            postOrderThreaded(root->right);
            //右边完事之后，如果不为空，那么设定父子关系
            if (root->right != NULL)
                root->right->parent = root;
        }
    
        //---------线索化------------
        //判断当前结点的左边是否为空，如果是，就指向上一个结点
        if (root->left == NULL) {
        
            root->left = pre;
            //修改标志位
            root->leftTag = 1;
        }
        //判断上一个结点的右边是否为NULL
        // 如果为空，就进行线索化，指向当前结点
        if (pre && pre->right == NULL) {
        
            pre->right = root;
            pre->rightTag = 1;
        }
        pre = root;
        //---------------------------
    }
    
    void postOrder(Node root) {
        
        //记录上一次遍历的结点
        Node last = NULL, node = root;
        while (node) {
        
            //依旧是从整棵树最左边开始 同时加入防止无线循环的条件
            while (node->left != last && node->leftTag == 0) {
        
                node = node->left;
            }
            //左边遍历完了，如果右边是线索，就一路向前
            while (node && node->rightTag == 1) {
        
                cout << node->element << " ";
                last = node;
                node = node->right;
            }
            if (node == root && node->right == last) {
        
                //当左子树便利完成，我们需要去寻找左子树根节点的兄弟节点
                //通过parent拿到兄弟节点，但是如果当前结点是根节点，需要特殊处理，因为根节点没有父节点
                cout << node->element << " ";
                //后序遍历中，根节点一定是最后一个节点。所以直接返回就可以了。
                return;
            }
            //如果当前节点的上一个遍历的结点，那么就继续进行
            while (node && node->right == last) {
        
                cout << node->element << " ";
                last = node;
                node = node->parent;
            }
            //从左子树遍历上来，当前节点的右边，要么是线索，要么是右子树。
            if (node && node->rightTag == 0) {
        
                //如果不是线索，就直接走右边，如果是等到下一轮再说
                node = node->right;
            }
        }
    }
    
    int main() {
        
       	Node a2 = createNode('A');
        Node b2 = createNode('B');
        Node c2 = createNode('C');
        Node d2 = createNode('D');
        Node e2 = createNode('E');
        a2->left = b2;
        b2->left = d2;
        a2->right = c2;
        b2->right = e2;
        pre = NULL;
        postOrderThreaded(a2);
        cout << "后序遍历的结果为：";
        postOrder(a2);
        return 0;
    }

![在这里插入图片描述][bf8591afecc74383830c097867622e65.png]

[8337d13514d449a9a91912979341492b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2516d34baaa84f7a89b02b78e55f000f.png
[d7919cb4cd95467a86cc07120fdce7da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/24b2324f8d6c448fb9e4380db4eb7b7a.png
[ae7c6b4326c14a559eccdadcdff42b0d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/962984d9860740db8ebe2f3497f74966.png
[3cf6701d531d4ba29426a294018ea926.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/210e428b09fb4540829018105644d7ae.png
[1f3b528d593a47fea98f79ce0b8ae0cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/06ae0740bf28454cad66173a57264630.png
[33ae1bb5ef634aa2bddf39194a6ce1c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8042f69a11694f6f9fba8ae695d43bd5.png
[98bdb19367204c45a53f0e926930832b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c99fc739ce1845e0b42290d50f1b97fb.png
[c4d7f778383e4f9cbc876423f4d4b231.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1b3e3375592a4eeb811e6b4083557617.png
[64f64edf96a843eebcc217a0e6f8f5f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ca99aae32a024a01a0fda1bf2d21dbe6.png
[2ac9182d4c5d45dba20097ffd1d492b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/11946b4bf74b4b4f97f07b93f7ee8e8a.png
[5528dd7d98cd45f09d28f928304334da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/498b129882fe4b74a6be9d94367e6b88.png
[bf8591afecc74383830c097867622e65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fa46ec81022140aeb42f4a5c881b8b91.png