#include <iostream>#include <fstream>#include <string>#include <stack>using std::cout;using std::endl;using std::cin;using std::ifstream;using std::stack;class BTree{private:    struct Node    {        Node* lChild;        char data;        Node* rChild;    };    Node* m_pRoot;        //pointer to tree root    void addNode(ifstream& fin, Node** ppNode);    void showNode(Node* pNode);        //递归中序遍历    void switchLRChild(Node* pNode);public:    explicit BTree(void) { m_pRoot = nullptr;}    void create(void);    void show(void);        //这是中序遍历    void switchLR(void);    void switchLR2(void);        //非递归实现交换节点的左右孩子    void preOrder(void);        //写着玩的非递归先序遍历    void inOrder(void);        //写着玩的非递归中序遍历    void aftOrder(void);        //写着玩的非递归后序遍历};void BTree::create(void){    ifstream fin("src.txt");    if(!fin)        cout<<"can not open the file!\n";    addNode(fin, &m_pRoot);}void BTree::addNode(ifstream& fin, Node** ppNode){    /* 手工读取    cout<<"Input node‘s value, blank to end:";    char ch;    cin.get(ch);    if(ch == ‘\n‘)        return;    while(cin.get() != ‘\n‘)        continue;    (*ppNode) = new Node;    (*ppNode)->data = http://www.mamicode.com/ch;"add left child:"<<endl;    addNode(&((*ppNode)->lChild));    cout<<"add right child:"<<endl;    addNode(&((*ppNode)->rChild));*/    //文件读取    std::string temp;    getline(fin, temp);        //这个函数以换行为标志读取一行，但是会丢弃换行符    if(temp.empty())        return;    (*ppNode) = new Node;    (*ppNode)->data = http://www.mamicode.com/temp[0];    (*ppNode)->lChild = nullptr;    (*ppNode)->rChild = nullptr;    addNode(fin, &((*ppNode)->lChild));    addNode(fin, &((*ppNode)->rChild));}void BTree::show(void){    if(m_pRoot)    {        showNode(m_pRoot);        cout<<endl;    }    else    {        cout<<"Empty tree!"<<endl;    }}void BTree::showNode(Node* pNode){    if (pNode)    {        showNode(pNode->lChild);        cout<<pNode->data<<" ";        showNode(pNode->rChild);    }    else    {        return;    }}void BTree::switchLR(void){    switchLRChild(m_pRoot);}void BTree::switchLRChild(Node* pNode){    if (pNode && (pNode->lChild != nullptr || pNode->rChild != nullptr))    {        Node* temp = pNode->lChild;        pNode->lChild = pNode->rChild;        pNode->rChild = temp;        switchLRChild(pNode->lChild);        switchLRChild(pNode->rChild);    }}void BTree::switchLR2(void){    struct BNode    {        Node* pToNode;        bool isFirst;    };    BNode p = {m_pRoot, true};    stack<BNode> myStack;    while(p.pToNode || !myStack.empty())    {        while(p.pToNode)        {            myStack.push(p);            p.pToNode = p.pToNode->lChild;            p.isFirst = true;    //重置        }        p = myStack.top();        myStack.pop();        if (p.isFirst)        {            p.isFirst = false;            myStack.push(p);            p.pToNode = p.pToNode->rChild;            p.isFirst = true;        }         else        //节点第二次在栈顶了，那么此时交换它的左右节点        {            Node* temp = p.pToNode->lChild;            p.pToNode->lChild = p.pToNode->rChild;            p.pToNode->rChild = temp;            p.pToNode = nullptr;        }    }    /*    这个和非递归的后序遍历的原理一样：先直接沿着左侧一路向下，把遇到的每个节点都入栈，直到没有了。    然后呢对于栈顶的节点，如果它是第一个出现在栈顶，那么还没有对它的右子树进行处理，所以切换到它的右子树    进行同样的处理。当它的右子树处理完了之后这个节点再次出现在栈顶，这个时候就可以交换它的左右子树了，    并且它的左右子树都已经完成了交换，这不就是递归吗？只不过是循环实现的就是啦。    */}void BTree::preOrder(void){    stack<Node*> myStack;    Node* p = m_pRoot;    while(p != nullptr || !myStack.empty())    {        while(p != nullptr)        //写的时候先写内层循环，再写外层循环        {            cout<<p->data<<" ";        //先访问数据            myStack.push(p);        //指针入栈            p = p->lChild;        //指向左孩子        }        if (!myStack.empty())    //到这里指针p肯定是空了        {            p = myStack.top();        //节点出现在栈顶时，此节点已经访问过，并且其左孩子也被访问过，只有其右孩子还没有            myStack.pop();            p = p->rChild;        }    }    cout<<endl;}void BTree::inOrder(void){    stack<Node*> myStack;    Node* p = m_pRoot;    while(p || !myStack.empty())    //外层循环相当于实现了递归的作用    {        while(p)        {            myStack.push(p);            p = p->lChild;        }        if (!myStack.empty())        {            p = myStack.top();        //节点出现在栈顶，则其左孩子已经被访问过，自己和右孩子都没有被访问过            myStack.pop();            cout<<p->data<<" ";        //访问数据            p = p->rChild;        //对右子树也用同样的方法，这不是递归的思想吗？        }    }    cout<<endl;}void BTree::aftOrder(void){    struct BNode        //这个结构体只多了一个是否是第一次访问的标志    {        Node* pToNode;        bool isFirst;    };    BNode p;    p.pToNode = m_pRoot;    p.isFirst = true;    stack<BNode> myStack;    while(p.pToNode || !myStack.empty())    {        while(p.pToNode)        {            myStack.push(p);            p.pToNode = p.pToNode->lChild;            p.isFirst = true;    //注意这里每次切换的时候都要设置true或false，因为就那么一个变量，虽然放到栈里面都有true或false        }        if (!myStack.empty())        {            p = myStack.top();            myStack.pop();            if (p.isFirst)        //是第一次出现在栈顶            {                p.isFirst = false;                myStack.push(p);                p.pToNode = p.pToNode->rChild;                p.isFirst = true;            }            else     //第二次出现在栈顶了            {                cout<<p.pToNode->data<<" ";                p.pToNode = nullptr;        //这里其实就是让程序直接运行到下次出栈            }        }    }    cout<<endl;    /*    非递归后序遍历：先一直沿着左孩子向下，并把指向节点的指针入栈，直到不能继续向下了。    这个时候对于栈顶的节点，让它出栈，但我们还不能访问它，如果这个时候访问了那不就是中序遍历了吗？    也就是一个节点第一次出现在栈顶时不能访问它，这时要继续对它的右子树进行访问。    当结束了对它的右子树访问时，这个时候这个节点又出现在了栈的顶端，这个时候才可以访问它，这才是后序遍历。    */}int main(void){    BTree myT;    myT.create();    myT.show();    //myT.preOrder();//    myT.switchLR();//    myT.show();    //myT.inOrder();    //myT.aftOrder();    myT.switchLR2();    myT.show();    cin.get();}

 1 C 2 T 3 G 4 V 5  6  7  8 W 9 10 11 M12 S13 14 15 N