【详解】前、中、后序线索化二叉树及其遍历

╰+哭是因爲堅強的太久メ 2022-07-03 23:50 139阅读 0赞

## 前序线索化二叉树 ##

前序线索化二叉树是在二叉树前序遍历的过程中对其进行线索化，将叶子节点和单分支节点的指针域线索化成其前驱和后继，利用递归的特点，并且定义两个节点指针，一个在前一个在后，在中序遍历的过程中通过这两个前后指针建立前驱后继的连接关系。  
**实现代码：**

//前序线索化二叉树
    void PreThBinaryTree(BtThNode*root, BtThNode *&p)
    {
        if (root == NULL)
            return;
        if (p != NULL&&root->leftchid == NULL)
        {
            root->leftchid = p;
            root->Ltag = THEAD;
        }
        if (p != NULL&&p->rightchild == NULL)
        {
            p->Rtag = THEAD;
            p->rightchild = root;
        }
        p = root;
        if (root->Ltag != THEAD)//如果不判断就会造成死循环，造成栈溢出
            PreThBinaryTree(root->leftchid, p);
        if (root->Rtag!=THEAD)//同理，因为在程序一开始就对其左右孩子为NULL时就做了前驱后继的处理，
            //但是改了标志位，所以此处可根据标志位判断是子树还是前驱后继
            PreThBinaryTree(root->rightchild, p);
    }

**遍历代码：**

BtThNode*next_pre(BtThNode*p)
    {
        if (p == NULL)
            return NULL;
        if (p->Ltag == LINK)
            return p->leftchid;
        else
            return p->rightchild;
    }
    void PreOderThBinaryTree(BtThNode*p)//遍历前序线索化二叉树
    {
        if (p == NULL)
            return;
        for (BtThNode*s = p; s != NULL; s = next_pre(s))
        {
            cout << s->data << " ";
        }
        cout << endl;
    }

## 中序线索化二叉树 ##

中序线索化二叉树跟前序线索化二叉树很相似，在中序遍历的过程中对叶子结点和单分支节点的指针域线索化为前驱和后继，实现代码如下：  
**代码：**

//中序线索化二叉树
    void InThTree(BtThNode*root,BtThNode *&p)
    {
        if (root == NULL)
            return;
        InThTree(root->leftchid,p);
        //cout << root->data << " ";
        if (root->leftchid == NULL)
        {
            root->leftchid = p;
            root->Ltag = THEAD;
        }
        if (p != NULL&&p->rightchild == NULL)
        {
            p->rightchild = root;
            p->Rtag = THEAD;
        }
        p = root;
        InThTree(root->rightchild,p);
    }

线索化后的二叉树对其进行遍历的过程就不需要使用递归或者栈的使用，直接根据前驱后继遍历，节省了空间，代码实现如下：  
**遍历过程：**

BtThNode* first(BtThNode *p)
    {
        while (p!=NULL && p->Ltag != THEAD)
        {
            p = p->leftchid;
        }
        return p;
    }
    
    BtThNode* next(BtThNode *p)
    {
        if (p == NULL)
            return NULL;
        if (p->Rtag == THEAD)
            return p->rightchild;
        else
            return first(p->rightchild);
    }
    //遍历中序线索化二叉树
    void InOderThTree(BtThNode*p)
    {
        if (p == NULL)
            return;
        for (BtThNode*s = first(p); s != NULL; s = next(s))
        {
            cout << s->data << " ";
        }
        cout << endl;
    }

## 后序线索化二叉树 ##

后序线索化二叉树在后序遍历的过程中对其进行线索化，这里不赘述：  
**代码：**

//后序线索化二叉树
    void PastThBinaryTree(BtThNode*root, BtThNode *&p)
    {
        if (root == NULL)
            return;
        PastThBinaryTree(root->leftchid, p);
        PastThBinaryTree(root->rightchild, p);
        if (root->leftchid == NULL)
        {
            root->leftchid = p;
            root->Ltag = THEAD;
        }
        if (p != NULL&&p->rightchild == NULL)
        {
            p->rightchild = root;
            p->Rtag = THEAD;
        }
        p = root;
    }

