线索化二叉树的实现

我就是我 2022-06-04 03:53 178阅读 0赞

之前我们介绍过二叉树和它的具体实现[http://blog.csdn.net/qq\_34021920/article/details/78698930][http_blog.csdn.net_qq_34021920_article_details_78698930]，但是不难发现，普通的二叉树存在以下的缺陷：

*  递归遍历有可能导致栈溢出；
 *  非递归遍历有可能降低程序的效率
 *  想要找到在某种遍历形式下某个结点的前驱或后继比较难
 *  树中有大量的空指针域造成浪费，比如：假如二叉树中有n个结点，则必定有n+1个空指针域

**线索化二叉树**就解决了这些问题，当某节点的左指针为空时，令该指针指向按照某种方式遍历二叉树时得到该节点的前驱结点；当某节点的右指针为空时，令该指针指向按照某种方式遍历二叉树时得到该节点的后继结点。  
但是这样我们又会发现一个问题：左指针指向的结点是它的左孩子结点还是前驱结点，右指针指向的结点是它的右孩子结点还是后继结点？因此需要增加两个线索标志位来区分这两种情况。

来看看线索化二叉树节点的构造：

enum PointerTag
    {
        THREAD,//线索
        LINK //子问题
    };
    
    template<class T>
    struct ThdBinaryTreeNode
    {
        T _data;//数据
        ThdBinaryTreeNode<T>* _pLeft;//左孩子
        ThdBinaryTreeNode<T>* _pRight;//右孩子
        PointerTag _leftTag;//左线索
        PointerTag _rightTag;//右线索
    
        ThdBinaryTreeNode(const T& data)
            :_data(data)
            , _pLeft(NULL)
            , _pRight(NULL)
            , _leftTag(LINK)
            , _rightTag(LINK)
        {}
    };

![这里写图片描述][SouthEast]  
线索化二叉树同二叉树类似，也有三种遍历(前序遍历线索化，中序遍历线索化，后序遍历线索化)，上三张图，一看就清楚了。

![这里写图片描述][SouthEast 1]

![这里写图片描述][SouthEast 2]

![这里写图片描述][SouthEast 3]

因为后序遍历线索化较为繁琐，所以在这里不多做解释。感兴趣的同学可以参考下面链接[后序线索化：http://blog.csdn.net/my\_heart\_/article/details/52087948][http_blog.csdn.net_my_heart_article_details_52087948]  
好了，直接上代码：

**BinaryTreeThd.h**

#pragma once
    
    #include <iostream>
    using namespace std;
    #include <stdlib.h>
    #include <string.h>
    
    enum PointerTag
    {
        THREAD,
        LINK
    };
    
    template<class T>
    struct ThdBinaryTreeNode
    {
        T _data;//数据
        ThdBinaryTreeNode<T>* _pLeft;//左孩子
        ThdBinaryTreeNode<T>* _pRight;//右孩子
        PointerTag _leftTag;//左线索
        PointerTag _rightTag;//右线索
    
        ThdBinaryTreeNode(const T& data)
            :_data(data)
            , _pLeft(NULL)
            , _pRight(NULL)
            , _leftTag(LINK)
            , _rightTag(LINK)
        {}
    };
    
    template<class T>
    class ThdBinaryTree
    {
        typedef ThdBinaryTreeNode<T> Node;
        typedef ThdBinaryTreeNode<T>* pNode;
    public:
        //无参构造函数
        ThdBinaryTree()
            :_pRoot(NULL)
        {}
        //有参构造函数
        ThdBinaryTree(T* arr, size_t size, const T& invalid)
        {
            size_t index = 0;
            _CreateThdBinaryTree(_pRoot, arr, size, index, invalid);
        }
        //前序遍历
        void PreOrder()
        {
            _PreOrder(_pRoot);
            cout << endl;
        }
        //前序线索化（递归实现）
        void PreOrderThreading()
        {
            pNode prev = NULL;
            _PreOrderThreading(_pRoot, prev);
            //在这里线索化最后一个节点
            if (prev)
                prev->_rightTag = THREAD;   
        }
        //前序遍历线索化(非递归)
        void PreOrderThdNoR()
        {
            _PreOrderThdNoR(_pRoot);
        }
        //中序遍历
        void InOrder()
        {
            _InOrder(_pRoot);
            cout << endl;
        }
        //中序线索化(递归实现)
        void InOrderThreading()
        {
            pNode prev = NULL;
            _InOrderThreading(_pRoot, prev);
    
            //线索化最后一个节点
            if (_pRoot)
            {
                pNode right = _pRoot->_pRight;
                while (right->_pRight)
                {
                    right = right->_pRight;
                }
                right->_rightTag = THREAD;
            }
        }
        //中序遍历线索化(非递归实现)
        void InOrderThdNoR()
        {
            _InOrderThdNoR(_pRoot);
        }
        //后序遍历
        void PostOrder()
        {
            _PostOrder(_pRoot);
            cout << endl;
        }
        //后序线索化(递归实现)
        void PostOrderThreading()
        {
            pNode prev = NULL;
            _PostOrderThreading(_pRoot, prev);
        }
    
    private:
        void _CreateThdBinaryTree(pNode& pRoot, T* arr, size_t& size, size_t& index, const T& invalid)
        {
            if (index < size&&arr[index] != invalid)
            {
                pNode pNewNode = new Node(arr[index]);
                _CreateThdBinaryTree(pNewNode->_pLeft, arr, size, ++index, invalid);
                _CreateThdBinaryTree(pNewNode->_pRight, arr, size, ++index, invalid);
                pRoot = pNewNode;
            }
        }
        //递归前序线索化
        void _PreOrderThreading(pNode pCur, pNode& prev)
        {
            if (pCur == NULL)
                return;
            //线索化当前节点的左指针域
            if (pCur->_pLeft == NULL)
            {
                pCur->_pLeft = prev;
                pCur->_leftTag = THREAD;
            }
            //线索化前一个节点的右指针域
            if (prev&&prev->_pRight == NULL)//(保证第一次进入时prev不为空)
            {
                prev->_pRight = pCur;
                prev->_rightTag = THREAD;
            }
            prev = pCur;
            if (pCur->_leftTag == LINK)
                _PreOrderThreading(pCur->_pLeft, prev);
            if (pCur->_rightTag == LINK)
                _PreOrderThreading(pCur->_pRight, prev);
        }
        //前序遍历(只能在线索化之前使用，下同)
        void _PreOrder(pNode pRoot)
        {
            if (pRoot)
            {
                cout << pRoot->_data << " ";
                if (pRoot->_leftTag == LINK)
                    _PreOrder(pRoot->_pLeft);
                if (pRoot->_rightTag == LINK)
                    _PreOrder(pRoot->_pRight);
            }
        }
        //非递归前序遍历线索化
        void _PreOrderThdNoR(pNode pCur)
        {
            while (pCur)
            {
                while (pCur->_leftTag == LINK)
                {
                    cout << pCur->_data << " ";
                    pCur = pCur->_pLeft;
                }
                cout << pCur->_data << " ";
                pCur = pCur->_pRight;//pCur已经是最左侧节点了，可以替换下面繁琐的方法
            }
            cout << endl;
        }
        //void _PreOrderThdNoR(pNode pCur)
        //{
        
        //  while (pCur)
        //  {
        
        //      //找最左侧路径中的节点并访问
        //      while (pCur->_leftTag == LINK)
        //      {
        
        //          cout << pCur->_data << " ";
        //          pCur = pCur->_pLeft;
        //      }
        //      cout << pCur->_data << " ";
        //      //访问连在一起的后继节点
        //      while (pCur->_rightTag == THREAD)
        //      {
        
        //          pCur = pCur->_pRight;
        //          cout << pCur->_data << " ";
        //      }
        //      if (pCur->_leftTag == LINK)
        //      {
        
        //          pCur = pCur->_pLeft;
        //      }
        //      else
        //          pCur = pCur->_pRight;
        //  }
        //  cout << endl;
        //}
        //递归中序线索化
        void _InOrderThreading(pNode pCur, pNode& prev)
        {
            if (pCur == NULL)
                return;
            //线索化左子树
            _InOrderTreading(pCur->_left, prev);
            //线索化根节点
            if (pCur->_pLeft == NULL)
            {
                pCur->_pLeft = prev;
                pCur->_leftTag = THREAD;
            }
            if (prev&&prev->_pRight == NULL)
            {
                prev->_pRight = pCur;
                prev->_rightTag = THREAD;
            }
            prev = pCur;
            //线索化右子树
            if (pCur->_rightTag == LINK)
                _InOrderTreading(pCur->_right, prev);
        }
        //中序遍历
        void _InOrder(pNode pRoot)
        {
            if (pRoot)
            {
                _InOrder(pRoot->_pLeft);
                cout << pRoot->_data << " ";
                _InOrder(pRoot->_pRight);
            }
        }
        //非递归中序遍历(线索化)
        void _InOrderThdNoR(pNode pCur)
        {
            while (pCur)
            {
                while (pCur->_leftTag == LINK)
                {
                    pCur = pCur->_pLeft;
                }
                cout << pCur->_data << " ";
                while (pCur->_rightTag == THREAD)
                {
                    pCur = pCur->_pRight;
                    if (pCur == NULL)//最后一个节点为空
                    {
                        cout << endl;
                        return;
                    }
                    cout << pCur->_data << " ";
                }
                //子问题
                if (pCur)
                    pCur = pCur->_pRight;
            }
            cout << endl;
        }
        //递归后序遍历
        void _PostOrder(pNode pRoot)
        {
            if (pRoot)
            {
                _PostOrder(pRoot->_pLeft);
                _PostOrder(pRoot->_pRight);
                cout << pRoot->_data << " ";
            }
        }
        //递归后序遍历线索化
        void _PostOrderThreading(pNode pCur, pNode& prev)
        {
            if (pCur == NULL)
                return;
            _PostOrderThreading(pCur->_pLeft, prev);
            _PostOrderThreading(pCur->_pRight, prev);
            if (pCur->_pLeft == NULL)
            {
                pCur->_pLeft = prev;
                pCur->_leftTag = THREAD;
            }
            if (prev&&prev->_pRight == NULL)
            {
                prev->_pRight = pCur;
                prev->_rightTag = THREAD;
            }
            prev = pCur;
        }
    
    private:
        pNode _pRoot;
    };

**test.cpp** 测试代码

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include "BinaryTreeThd.h"
    
    
    void FunTest()
    {
        char str1[] = "ABD#G###CE##F";
        ThdBinaryTree<char> bt1(str1, strlen(str1), '#');
        bt1.InOrder();
        bt1.InOrderThreading();
        bt1.InOrderThdNoR();
    
        char str2[] = "ABD#G###CE##F";
        ThdBinaryTree<char> bt2(str2, strlen(str2), '#');
        bt2.PreOrder();
        bt2.PreOrderThreading();
        bt2.PreOrderThdNoR();
    }
    
    int main()
    {
        FunTest();
        system("pause");
        return 0;
    }

测试结果：  
![这里写图片描述][SouthEast 4]

[http_blog.csdn.net_qq_34021920_article_details_78698930]: http://blog.csdn.net/qq_34021920/article/details/78698930
[SouthEast]: /images/20220604/b3bfac753bbb4556a66eda291ffa2cee.png
[SouthEast 1]: /images/20220604/f4a72940e6e44e16bddded7bde30de39.png
[SouthEast 2]: /images/20220604/3238bff3f5cc463e8d485319cbd479b3.png
[SouthEast 3]: /images/20220604/94478015294d4ca5b1746b92fa2042cf.png
[http_blog.csdn.net_my_heart_article_details_52087948]: http://blog.csdn.net/my_heart_/article/details/52087948
[SouthEast 4]: /images/20220604/6c79fdecf86c406682e65deaa016045f.png