C语言中序线索二叉树的建立及遍历

小灰灰 2022-04-24 09:46 169阅读 0赞

有n个节点的二叉树共有2\*n个指针域，但是实际用到的只有n-1（总分支数=总指针域数）个，故剩余n+1个指针域被浪费。现将空闲指针域利用，使其指向节点前驱或后继，并做如下规定：

1、若节点有左（右）孩子，则左（右）指针指向其左右孩子；否则左指针指向前驱，右指针指向后继  
2、为标明其左右指针是指向左（右）孩子还是前驱（后继），设标志域LTag（RTag）  
LTag = \{ 0 : lchild 域指示结点的左孩子； 1 : lchild 域指示结点的前驱 \}  
RTag = \{ 0 : rchild 域指示结点的右孩子； 1 : rchild 域指示结点的后继 \}

## 1.中序线索二叉树 ##

### 1.1示意图 ###

（此图与代码无关，只是为了说明中序线索二叉树节点关系）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]

### 1.2 关于头节点、中序首节点、中序尾节点的几点声明 ###

**设中序遍历第一个节点、最后一个节点分别为first、last；头节点为ThrHead**  
1、头节点非根节点  
2、first->lchild：指向ThrHead  
3、last->rchild：指向ThrHead  
4、ThrHead->lchild：指向根节点  
5、ThrHead->rchild：指向last

#include <malloc.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char elemType;
    typedef struct BiTNode { 
        elemType data;
        struct BiTNode *lchild, *rchild;
        int LTag, RTag;
    } BiThreadNode, *BiThreadTree;
    
    void visit(elemType x);            // 输出元素x
    BiThreadTree createBiThreadTree(); // 先序输入节点的值，构造二叉树
    BiThreadNode *CreateInThrTree(BiThreadTree T); // 创建中序线索二叉树
    void InThreading(BiThreadTree T);              // 中序遍历线索化
    void ThrInOrderTraverse(BiThreadTree T);       // 遍历中序线索二叉树
    
    BiThreadNode *pre; // 当前访问节点的前驱
    
    int main(void)
    { 
        BiThreadTree root;
    
        printf("请按先序顺序输入节点值，输入‘#’代表节点为空：\n");
        root = createBiThreadTree();
        BiThreadNode *ThrHead = CreateInThrTree(root);
        ThrInOrderTraverse(ThrHead);
    
        return 0;
    }
    
    void visit(elemType x) {  printf("%c, ", x); }
    BiThreadTree createBiThreadTree()
    { 
        BiThreadNode *T;
        char ch;
    
        if ((ch = getchar()) == '#')
            T = NULL;
        else { 
            T = (BiThreadNode *)malloc(sizeof(BiThreadNode));
            T->data = ch;
            T->lchild = createBiThreadTree();
            T->rchild = createBiThreadTree();
        }
    
        return T;
    }
    void InThreading(BiThreadTree T)
    { 
        if (T != NULL) { 
            InThreading(T->lchild); // 线索化左子树
    
            // 左孩子为空，则lchild指向前驱pre
            if (T->lchild == NULL) { 
                T->LTag = 1;
                T->lchild = pre;
            }
            else
                T->LTag = 0;
    
            // 前驱pre右孩子为空，则当前节点为前驱pre的后继
            if (pre->rchild == NULL) { 
                pre->RTag = 1;
                pre->rchild = T;
            }
            else
                pre->RTag = 0;
    
            pre = T;
            InThreading(T->rchild); // 线索化右子树
        }
    }
    BiThreadNode *CreateInThrTree(BiThreadTree T)
    { 
        BiThreadNode *ThrHead; // 中序线索二叉树头节点（非根节点）
        /* * 设中序遍历第一个节点、最后一个节点分别为first、last * 则：first->lchild指向ThrHead * last->rchild指向ThrHead * ThrHead->lchild：指向根节点 * ThrHead->rchild：指向last */
    
        ThrHead = (BiThreadNode *)malloc(sizeof(BiThreadNode));
        ThrHead->RTag = 1;
        ThrHead->rchild = ThrHead; // 先将ThrHead->rchild指向自身
        ThrHead->LTag = 0;
    
        if (T == NULL)
            ThrHead->lchild = ThrHead; // 若根节点为空，则ThrHead->lchild指向自身
        else { 
            ThrHead->lchild = T;
            pre = ThrHead; // 将ThrHead赋给pre，pre为中序线索树中first节点前驱
            InThreading(T);        // 二叉树线索化完毕，pre指向last节点
            pre->rchild = ThrHead; // 将ThrHead作为last节点后继
            pre->RTag = 1;
            ThrHead->rchild = pre; // 将ThrHead->rchild指向pre(last)
        }
    
        return ThrHead;
    }
    void ThrInOrderTraverse(BiThreadTree ThrHead)
    { 
        BiThreadNode *temp = ThrHead->lchild; // 让temp指向根节点
    
        while (temp != ThrHead) { 
            while (temp->LTag == 0)
                temp = temp->lchild; // 向左走到尽头
            visit(temp->data);
            // 若当前节点无右子树且后继不是头节点，则输出后继的值
            while (temp->RTag == 1 && temp->rchild != ThrHead) { 
                temp = temp->rchild;
                visit(temp->data);
            }
            temp = temp->rchild; // 遍历右子树
        }
    }

![在这里插入图片描述][20190422225619908.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220216/049c60b7d01a49a682ca3f15122166de.png
[20190422225619908.jpg]: /images/20220216/6827607113824a43812bc385fd13b398.png