**遍历的过程：**

BtThNode* first_past(BtThNode*p)//找第一个前驱
    {
        while (p != NULL&&p->Ltag != THEAD)//不能写成p->leftchild==NULL，因为当线索化之后空指针域也将被改为前驱和后继
            p = p->leftchid;
        while (p->Rtag != THEAD)
            p = p->rightchild;
        return p;
    }
    BtThNode*Parent(BtThNode*p, BtThNode*child)//找孩子的双亲
    {
        if (p == NULL||child==NULL||p==child)
            return NULL;
        //这里已经将叶子节点指针域线索化成了前驱和后继，所以得加另外的限制
        if (p->Ltag!=THEAD&&p->leftchid== child||p->Rtag!=THEAD&&p->rightchild==child)
            return p;
        BtThNode*s = NULL;
        if (p->Ltag!=THEAD)//这里同样是要判断是左右孩子还是前驱后继，否则就会造成循环
            s=Parent(p->leftchid, child);
        if (s == NULL&&p->Rtag!=THEAD)
            s = Parent(p->rightchild, child);
        return s;
    }
    BtThNode*next_past(BtThNode*p, BtThNode*s)//找下一个后继
    {
        if (s == NULL)
            return NULL;
        if (s->Rtag == THEAD)
            return s->rightchild;
        else
        {
            BtThNode*parent = Parent(p,s);
            if (parent == p)
                if (parent->leftchid==s)//如果右孩子的双亲等于s说明右子树已经遍历过就直接返回根节点
                    return first_past(p->rightchild);
            return parent;
        }
    }
    void PastOderThBinaryTree(BtThNode*p)//遍历后序线索化二叉树
    {
        for (BtThNode *s = first_past(p); s != NULL; s = next_past(p, s))
        {
            cout << s->data << " ";
        }
        cout << endl;
    }

## 附： ##

**总的源代码：**

