层次遍历二叉树

1、若树非空，访问根结点。

2、若第1，…i(i≥1)层结点已被访问，且第i+1层结点尚未访问，则从左到右依次访问第i+1层。
层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。

为保证是按层次遍历，必须设置一个队列，初始化时为空。

设T是指向根结点的指针变量，层次遍历非递归算法是：

若二叉树为空，则返回；否则，令p=T，p入队；

⑴ 队首元素出队到p；

⑵访问p所指向的结点； 

 ⑶将p所指向的结点的左、右子结点依次入队。直到队空为止。


层序遍历

二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 

#include<iostream>
#include<queue>
using namespace std;
typedef struct Bitree
{
	int data;
	struct Bitree *Lchild,*Rchild;
}BitreeNode,*LinkBitree;
const int STOP_INPUT=0;
LinkBitree CreatBitree();
void LevelOrderTraverse(LinkBitree);

int main()
{
	LinkBitree BitreeHead;
	cout<<"请输入根结点的值：\n";
	BitreeHead=CreatBitree();
	LevelOrderTraverse(BitreeHead);
	return 0;
}

LinkBitree CreatBitree()
{
	int e_data;
	LinkBitree BitreeHead;
	cin>>e_data;
	if(e_data!=STOP_INPUT)
	{
		BitreeHead=new BitreeNode;
		if(BitreeHead==NULL)
		{
			cout<<"\nError!!\n";
		}
		else
		{
			BitreeHead->data=e_data;
			cout<<"请输入结点"<<BitreeHead->data<<"的左孩子结点的值：\n";
	        BitreeHead->Lchild=CreatBitree();
	        cout<<"请输入结点"<<BitreeHead->data<<"的右孩子结点的值：\n";
            BitreeHead->Rchild=CreatBitree();
		}
	}
	else
	{
		BitreeHead=NULL;
	}
	return BitreeHead;
}
void LevelOrderTraverse(LinkBitree BitreeHead)
{
	queue<LinkBitree> Q;
	if(BitreeHead!=NULL)
	{
		Q.push(BitreeHead);//根节点入队列
    }
	while(!Q.empty())//队列不为空
	{
		cout<<Q.front()->data<<"  "; //输出作为遍历操作
		//Q.pop();
		if(Q.front()->Lchild!=NULL)//左孩子不为空，入队列
		{
			Q.push(Q.front()->Lchild);
        }
		if(Q.front()->Rchild!=NULL)//右孩子不为空，入队列
		{
			Q.push(Q.front()->Rchild);
		}
		Q.pop();
	}
}
/*******************************
输入二叉树形态如下：
       1
    2       5
 3    4   0  0
0 0  0 0  

********************************/
/*********************************
运行结果：
请输入根结点的值：
1
请输入结点1的左孩子结点的值：
2
请输入结点2的左孩子结点的值：
3
请输入结点3的左孩子结点的值：
0
请输入结点3的右孩子结点的值：
0
请输入结点2的右孩子结点的值：
4
请输入结点4的左孩子结点的值：
0
请输入结点4的右孩子结点的值：
0
请输入结点1的右孩子结点的值：
5
请输入结点5的左孩子结点的值：
0
请输入结点5的右孩子结点的值：
0
1  2  5  3  4
************************************/
#include<iostream>

#include<queue>

using namespace std;

typedef struct Bitree

{

    int data;

    struct Bitree *Lchild,*Rchild;

}BitreeNode,*LinkBitree;

const int STOP_INPUT=0;

LinkBitree CreatBitree();

void LevelOrderTraverse(LinkBitree);


int main()

{

    LinkBitree BitreeHead;

    cout<<"请输入根结点的值：\n";

    BitreeHead=CreatBitree();

    LevelOrderTraverse(BitreeHead);

    return 0;

}


LinkBitree CreatBitree()

{

    int e_data;

    LinkBitree BitreeHead;

    cin>>e_data;

    if(e_data!=STOP_INPUT)

    {

        BitreeHead=new BitreeNode;

        if(BitreeHead==NULL)

        {

            cout<<"\nError!!\n";

        }

        else

        {

            BitreeHead->data=e_data;

            cout<<"请输入结点"<<BitreeHead->data<<"的左孩子结点的值：\n";

            BitreeHead->Lchild=CreatBitree();

            cout<<"请输入结点"<<BitreeHead->data<<"的右孩子结点的值：\n";

            BitreeHead->Rchild=CreatBitree();

        }

    }

    else

    {

        BitreeHead=NULL;

    }

    return BitreeHead;

}

void LevelOrderTraverse(LinkBitree BitreeHead)

{

    queue<LinkBitree> Q;

    if(BitreeHead!=NULL)

    {

        Q.push(BitreeHead);//根节点入队列

    }

    while(!Q.empty())//队列不为空

    {

        cout<<Q.front()->data<<"  "; //输出作为遍历操作

        //Q.pop();

        if(Q.front()->Lchild!=NULL)//左孩子不为空，入队列

        {

            Q.push(Q.front()->Lchild);

        }

        if(Q.front()->Rchild!=NULL)//右孩子不为空，入队列

        {

            Q.push(Q.front()->Rchild);

        }

        Q.pop();

    }

}

/*******************************

输入二叉树形态如下：

       1

    2       5

 3    4   0  0

0 0  0 0  


********************************/

