线索二叉树详解以及代码实现

Bertha 。 2022-08-09 15:49 127阅读 0赞

参照《大话数据结构》188到194页。

一、二叉树的线索存储结构定义

/* 二叉树线索存储结构定义
       Link = 0,代表指向左右孩子的指针
       Thread= 1 代表指向前驱或后继的线索*/
    typedef enum{ Link, Thread} PointerTag;
    
    typedef char TypeData;
    
    typedef struct BiTreeNode
    {
        TypeData data;
        struct BiTreeNode *lchild, *rchild;
        PointerTag LTag;
        PointerTag RTag;
    }BITREENODE;

![20151030142345266][]

二、对二叉树进行中序遍历，并把所有的空的左孩子指针指向该节点的前驱，空的右孩子指针指向该节点的后继。

![20151030142638726][]

![20151030142648345][]

三、代码实现（慢慢去看）

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    using namespace std;
    
    /* 二叉树线索存储结构定义
       Link = 0,代表指向左右孩子的指针
       Thread= 1 代表指向前驱或后继的线索*/
    typedef enum{ Link, Thread} PointerTag;
    
    typedef char TypeData;
    
    typedef struct BiTreeNode
    {
        TypeData data;
        struct BiTreeNode *lchild, *rchild;
        PointerTag LTag;
        PointerTag RTag;
    }BITREENODE;
    
    
    BITREENODE* createBiTree();          /* 创建二叉树 */
    void preOrderBiTree(BITREENODE* T);  /* 前序遍历该二叉树 */
    void InThreadBiTree(BITREENODE* T);  /* 中序遍历线索化该二叉树 */
    void InOrderBiTree_Thread(BITREENODE* T); /* 中序遍历该线索二叉树 */
    
    
    
    /* 创建二叉树 */
    BITREENODE* createBiTree()
    {
        TypeData ch = 0;
        BITREENODE* pNewNode = NULL;
    
        cin >> ch;
    
        if(ch == '#')
        {
            pNewNode = NULL;
        }
        else
        {
            /* 给节点分配内存 */
            pNewNode = (BITREENODE*)malloc(sizeof(BITREENODE));
            pNewNode->data = ch;
            pNewNode->LTag = pNewNode->RTag = Link;
    
            /* 递归构建左右子树 */
            pNewNode->lchild = createBiTree();
            pNewNode->rchild = createBiTree();
        }
    
        return pNewNode;
    }
    
    /* 前序遍历该二叉树 */
    void preOrderBiTree(BITREENODE* T)
    {
        if(T)
        {
           cout << T->data << " ";
           preOrderBiTree(T->lchild);
           preOrderBiTree(T->rchild);
        }
    }
    
    /* 中序遍历线索化该二叉树 */
    BITREENODE* pre = NULL;  //全局变量，始终指向刚刚访问过的节点
    void InThreadBiTree(BITREENODE* T)
    {
        if(T)
        {
            /* 递归线索化左子树 */
            InThreadBiTree(T->lchild);
    
            /* 没有左孩子 */
            if(!T->lchild)
            {
                T->LTag = Thread;  //前驱线索
                T->lchild = pre;   //左孩子指针，指向后继
            }
    
            /* 前驱没有右孩子 */
            if(pre != NULL && pre->rchild == NULL)
            {
                pre->RTag = Thread;  //后驱线索
                pre->rchild = T;     //前驱的右孩子指向后继
            }
    
            /* 保持pre指向T的前驱 */
            pre = T;
    
            /* 递归右子树线索化 */
            InThreadBiTree(T->rchild);
        }
    }
    
    /* 中序遍历该线索二叉树 */
    void InOrderBiTree_Thread(BITREENODE* T)
    {
        BITREENODE* p = T;
    
        while(p != NULL)
        {
    
            /* 当LTag == 0时循环到中序序列第一个节点 */
            while(p->LTag == Link)
            {
                p = p->lchild;
            }
    
            /*打印出该节点的数值*/
            cout << p->data << " ";
    
            /* 打印出当前节点的后继*/
            while(p->RTag == Thread && p->rchild != NULL)
            {
                p = p->rchild;
                cout << p->data << " ";
            }
    
            /* 指向该节点的后继 */
            p = p->rchild;
        }
    
        cout << endl;
    
    }
    
    
    int main(void)
    {
        BITREENODE* pRoot = NULL;
    
        /* 创建二叉树 */
        pRoot = createBiTree();
    
        /* 前序遍历该二叉树,这时候还没有线索化二叉树，可以这样进行前序遍历 */
        preOrderBiTree(pRoot);
        cout << endl;
    
        /* 中序线索化该二叉树 */
        InThreadBiTree(pRoot);
    
        /* 前序遍历该二叉树,这时候已经中序线索化了二叉树，就不可以这样中序遍历了 */
       // preOrderBiTree(pRoot);
    
       InOrderBiTree_Thread(pRoot);
    
        return 0;
    }

[20151030142345266]: /images/20220731/ee3d6e6ea66246bca20a0c9944f1039b.png
[20151030142638726]: /images/20220731/fd966b603cd146c5bf0a7f5c5b6bfb35.png
[20151030142648345]: /images/20220731/c5ab6d337fd542f890d0cb0679dadbb8.png