树节点定义

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x),left(NULL),right(NULL);
}

先序遍历（递归）

void visit(TreeNode*root)
{
    cout<< root->val << " ";
}
 void preoreder1(TreeNode* root)
 {
     if(root==NULL) return ;

     visit(root);  //根
     preorder1(root->left);  //左
     preorder1(root->right);  //右
 }

先序遍历（非递归）借用栈来实现非递归

void preoreder2(TreeNode*root)
{
    if(root==NULL) return ;

    stack<TreenNode*> s;  //注意 <>中的类型是 TreeNode*
    s.push(root);

    while(!s.empty() )
    {
        TreeNode*t = s.top();
        s.pop();
        cout<< t->val << ' ';
        if(root->right)  s.push(root->right);  //栈先进后出，所以这里让right先入栈
        if(root->left)   s.push(root->left);
    }
}

中序遍历（递归）

void visir(TreeNode*root)
{
    cout<< root->val << ' ' ;
}
void inorder1(TreeNode*root)
{
    if(root==NULL) return ;

    inorder1(root->left);  //左
    visit(root);           //根
    inorder1(root->right)  //右
}

中序遍历（非递归）

void inorder2(TreeNode* root)
{
    if(root==NULL) return ;

    stack<TreeNode*> s;
    TreeNode* t = root;

    while( t || !s.empty() )
    {

        while(t)   //先把左侧所有节点全部入栈 
        {
            s.push(t);
            t=t->left;
         }

        t = s.top();   
        s.pop();   

        cout<< t->val << ' ';

        t = t->right;  

    }
}

后续遍历（递归）

void postorder(TreeNode*root)
{
    if(root==NULL) return ;
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

后序（非递归）法一：

对中序非递归改进，让右节点输出后才输出根节点

void postorder2(TreeNode*root)
{
    stack<TreeNode*> s;
    TreeNode* t = root;
    TreeNOde* p = NULL;

    while(t || !s.empty() )
    {
        while(t)      //这个while循环里面等价于递归中postorder(root->left)
        {
            s.push(t);
            t = t->left;
        }             //把所有最左节点先全部入栈   


        t = s.top();

        //因为最左节点已经在栈中了， 只用考虑右子树的情况
        //输出一个节点的两种情况: 右子树没有 或者 右子树已经输出

        if(t->right==NULL || t->right==pre)   //  第二个t->right==pre, 说明t的右节点已经输出
        {
            s.pop();
            cout<< t->val <<' ' ;
            pre = t;
        }

        else t = t->right;


        后两行的if和 else 也可改为

        if(t->right&&t->right!=pre)    // 这里的if() 相当于post(root->right)
        {
            s.push(cur);
            pre=cur;
            cur=cur->right;
        }

        else cout<< cur->val << ' ';    //visi(root)
    }
}

后序（非递归）法二：

把先序遍历改为 根-右-左 得到的是后序的逆序，将逆序再逆一遍得到后序

void  postorder3(TreeNode*root)
{
    if(root==NULL) return ;
    stack<TreeNode*> s;  //开两个栈
    stack<TreeNode*> r;

    s.push(root);

    while( !s.empty() )
    {
        TreeNode* t = s.top();
        r.push(t);                    
        s.pop();

        if(t->left) s.push(t->left);  //非递归先序是先right入栈，这里改为left

        if(t->right) s.push(t->right);
    }

    while(r.empty() )
    {
        cout<< r.top() << ' ';
        r.pop();
    }

}

层次遍历

类似于图的bfs() 输出拓扑排序

void levelorder(TreeNode*root)
{
    if(root==NULL) return ;

    queue<TreeNode*> q;
    q.push(root);

    while( !q.empty() )
    {
        TreeNode* t = q.front():
        cout<< t->val << ' ' ;
        q.pop();

        if(t->left)  q.push(t->left);
        if(t-right)  q.push(t->right);
    }
}