线索二叉树前、中、后续遍历

#include <stack>
#pragma once

enum PointerTag{THREAD,LINK};

template<class T>
struct BinaryTreeNode_Thd
{
    BinaryTreeNode_Thd(const T& data)
        :_data(data)
        ,_left(NULL)
        ,_right(NULL)
        ,_leftTag(LINK)
        ,_rightTag(LINK)
    {}
    T _data;
    BinaryTreeNode_Thd<T> *_left;
    BinaryTreeNode_Thd<T> *_right;
    PointerTag _leftTag;
    PointerTag _rightTag;

};
template<class T>
class BinaryTree_Thd
{
public:
    BinaryTree_Thd()
        :_root(NULL)
    {}
    BinaryTree_Thd(const T *a,const size_t size)
    {
        int index = 0;
        _root = _CreatTree(a,size,index);
    }
    void PrevOrder_Threading()
    {
        BinaryTreeNode_Thd<T> *prev = NULL;
        _PrevOrder_Threading(_root,prev);
    }
    void InOrder_Threading()
    {
        BinaryTreeNode_Thd<T> *prev = NULL;
        _InOrder_Threading(_root,prev);
    }
    void PostOrder_Threading()
    {
        BinaryTreeNode_Thd<T> *prev = NULL;
        _PostOrder_Threading(_root,prev);
    }
    void InOrder()
    {
        if(_root == NULL)
        {
            return;
        }
        BinaryTreeNode_Thd<T> *cur = _root;
        while (cur)
        {
            while (cur->_left != NULL && cur->_leftTag==LINK)
            {
                cur = cur->_left;
            }
            cout << cur->_data << " ";
            while(cur->_rightTag == THREAD)//用while支持连跳
            {
                cur = cur->_right;
                cout << cur->_data << " ";
            }
            cur = cur->_right;
        }
    }
    void PreOrder()
    {
        if(_root == NULL)
        {
            return;
        }
        BinaryTreeNode_Thd<T> *cur = _root;
        while(cur)
        {
            while (cur->_left != NULL && cur->_leftTag==LINK)
            {
                cout<<cur->_data<<" ";
                cur = cur->_left;
            }
            cout<<cur->_data<<" ";

            cur = cur->_right;
        }
    }
    void PostOrder()
    {
        BinaryTreeNode_Thd<T> *cur = _root;
        stack<BinaryTreeNode_Thd<T> *> s;
        while(cur)
        {
            while (cur->_right != NULL && cur->_rightTag==LINK)
            {
                s.push(cur);
                cur = cur->_right;
            }
            s.push(cur);
            cur = cur->_left;
        }
        while(!s.empty())
        {
            BinaryTreeNode_Thd<T> *tmp = s.top();
            s.pop();
            cout<<tmp->_data<<" ";
        }
    }
protected:
    BinaryTreeNode_Thd<T>* _CreatTree(const int *a,size_t size,int &index)
    {
        BinaryTreeNode_Thd<T> *root = NULL;
        if(index < size && a[index] != '#')
        {
            root = new BinaryTreeNode_Thd<T>(a[index]);
            root->_left = _CreatTree(a,size,++index);
            root->_right = _CreatTree(a,size,++index);
        }
        return root;
    }
    void _PostOrder_Threading(BinaryTreeNode_Thd<T> *cur,BinaryTreeNode_Thd<T> * &prev)
    {
        if(cur == NULL)
        {
            return;
        }
        _PostOrder_Threading(cur->_left,prev);
        _PostOrder_Threading(cur->_right,prev);
        if(!cur->_left)
        {
            cur->_leftTag = THREAD;
            cur->_left = prev;
        }
        if(prev && !prev->_right)
        {
            prev->_rightTag = THREAD;
            prev->_right = cur;
        }
        prev = cur;
    }
    void _PrevOrder_Threading(BinaryTreeNode_Thd<T> *cur,BinaryTreeNode_Thd<T> * &prev)
    {
        if(cur == NULL)
        {
            return;
        }
        if(!cur->_left)
        {
            cur->_leftTag = THREAD;
            cur->_left = prev;
        }
        if(prev && !prev->_right)
        {
            prev->_rightTag = THREAD;
            prev->_right = cur;
        }
        prev = cur;

        if(cur->_leftTag == LINK)
        {
            _PrevOrder_Threading(cur->_left,prev);
        }
        if(cur->_rightTag == LINK)
        {
            _PrevOrder_Threading(cur->_right,prev);
        }
    }
    void _InOrder_Threading(BinaryTreeNode_Thd<T> *cur,BinaryTreeNode_Thd<T> *&prev)//记得加引用
    {
        if(cur == NULL)
        {
            return;
        }
        _InOrder_Threading(cur->_left,prev);
        if(!cur->_left)
        {
            cur->_leftTag = THREAD;
            cur->_left = prev;
        }
        if(prev && !prev->_right)
        {
            prev->_rightTag = THREAD;
            prev->_right = cur;
        }
        prev = cur;
        _InOrder_Threading(cur->_right,prev);
    }
protected:
    BinaryTreeNode_Thd<T> *_root;
};

测试：

#include <iostream>
#include "BinaryTree_ThR.h"
using namespace std;

void test()
{
    int a[10] = {1,2,3,'#','#',4,'#','#',5,6};
    BinaryTree_Thd<int> t1(a,10);
//     t1.InOrder_Threading();
//     t1.InOrder();

//    t1.PrevOrder_Threading();
//    t1.PreOrder();

    t1.PostOrder_Threading();
    t1.PostOrder();
}
int main()
{
    test();
    return 0;
}