C语言——线索二叉树（前序、中序、后序-附代码）

桃扇骨 2024-03-22 09:28 92阅读 0赞

## 一、什么是线索二叉树 ##

> 线索二叉树（Threaded Binary Tree）是一种特殊的二叉树，通过将空指针改为线索（即前驱或后继指针）的方式，将二叉树中的空闲指针利用起来，从而实现对二叉树的高效遍历和查找。
> 
> 线索化是将二叉树以某种遍历方式进行扫描，并为每个节点添加线索的过程。
> 
>  *  线索二叉树的节点定义包含两个标志位，分别表示其左右指针是否为线索。
>  *  如果左孩子节点为空，则将其左孩子指针指向该节点的直接前驱节点；
>  *  如果右孩子节点为空，则将其右孩子指针指向该节点的直接后继节点。
> 
> **这样，在线索化之后，可以通过线索快速定位节点的前驱和后继，避免了不必要的遍历，提高了查找效率。**
> 
> **线索二叉树的好处主要在于它可以提高对二叉树的遍历效率。**
> 
> 常规二叉树的遍历需要使用递归或堆栈等数据结构，效率较低。而线索二叉树通过将原本为空的指针改为前驱或后继线索，实现了对二叉树的高效遍历和查找。
> 
> **同时，线索二叉树可以有效地节约存储空间，避免了在节点中存储额外的空指针，提高了内存利用率。**

## 二、全部代码（内有详细注释） ##

## 2.0、文件结构与代码示例 ##

> ![67a2f794ce534890919cc9717fdaf2d2.png][]
> 
> **需要注意的是，因为指针是按值传递的，所以在函数中如果需要修改指针变量的值（如pNode），必须使用指向指针的指针或指针的引用等方式，否则修改不会生效。 在代码中，由于函数没有返回值，因此无法判断函数是否执行成功。如果出现错误或异常情况，程序可能会发生意外的行为或崩溃。**

> **代码中构建的二叉树**
> 
> ![a7412ac4078a4a8182cdb6d2245ce238.png][]

### 2.1、main.cpp ###

#include "test.h"
    int main() {
    
        char *str = "123##45##6##7#8##";     // 前序构造二叉树
        BThead binTreeHead;
        initBinTree(&binTreeHead,'#');
    
        createBinTreeNode(&binTreeHead,str);  // 前序构造二叉树
    
        ForEachBinTree(&binTreeHead,1);    // 遍历二叉树（1：前序，2：中序，3：后序）
        threadBinTree(&binTreeHead, 1);    // 线索二叉树（1：前序，2：中序，3：后序）
    
    
        printf("%p",&binTreeHead);
    }

### 2.2、test.h ###

#pragma once
    
    #include<stdio.h>
    #include<malloc.h>
    #include<assert.h>
    #include <math.h>
    #include <iostream>
    
    //元素类型
    #define ElemType char
    #define MyType int
    
    
    // 二叉树结点
    typedef struct BinTreeNode{
        // 标志  0代表是孩子  1代表是前驱或后继
        MyType L_tag;
        MyType R_tag;
    
        // 节点
        struct BinTreeNode *L_child;
        struct BinTreeNode *R_child;
    
        // 值
        ElemType value;
    }BTnode, *BT;
    
    // 二叉树的头结点
    typedef struct BinTreeHead{
        ElemType endFlag;
        BinTreeNode *BTNode;
    }BThead;
    
    
    
    void initBinTree(BinTreeHead *head, ElemType endFlag);  // 头节点初始化
    
    void createBinTreeNode(BinTreeHead *head, char *str);  // 接收 头结点  一个字符串地址
    
    void ForEachBinTree(BinTreeHead *head,int i); // 遍历二叉树（1：前序，2：中序，3：后序）
    
    void threadBinTree(BinTreeHead *head, int i); // 线索二叉树（1：前序，2：中序，3：后序）

### 2.3、test.cpp ###