/*********************************

运行结果：

请输入根结点的值：

1

请输入结点1的左孩子结点的值：

2

请输入结点2的左孩子结点的值：

3

请输入结点3的左孩子结点的值：

0

请输入结点3的右孩子结点的值：

0

请输入结点2的右孩子结点的值：

4

请输入结点4的左孩子结点的值：

0

请输入结点4的右孩子结点的值：

0

请输入结点1的右孩子结点的值：

5

请输入结点5的左孩子结点的值：

0

请输入结点5的右孩子结点的值：

0

1  2  5  3  4

************************************/

思路很简单。通过队列，先将头结点放入队列，再遍历每个节点的左节点和右节点。
import java.util.ArrayList;
import java.util.LinkedList;
/**
* 遍历层次二叉树
*
* @author chenjunxu
*
*/
public class Main {
public static void main(String[] args) {
// 队列
LinkedList queue = new LinkedList();
// 模拟数据
TreeNode root = new TreeNode("1");
TreeNode root2 = new TreeNode("2");
root.leftTree = root2;
// 将头节点加入队列
queue.add(root);
TreeNode temp = null;
// 收集结果
ArrayList resultArray = new ArrayList();
// 通过while循环，将队列内容全部取出
while (!queue.isEmpty()) {
// 取出队列第一个节点
temp = queue.poll();
// 该节点若有左子树，则添加至队列尾部
if (temp.leftTree != null) {
queue.add(temp.leftTree);
}
// 该节点若有右子树，则添加至队列尾部
if (temp.rightTree != null) {
queue.add(temp.rightTree);
}
// 保存结果
resultArray.add(temp.val);
}
// 输出结果
for (String str : resultArray) {
System.out.println(str);
}
}
}
/**
* 二叉树节点
*
* @author chenjunxu
*
*/
class TreeNode {
public String val = "root";
public TreeNode leftTree = null;
public TreeNode rightTree = null;
public TreeNode(String val) {
this.val = val;
}
}

1.递归的方法

　　二叉树本身就带有递归属性，通常我们可以用递归方法解决。假设要访问第k层节点，那么其实可以转皇城分别访问“以该二叉树根节点的左右子节点为根节点的两棵子树”中层次为k-1的节点。此方法需要求出二叉树的深度，其实可以直接访问到二叉树某一层次失败的时候返回就可以了。

　　这个方法的问题是递归调用，效率较低。而且对每一层的访问都需要从根节点开始，效率极差。

　　最坏的情况下（不平衡树）时间复杂度为O(n^2),空间复杂度O(1)
//输出以root为根节点中的第level层中的所有节点（从左至右），成功返回1
//失败返回0
//root为二叉树根节点
//level为层次数，其中根节点为第0层
int PrintNodeAtLevel(TreeNode *root, int level) {
    if (!root || level < 0) return 0;
    if (level == 0){
        cout<<root->val;
        return 1;
    }

    return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
}

//层次遍历二叉树
//root，二叉树的根节点
void LevelOrder(TreeNode *root) {
    for (int level = 0; ; level++) {
        if (!PrintNodeAtLevel(root, level)) 
            break;
        cout<<endl;
    }
}

2. 使用数组和两个游标的方法

　　在访问k层的时候，我们只需要知道k-1层的信息就足够了，所以在访问第k层的时候，要是能够知道k-1层的节点信息，就不再需要从根节点开始遍历了。

　　根据上述分析，可以从根节点出发，依次将每一层的根节点从左往右压入一个数组，并并用一个游标cur记录当前访问的节点，另一个游标last指示当前层次的最后一个节点的下一个位置，以cur===last作为当前层次访问结束的条件，在访问某一层的同时将该层的所有节点的子节点压入数组，在访问完某一层之后，检查是否还有新的层次可以访问，直到检查完所有的层次（不再有新的节点可以访问）

　　这种方法需要一个vector一直存储所有节点，空间效率较差。

　　时间复杂度为O(n),空间复杂度为O(n)
void LevelOrder(TreeNode *root) {
    if (root == NULL) return;
    vector<TreeNode *> vec; //这里使用stl中的vector代替数组，可利用到
                            //其动态扩展的属性
    vec.push_back(root);
    int cur = 0, last = vec.size();
    while (cur < vec.size()) {
        last = vec.size();

        while (cur < last) {
            cout<<vec[cur]->val;
            if (vec[cur]->left) 
                vec.push_back(vec[cur]->left);
            if(vec[cur]->right)
                vec.push_back(vec[cur]->right);
            ++cur;
        }
        cout<<endl;
    }
}
以上两种方法是书上给出的方法,其实二叉树分层遍历其实就是图的广度优先遍历的一个特殊形式，只要将其稍加修改就可以了。(树是图的一种特殊形式)
第三种方法：通过一个队列进行分层遍历

public void levelorder(BinaryNode root)
{
	linkedList<BinaryNode> que = new LinkedList<BinaryNode>();
	while(root!=null)
	{
		System.out.print(p.data);
		if(p.left!=null)
			que.add(p.left);
		if(p.right!=null)
			que.add(p.right);
		p=que.poll();
	}
}

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> temp;
            auto size=q.size();
            while(size--)
            {
                TreeNode* node=q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
                temp.push_back(node->val);
            }
            res.push_back(temp);
        }
        return res; 
    }
};