层次遍历算法笔试题

层次遍历算法

　　// 二叉树的数据结构

structBinaryTree

{

    int value;    // 不写模板了，暂时用整形代替节点的数据类型

    BinaryTree *left;

    BinaryTree *right;

};

BinaryTree*root;    // 已知二叉树的根节点

//层次遍历

voidLevel( const BinaryTree *root )

{

    Queue *buf = new Queue();    // 定义一个空队列，假设此队列的节点数据类型也是整形的

    BinaryTree t;                // 一个临时变量

    buf.push_back(root);         //令根节点入队

    while( buf.empty == false )    // 当队列不为空

    {

        p = buf.front();          // 取出队列的第一个元素

        cout<<p->value<<' ';

        if( p->left != NULL )     // 若左子树不空，则令其入队

        {

            q.push( p->left );

        }

        if( p->right != NULL )    // 若右子树不空，则令其入队

        {

            q.push( p->right );

        }      

        buf.pop();              // 遍历过的节点出队

    }   

    cout<<endl;

}