#include"test.h"
    // 定义数据类型
    struct BinTreeNode *pre = NULL;
    
    // 申请结点
    BinTreeNode* mallocNode(ElemType e){
        BinTreeNode *newNode = (BinTreeNode*)malloc(sizeof(BinTreeNode));
        assert(newNode != NULL);
        newNode->L_child = newNode->R_child = NULL;
        newNode->L_tag = newNode->R_tag = 0;  //线索化之前左右标记都初始为指针链
        newNode->value = e;
        return newNode;
    }
    
    // 头节点初始化
    void initBinTree(BinTreeHead *head, ElemType endFlag){
        head->endFlag = endFlag;
        head->BTNode = NULL;
    
    }
    
    // 创建二叉树（前序）
    void createBTreeNode(BinTreeHead *pHead, BinTreeNode **pNode, char **pString) {
    
    //    printf("%d \n",**pString);
    //    printf("%d \n",pHead->endFlag);
        // 如果终止：
        if(**pString == pHead->endFlag){
            *pNode = NULL;
            return;
        }
    
        // 创建新的根结点
        *pNode = mallocNode(**pString);
    
        // 创建左孩子
        (*pString)++;
        createBTreeNode(pHead, &((*pNode)->L_child), pString);
        // 创建右孩子
        (*pString)++;
        createBTreeNode(pHead, &((*pNode)->R_child), pString);
    
    }
    
    // 创建二叉树的头结点
    void createBinTreeNode(BinTreeHead *head, char *str){
        createBTreeNode(head, &(head->BTNode), &str);
    }
    
    //---------------------------------------遍历二叉树
    // 输出二叉树
    void visit(BinTreeNode *pNode){
    
        printf("value: %c \n",pNode->value);
    
    }
    
    // 前序遍历二叉树
    void preOrder(BinTreeNode *pNode){
    
        if(pNode == NULL){
            return;
        }
    
        visit(pNode);  // 输出结点value
    
        preOrder(pNode->L_child);
        preOrder(pNode->R_child);
    }
    
    // 中序遍历二叉树
    void inOrder(BinTreeNode *pNode){
    
        if(pNode == NULL){
            return;
        }
    
        inOrder(pNode->L_child);
        visit(pNode);  // 输出结点value
        inOrder(pNode->R_child);
    }
    // 后序遍历二叉树
    void afterOrder(BinTreeNode *pNode){
    
        if(pNode == NULL){
            return;
        }
    
        afterOrder(pNode->L_child);
        afterOrder(pNode->R_child);
        visit(pNode);  // 输出结点value
    }
    
    // 用头结点遍历二叉树
    void ForEachBinTree(BinTreeHead *head,int i){
        // 如果是1，则前序遍历
        if(i==1){
            preOrder(head->BTNode);
            return;
        }
        // 如果是2，则中序遍历
        if(i==2){
            inOrder(head->BTNode);
            return;
        }
        // 如果是3，则后序遍历
        if(i==3){
            afterOrder(head->BTNode);
            return;
        }
        printf("请输入对应的数字！");
    }
    //-------------------------------------------------------------- 线索二叉树
    
    // 线索化
    void createThread(BinTreeNode **pNode){
    
    
        // 如果左孩子为空      （前驱）
        if((*pNode)->L_child == NULL && (*pNode)->L_tag == 0){
            (*pNode)->L_tag = 1;
            (*pNode)->L_child = pre;
        }
    
        // 如果pre的右孩子为空  （后继）
        if(pre->R_child == NULL && (*pNode)->R_tag == 0){
            pre->R_tag = 1;
            pre->R_child = *pNode;
        }
    
        // 回退之前 pre 赋值 当前结点
        pre = (*pNode);
    
    }
    
    // 前序
    void preThreadBinTree(BinTreeNode **pNode){
    
        if(*pNode == NULL){
            return;
        }
        createThread(&(*pNode));  // 线索化
        if((*pNode)->L_tag == 0){    // 如果没有被线索化 ！！！ --------防止转圈 ！！！
            preThreadBinTree(&((*pNode)->L_child));
        }
        preThreadBinTree(&((*pNode)->R_child));
    
    }
    
    // 中序
    void inThreadBinTree(BinTreeNode **pNode){
        if(*pNode == NULL){
            return;
        }
        inThreadBinTree(&((*pNode)->L_child));
        createThread(&(*pNode));  // 输出结点value
        inThreadBinTree(&((*pNode)->R_child));
    
    }
    
    // 后序
    void afterThreadBinTree(BinTreeNode **pNode){
        if(*pNode == NULL){
            return;
        }
    
        preThreadBinTree(&((*pNode)->L_child));
        preThreadBinTree(&((*pNode)->R_child));
        createThread(&(*pNode));  // 输出结点value
    }
    
    
    // 创建线索二叉树
    void threadBinTree(BinTreeHead *head, int i){
        // pre初始化 - 让其指向根结点
        pre = head->BTNode;
    
        // 如果是1，则前序 创建线索二叉树
        if(i==1){
            preThreadBinTree(&(head->BTNode));
            return;
        }
        // 如果是2，则中序 创建线索二叉树
        if(i==2){
            inThreadBinTree(&(head->BTNode));
            return;
        }
        // 如果是3，则后序 创建线索二叉树
        if(i==3){
            afterThreadBinTree(&(head->BTNode));
            return;
        }
        printf("请输入对应的数字！");
    }

## 三、注意事项 ##

> **构造线索二叉树时，需要注意以下几点：**
> 
> 1.  在线索化过程中，**需要保证已经线索化的节点不能再次线索化，否则会形成死循环。**
> 2.  由于线索化操作会改变原有的指针关系，因此需要在构造完成后进行还原，以便保证二叉树结构的完整性。
> 3.  如果通过线索来遍历二叉树，需要考虑如何恰当地使用前驱和后继线索，以避免遍历过程中出现错误。
> 
> **在进行前序、中序、后序构造时，需要注意以下几点：**
> 
> 1.  通过前序遍历和中序遍历，可以唯一确定一个二叉树。因此，在进行构造时，需要保证输入的前序和中序序列是正确的，且序列中的元素没有重复。
> 2.  对于中序遍历和后序遍历，同样也可以唯一确定一个二叉树。在进行构造时，需要满足输入的中序和后序序列是正确的，且序列中的元素没有重复。
> 3.  在实际操作中，**需要注意递归的边界情况，以避免出现死循环或者溢出等异常情况。**

[67a2f794ce534890919cc9717fdaf2d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/4b2a507b316e47bbbf7260c0dd70144c.png
[a7412ac4078a4a8182cdb6d2245ce238.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/fd983f71371546b4ba72735ca3c0f592.png