【數據結構】線索化二叉樹中序線索化的遞歸寫法和非遞歸寫法

  二叉樹是一種非線性結構，遍歷二叉樹幾乎都是通過遞歸或者用棧輔助實現非遞歸的遍歷。用二叉樹作為存儲結構時，取到一個節點，只能獲取節點的左孩子和右孩子，不能直接得到節點的任一遍歷序列的前驅或者后繼。

  為了保存這種在遍歷中需要的信息，我們利用二叉樹中指向左右子樹的空指針來存放節點的前驅和后繼信息。所以引入了線索化二叉樹。下面我們講一下線索化二叉樹中序線索化的兩種實現方法：

  (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;
        }
        
    }