从上往下打印二叉树——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<
运行程序：
《完》
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
            

            当前标题：从上往下打印二叉树——23-创新互联            

            URL链接：http://cqcxhl.cn/article/dspsdo.html