#include<iostream>
    using namespace std;
    typedef char Elemtype;
    typedef enum{ LINK = 0, THEAD = 1 } tagtype;
    typedef struct _BtThNode
    {
        _BtThNode* leftchid;
        _BtThNode*rightchild;
        tagtype Ltag;
        tagtype Rtag;
        Elemtype data;
    }BtThNode, *BtThTree;
    
    BtThNode *BuyThNode()
    {
        BtThNode *p = new BtThNode();
        //BtThNode *p = (BtThNode *)malloc(sizeof(BtThNode));
        if (p == NULL)
        {
            throw("new failed!");
            exit(-1);
        }
        memset(p, 0, sizeof(BtThNode));
        return p;
    }
    BtThNode * CreateThBinaryTree(char *&str)
    {
        if (str == NULL || *str == '#')
            return NULL;
        BtThNode *p = BuyThNode();
        p->data = *str;
        p->leftchid = CreateThBinaryTree(++str);
        p->rightchild = CreateThBinaryTree(++str);
        return p;
    }
    
    //中序线索化二叉树
    void InThTree(BtThNode*root,BtThNode *&p)
    {
        if (root == NULL)
            return;
        InThTree(root->leftchid,p);
        //cout << root->data << " ";
        if (root->leftchid == NULL)
        {
            root->leftchid = p;
            root->Ltag = THEAD;
        }
        if (p != NULL&&p->rightchild == NULL)
        {
            p->rightchild = root;
            p->Rtag = THEAD;
        }
        p = root;
        InThTree(root->rightchild,p);
    }
    BtThNode* first(BtThNode *p)
    {
        while (p!=NULL && p->Ltag != THEAD)
        {
            p = p->leftchid;
        }
        return p;
    }
    
    BtThNode* next(BtThNode *p)
    {
        if (p == NULL)
            return NULL;
        if (p->Rtag == THEAD)
            return p->rightchild;
        else
            return first(p->rightchild);
    }
    //遍历中序线索化二叉树
    void InOderThTree(BtThNode*p)
    {
        if (p == NULL)
            return;
        for (BtThNode*s = first(p); s != NULL; s = next(s))
        {
            cout << s->data << " ";
        }
        cout << endl;
    }
    
    
    //前序线索化二叉树
    void PreThBinaryTree(BtThNode*root, BtThNode *&p)
    {
        if (root == NULL)
            return;
        if (p != NULL&&root->leftchid == NULL)
        {
            root->leftchid = p;
            root->Ltag = THEAD;
        }
        if (p != NULL&&p->rightchild == NULL)
        {
            p->Rtag = THEAD;
            p->rightchild = root;
        }
        p = root;
        if (root->Ltag != THEAD)//如果不判断就会造成死循环，造成栈溢出
            PreThBinaryTree(root->leftchid, p);
        if (root->Rtag!=THEAD)//同理，因为在程序一开始就对其左右孩子为NULL时就做了前驱后继的处理，
            //但是改了标志位，所以此处可根据标志位判断是子树还是前驱后继
            PreThBinaryTree(root->rightchild, p);
    }
    BtThNode*next_pre(BtThNode*p)
    {
        if (p == NULL)
            return NULL;
        if (p->Ltag == LINK)
            return p->leftchid;
        else
            return p->rightchild;
    }
    void PreOderThBinaryTree(BtThNode*p)//遍历前序线索化二叉树
    {
        if (p == NULL)
            return;
        for (BtThNode*s = p; s != NULL; s = next_pre(s))
        {
            cout << s->data << " ";
        }
        cout << endl;
    }
    //后序线索化二叉树
    void PastThBinaryTree(BtThNode*root, BtThNode *&p)
    {
        if (root == NULL)
            return;
        PastThBinaryTree(root->leftchid, p);
        PastThBinaryTree(root->rightchild, p);
        if (root->leftchid == NULL)
        {
            root->leftchid = p;
            root->Ltag = THEAD;
        }
        if (p != NULL&&p->rightchild == NULL)
        {
            p->rightchild = root;
            p->Rtag = THEAD;
        }
        p = root;
    }
    BtThNode* first_past(BtThNode*p)//找第一个前驱
    {
        while (p != NULL&&p->Ltag != THEAD)//不能写成p->leftchild==NULL，因为当线索化之后空指针域也将被改为前驱和后继
            p = p->leftchid;
        while (p->Rtag != THEAD)
            p = p->rightchild;
        return p;
    }
    BtThNode*Parent(BtThNode*p, BtThNode*child)//找孩子的双亲
    {
        if (p == NULL||child==NULL||p==child)
            return NULL;
        //这里已经将叶子节点指针域线索化成了前驱和后继，所以得加另外的限制
        if (p->Ltag!=THEAD&&p->leftchid== child||p->Rtag!=THEAD&&p->rightchild==child)
            return p;
        BtThNode*s = NULL;
        if (p->Ltag!=THEAD)//这里同样是要判断是左右孩子还是前驱后继，否则就会造成循环
            s=Parent(p->leftchid, child);
        if (s == NULL&&p->Rtag!=THEAD)
            s = Parent(p->rightchild, child);
        return s;
    }
    BtThNode*next_past(BtThNode*p, BtThNode*s)//找下一个后继
    {
        if (s == NULL)
            return NULL;
        if (s->Rtag == THEAD)
            return s->rightchild;
        else
        {
            BtThNode*parent = Parent(p,s);
            if (parent == p)
                if (parent->leftchid==s)//如果右孩子的双亲等于s说明右子树已经遍历过就直接返回根节点
                    return first_past(p->rightchild);
            return parent;
        }
    }
    void PastOderThBinaryTree(BtThNode*p)//遍历后序线索化二叉树
    {
        for (BtThNode *s = first_past(p); s != NULL; s = next_past(p, s))
        {
            cout << s->data << " ";
        }
        cout << endl;
    }