二叉树的遍历的相关变型

说明：代码使用codeblocks编译，C++实现，个人编写，如有错误，还望指正。

fengjingtu

1、按照层次打印二叉树，并使用换行符分隔

使用last指向本层的最后一个，nlast=root指向下一层最后一个，只有在上一层全部出队列之后才能确认该层后面不会有别的值了。

#include <iostream>
#include <stdlib.h>
#include <stack>
#include <queue>


using namespace std;

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int v):val(v),left(NULL),right(NULL){
    }
};
/*
构建这样一棵二叉树：

        1
       / \
      2   3
     /\   /\
    4  5  6 7
    /   \    \ 
    8    9    0
                \ 
                 1

*/
void BuildTree(TreeNode* &root)
{
    root=new TreeNode(1);
    root->left=new TreeNode(2);
    root->right=new TreeNode(3);
    root->left->left=new TreeNode(4);
    root->left->right=new TreeNode(5);
    root->right->left=new TreeNode(6);
    root->right->right=new TreeNode(7);
    root->left->left->left=new TreeNode(8);
    root->left->right->right=new TreeNode(9);
    root->right->right->right=new TreeNode(0);
    root->right->right->right->right=new TreeNode(1);

    return ;
}
void wideEnterPrint(TreeNode*root)
{
    if(root==NULL)
        return ;
    queue<TreeNode*>q;
    q.push(root);
    TreeNode*cur;
    TreeNode*last=root;//指向本层的最后一个
    TreeNode*nlast=root;//指向下一层最后一个，
    while(!q.empty())
    {
        cur=q.front();
        if(cur)
            cout<<cur->val<<" ";
        q.pop();
        if(cur->left)
        {
            q.push(cur->left);
            nlast=(cur->left);
        }
        if(cur->right)
        {
            q.push(cur->right);
            nlast=(cur->right);
        }
        if(cur==last)
        {
            cout<<endl;
            last=nlast;
        }
    }
    return ;

}

int main()
{
    TreeNode *root;
    //构建二叉树
    BuildTree(root);
    wideEnterPrint(root);
    //销毁二叉树
    DestroyTree(root);
    return 0;
}