二叉树的遍历（前序、中序、后序）*（递归、非递归）共6种

二叉树结构定义

struct Node
{
    int data=0;
    Node* parent=NULL;
    Node* lchild=NULL;
    Node* rchild=NULL;
    Node(int n)
    {
        data=n;
    }
};
class BinarySearchTree
{
    Node* root;
public:
......
};

递归版

中序遍历（左、根、右）

void BinarySearchTree::inOrder(Node *p)
{ //中序遍历
    if (p->lchild)
        inOrder(p->lchild);
    cout << p->data << setw(4);
    if (p->rchild)
        inOrder(p->rchild);
    return;
}

前序遍历（根、左、右）

void BinarySearchTree::preOrder(Node *p)
{ //前序遍历
    cout << p->data << setw(4);
    if (p->lchild)
        inOrder(p->lchild);
    if (p->rchild)
        inOrder(p->rchild);
    return;
}

后序遍历（左、右、根）

void BinarySearchTree::postOrder(Node *p)
{ //后序遍历
    if (p->lchild)
        inOrder(p->lchild);
    if (p->rchild)
        inOrder(p->rchild);
    cout << p->data << setw(4);
    return;
}

非递归版

中序遍历（左、根、右）

void BinarySearchTree::nonRecursiveInOrder()
{
    /*非递归中序遍历
    对每一个根节点：
    1.向左下方遍历，遍历节点入栈，找到它的左子树最下边
    2.弹出栈顶并打印
    3.其右子树为新的根节点
    重复上述步骤直到栈空
    */
    Node *p = root;
    stack<Node *> stk;
    while (!stk.empty() p)
    {
        //遍历节点入栈
        while (p)
        {
            stk.push(p);
            p = p->lchild;
        }
        //弹出栈顶并打印
        if (!stk.empty())
        {
            p = stk.top();
            stk.pop();
            cout << p->data << setw(4);
            p = p->rchild;
            //进入右子树，开始新的一轮左子树遍历
            //若没有右子树，按循环条件，直接弹出下一个栈顶
        }
    }
    cout << endl;
    return;
}

前序遍历（根、左、右）

void BinarySearchTree::nonRecursivePreOrder()
{
    /*非递归前序遍历
    对每一个根节点：
    1.打印值
    2.向左下方遍历，遍历节点入栈，找到它的左子树最下边
    3.弹出栈顶
    4.其右子树为新的根节点
    重复上述步骤直到栈空
    */
    Node *p = root;
    stack<Node *> stk;
    while (!stk.empty() p)
    {
        //打印根节点的值，往左下遍历，遍历节点入栈
        while (p)
        {
            cout << p->data << setw(4);
            stk.push(p);
            p = p->lchild;
        }
        //弹出栈顶
        if (!stk.empty())
        {
            p = stk.top();
            stk.pop();
            p = p->rchild;
            //进入右子树，开始新的一轮左子树遍历
            //若没有右子树，按循环条件，直接弹出下一个栈顶
        }
    }
    cout << endl;
    return;
}

后序遍历（左、右、根）

void BinarySearchTree::nonRecursivePostOrder()
{
    /*非递归后序遍历
    对每一个根节点：
    1.向左下方遍历，遍历节点入栈，找到它的左子树最下边
    2.如果无右子树或者右子树刚被访问，直接打印根节点
      否则根节点再次入栈，先处理右子树
    3.其右子树为新的根节点
    重复上述步骤直到栈空
    */
    Node *p = root;
    Node *last = NULL; //标记上一个访问的节点
    stack<Node *> stk;
    //往左下遍历，遍历节点入栈
    while (p)
    {
        stk.push(p);
        p = p->lchild;
    }
    while (!stk.empty())
    {
        //弹出栈顶
        p = stk.top();
        stk.pop();
        //一个根节点被打印的条件：无右子树或者右子树刚被访问
        if (!p->rchild(last && last->data == p->rchild->data))
        {
            cout << p->data << setw(4);
            last = p; //修改上一个访问的节点
        }
        else
        {
            //进入该条件说明有右子树且尚未被访问
            //根节点再次入栈，先处理右子树
            stk.push(p);
            p = p->rchild;
            //往左下遍历，遍历节点入栈
            while (p)
            {
                stk.push(p);
                p = p->lchild;
            }
        }
    }
    cout << endl;
    return;
}