【數(shù)據(jù)結(jié)構(gòu)】線索化二叉樹中序線索化的遞歸寫法和非遞歸寫法

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

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

  (1).遞歸實現(xiàn)中序線索化二叉樹

  首先我們先看一下線索化二叉樹的結(jié)構(gòu)

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)
    {}
};

用遞歸實現(xiàn)中序線索化二叉樹，主要有兩個需要注意到地方。

  首先我們先遞歸左。但是要考慮遞歸的條件是什么，只有當(dāng)左右的標(biāo)識符為THREAD的時候我們才能遞歸，否則會無限循環(huán)，因為左右為空的節(jié)點會指向前一個節(jié)點和后一個節(jié)點，從而引發(fā)無限遞歸。這個可以自己下去試驗一下。

  另外一個需要注意的點就需要在自己分析問題的時候遇到的，就是當(dāng)我們的右節(jié)點為空時，我們需要將右節(jié)點連接到上一層遞歸的節(jié)點上去。既然是遞歸下來的，那么上一層就相當(dāng)于未來一樣的，我們是無法預(yù)知的，那么怎么才能將右邊連接到上一層的節(jié)點上去呢？

  嘿嘿，既然我們不能從現(xiàn)在去到未來，那么到未來的時候，我們再來做這件是嘛！我們先將這個時間節(jié)點記住，把他記作prev當(dāng)我們到他的上一層節(jié)點的時候，先判斷一下prev是不是為NULL的并且判斷一下他是不是需要THREAD的(線索化的)。如果是，那么把保存的prev節(jié)點的右指向當(dāng)前的節(jié)點就行了。

  然后再遞歸右，這樣就完成了線索話二叉樹。

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;
    }
    
//用遞歸實現(xiàn)線索化二叉樹
    void InOrderThreading()
    {
        Node* prev = NULL;
        _InOrderThreading(_root,prev);
    }
    
    protected:
    //遞歸實現(xiàn)線索化二叉樹
    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).用棧實現(xiàn)中序線索化二叉樹

  用棧實現(xiàn)線索化二叉樹就沒有遞歸那么抽象了，思路跟遞歸的差不多，只是我們不再需要考慮上一層訪問不到的問題了，因為棧取棧頂就能知道上一層的節(jié)點了。這種寫法，自己去畫圖倒一下就能理解啦。這里我就只給出代碼了。

/*用棧線索化二叉樹*/
    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).循環(huán)打印

前面兩種的打印方法沒有體現(xiàn)線索化二叉樹的優(yōu)勢，下面這種打印方法就充分體現(xiàn)了線索二叉樹的優(yōu)勢了。但是值得注意的是我把左后一個節(jié)點的右也線索化成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;
        }
        
    }