从上往下打印二叉树——23

   从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。例如如下二叉树打印出的结果为1、2、3、4、5、6、7、8、9。

创新互联是一家集网站建设,信阳企业网站建设,信阳品牌网站建设,网站定制,信阳网站建设报价,网络营销,网络优化,信阳网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

    上面所说的也就是二叉树的层序遍历，对于层序遍历来说，首先访问的肯定是根节点，然后是其左右结点，之后就是左子树的左右结点和右子树的左右结点，依次往下，如果使用像前中后序遍历那样按照左右结点去递归打印的话肯定是不行的，因为并不能一直先访问某个左结点或者右结点，而是应该左右交叉访问；

    上面的二叉树中，打印的顺序是1、2、3、4、5、6、7、8、9，可以想到按照队列的方式依次将其放入其中，而先进先出，得到的也就是打印的顺序，至于如何存放，可以先将根结点放入其中，拿到队首结点，如果队首结点的左右结点不为NULL，就依次放入队列中，然后将队首元素pop出，再循环取队首元素进行判断放入......直至遍历完二叉树且队列为空为止；

程序设计如下：

#include 
#include 
#include 
using namespace std;

struct BinaryTreeNode//二叉树结点结构体
{
    int _val;
    BinaryTreeNode *_Lnode;
    BinaryTreeNode *_Rnode;

    BinaryTreeNode(int val)//构造函数
        :_val(val)
         ,_Lnode(NULL)
         ,_Rnode(NULL)
    {}
};

BinaryTreeNode* _Create(int *arr, size_t& index, size_t size)//前序方式创建二叉树
{
    if((index < size) && (arr[index] != '#'))
    {
        BinaryTreeNode *root = new BinaryTreeNode(arr[index]);
        root->_Lnode = _Create(arr, ++index, size);
        root->_Rnode = _Create(arr, ++index, size);
        return root;
    }
    else
        return NULL;
}

BinaryTreeNode* CreateBinaryTree(int *arr, size_t size)
{
    assert(arr && size);

    size_t index = 0;
    return _Create(arr, index, size);
}

void DestoryBinaryTree(BinaryTreeNode* root)//销毁二叉树
{
    if(root != NULL)
    {
        DestoryBinaryTree(root->_Lnode);
        DestoryBinaryTree(root->_Rnode);
        delete root;
        root = NULL;
    }
}

void LevelOrderBinaryTree(BinaryTreeNode *root)//层序遍历二叉树
{
    assert(root);
    queue q;

    q.push(root);
    while(!q.empty())
    {
        if(q.front()->_Lnode != NULL)
            q.push(q.front()->_Lnode);
        if(q.front()->_Rnode != NULL)
            q.push(q.front()->_Rnode);

        cout<_val<<" ";
        q.pop();
    }
    cout<_val<<" ";
        PrevOrder(root->_Lnode);
        PrevOrder(root->_Rnode);
    }
}

int main()
{
    int arr[] = {1,2,4,'#','#',5,8,'#','#','#',3,6,'#','#',7,'#',9,'#','#'};
    BinaryTreeNode *root = CreateBinaryTree(arr, sizeof(arr)/sizeof(arr[0]));
    cout<<"PrevOrder: ";
    PrevOrder(root);
    cout<
运行程序：
《完》
            
            
                        

            当前标题：从上往下打印二叉树——23            

            文章来源：http://cqcxhl.cn/article/ihhodc.html