【数据结构】线索化二叉树中序线索化的递归写法和非递归写法

  二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。

  为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。所以引入了线索化二叉树。下面我们讲一下线索化二叉树中序线索化的两种实现方法：

  (1).递归实现中序线索化二叉树

  首先我们先看一下线索化二叉树的结构

enum PointerTag{ THREAD, LINK };

template<class T>
struct BinaryTreeThdNode
{
    BinaryTreeThdNode<T>* _left;
    BinaryTreeThdNode<T>* _right;
    PointerTag _leftTag;
    PointerTag _rightTag;
    T _data;

    BinaryTreeThdNode(const T& x)
        :_left(NULL)
        , _right(NULL)
        , _leftTag(LINK)
        , _rightTag(LINK)
        , _data(x)
    {}
};

用递归实现中序线索化二叉树，主要有两个需要注意到地方。

  首先我们先递归左。但是要考虑递归的条件是什么，只有当左右的标识符为THREAD的时候我们才能递归，否则会无限循环，因为左右为空的节点会指向前一个节点和后一个节点，从而引发无限递归。这个可以自己下去试验一下。

  另外一个需要注意的点就需要在自己分析问题的时候遇到的，就是当我们的右节点为空时，我们需要将右节点连接到上一层递归的节点上去。既然是递归下来的，那么上一层就相当于未来一样的，我们是无法预知的，那么怎么才能将右边连接到上一层的节点上去呢？

  嘿嘿，既然我们不能从现在去到未来，那么到未来的时候，我们再来做这件是嘛！我们先将这个时间节点记住，把他记作prev当我们到他的上一层节点的时候，先判断一下prev是不是为NULL的并且判断一下他是不是需要THREAD的(线索化的)。如果是，那么把保存的prev节点的右指向当前的节点就行了。

  然后再递归右，这样就完成了线索话二叉树。

template<class T>
class BinaryTreeThd
{
    typedef BinaryTreeThdNode<T> Node;
public:
    BinaryTreeThd(int* a, size_t size, const T& invalid)
    {
        size_t index = 0;
        _root = _CreateTreeThd(a, size, invalid,index);
    }
    
    Node* _CreateTreeThd(int* a, size_t size, const T& invalid, size_t& index)
    {
        Node* root = NULL;
        if (index < size && a[index] != invalid)
        {
            root = new Node(a[index]);
            root->_left = _CreateTreeThd(a, size, invalid, ++index);
            root->_right = _CreateTreeThd(a, size, invalid, ++index);
        }

        return root;
    }
    
//用递归实现线索化二叉树
    void InOrderThreading()
    {
        Node* prev = NULL;
        _InOrderThreading(_root,prev);
    }
    
    protected:
    //递归实现线索化二叉树
    void _InOrderThreading(Node* root,Node* prev)
    {
        if (root == NULL)
            return;

        if (root->_leftTag == LINK)
        _InOrderThreading(root->_left, prev);

        if (root->_left == NULL)
        {
            root->_left = prev;
            root->_leftTag = THREAD;
        }
        if (root->_right == NULL)
        {
            root->_rightTag = THREAD;
        }
        if (prev != NULL && prev->_rightTag == THREAD)
        {
            prev->_right = root;
        }

        prev = root;

        if (root->_rightTag == LINK)
        _InOrderThreading(root->_right, prev);
    }

  (2).用栈实现中序线索化二叉树

  用栈实现线索化二叉树就没有递归那么抽象了，思路跟递归的差不多，只是我们不再需要考虑上一层访问不到的问题了，因为栈取栈顶就能知道上一层的节点了。这种写法，自己去画图倒一下就能理解啦。这里我就只给出代码了。

/*用栈线索化二叉树*/
    void InOrderThreading()
    {
        stack<Node*> s;
        Node* prev = NULL;
        Node* cur = _root;
        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);
                cur = cur->_left;
            }
            cur = s.top();
            s.pop();
            if (cur->_left == NULL)
            {
                cur->_left = prev;
                cur->_leftTag = THREAD;
            }
            prev = cur;
            if (cur->_right == NULL && !s.empty())
            {
                cur->_right = s.top();
                cur->_rightTag = THREAD;
                cur = NULL;
            }

            else
            {
                cur = cur->_right;
            }
        }
    }

  另加两种打印方法：

  (1).递归打印

void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }  
    
    //递归打印线索化二叉树
    void _InOrder(Node* root)
    {
        if (root == NULL)
            return;
        if (root->_leftTag == LINK)
            _InOrder(root->_left);

        cout << root->_data << " ";
        if (root->_rightTag == LINK)
        {
            _InOrder(root->_right);
        }
    
    }

  (2).用栈打印

void InOrder()
    {
        if (_root == NULL)
            return;
        Node* cur = _root;
        while (cur)
        {
            while (cur->_left)
            {
                cur = cur->_left;
            }
            cut << cur->_data << " ";
            if (cur->_rightTag == THREAD)
            {
                cout << cur->_right->_data << " ";
                cur = cur->_right;
            }
            else if (cur->_right == LINK)
            {
                
            }
        }
    }

  (3).循环打印

前面两种的打印方法没有体现线索化二叉树的优势，下面这种打印方法就充分体现了线索二叉树的优势了。但是值得注意的是我把左后一个节点的右也线索化成THREAD类型了，所以加上了return。

void InOrderM()
    {
        Node* cur = _root;
        while (cur)
        {
            while (cur->_leftTag == LINK)
            cur = cur->_left;

            cout << cur->_data << " ";

            while(cur->_rightTag == THREAD)
            {
                cur = cur->_right;
                if (cur == NULL)
                {
                    cout << endl;
                    return;
                }
                cout << cur->_data << " ";
            }

            cur = cur->_right;
        }
        
    }