核心思想：二叉树层次i的结点遍历结束后，层次i+1的结点已全部进队，此时队列的元素个数即为层次 i + 1的宽度
难点：如何判断二叉树层次i已经遍历结束呢？可采用一个变量width记录层次i的结点个数，每出队一个元素，变量width减一，当width == 0时，表明层次i遍历完毕。
二叉树层次i遍历结束后（width == 0），只需要用当前队列的元素个数来更新width，表示二叉树层次i + 1的结点个数
int BTWidth(BTNode *b)
{
	if(b == NULL)   //为空树，返回宽度为0
		return 0;

	int width, max;
	int i = 1, max_i; //初始化二叉树层次i，最大宽度所在层次max_i
	BTNode * p;
	SqQueue * qu;       
	InitQueue(qu);     //初始化层次遍历需要借助的队列
	enQueue(qu, b);    //树不为空，根节点进队
	width = 1;         // 宽度置为1
	max = width;       //最大宽度为1
	max_i = i;         //最大宽度所在层次

	while(!QueueEmpty(qu))   //队列为空，表明二叉树遍历完毕，退出循环
	{
		deQueue(qu, p);      //节点出队，赋给p
		width --;            //出队一次，width减1
		if(p -> lchild != NULL) //出队节点的左孩子进队
			enQueue(qu, p -> lchild);
		if(p -> rchild != NULL)
			enQueue(qu, p -> rchild); //出队节点的右孩子出队

		if(width == 0)  //width == 0，表示当前层次i所有节点已遍历完毕
		{               //此时队列元素个数即为下一层次 i + 1 的节点个数
			width = (qu->rear - qu->front + MaxSize) % MaxSize;  //更新宽度
			i++;     //层次变为下一层 i + 1
			if(width > max)  //如果层次 i + 1 宽度 > max
			{
				max = width;  //更新max
				max_i = i;   //并记录最大宽度所在层次
			}
		}
	}

	printf("二叉树层次 %d 的宽度最大\n", max_i);
	return max;
}

	

难度(medium)
题目描述：
求给定的二叉树的后序遍历。例如：给定的二叉树为{1,#,2,3}
1↵    ↵     2↵    /↵   3↵
返回[3,2,1]
思路：
根据后序遍历的规则，左——右——根，那么可以考虑先找到左子节点的最底层的左子节点，然后进行保存，同样的，再找到左子节点的最底层的左子节点进行保存，再找到根节点保存，然后按照这种顺序进行输出，利用递归实现树的所有节点遍历。
代码：
import java.util.ArrayList;    public static ArrayList<Integer> postOrder(TreeNode root) {        //如果根不为空        if (root != null) {            //递归找到此次根下最底层的左子节点            ArrayList<Integer> left = postOrder(root.left);            //递归找到此次根下最底层的右子节点            ArrayList<Integer> right = postOrder(root.right);            ArrayList<Integer> result = new ArrayList<>();            //按规则顺序添加            result.addAll(left);            result.addAll(right);            result.add(root.data);            //返回添加的一种结果，最后将几种集中结果凑在一起就是完整的后序遍历            return result;        }        //如果根为空        return new ArrayList<>();    }}
还有一种方法时非递归形式，用栈来解决，也可以。
封面来源于网络，侵删
	

例6-5
假设二叉树采用二叉链表存储结构存储，设计一个算法，求出该二叉树的宽度（拥有节点数最多的那一层的节点个数）
思路： 要求结点数最多的一层，可以分别求出每层的节点数，然后从中选取最多的，要达到这个目的，需要明白两件事：

第一：对于非空树，树根所在的层位第一层，并且从层次遍历算法的程序中可以看出，有一个由当前节点找到其左右孩子节点的操作。这就提示我们，如果知道当前节点的层号，就能推出其左右孩子的层号，即当前节点的层号+1，进而可以求出所有结点的层号

第二：在层次遍历中，用到了一个循环队列（队列用数组表示的），其出对和入队操作:front=(front+1）%MaxSize,  rear=(rear+1)%MaxSize。如果用来存队列的数组足够长，足以容纳树中所有的结点，那就不会出现假溢出的情况，那就可以不用循环队列，用++rear, ++front代替。这样的话，访问的所有结点不存在覆盖的情况，所有节点都保存在数组中。再给这个数组一个层号，如果这个层号是某一层时，一个计数n++，直到这个层全找完为止。
typedef struct BTNode{
	int data;
	struct BTNode * lchild;
	struct BTNode * rchild; 
}BTNode;
typedef struct{
	BTNode * p;		//结点指针 
	int lno;		//节点所在层次号 
}St;
int maxNode(BTnode *b){
	St que[MaxSize];		//定义顺序非循环队列 
	int front,rear=0;
	int Lno=0,i,j,n,max=0;
	front=rear=0;
	BTNode * q;
	if(b!=NULL){
		++rear;
		que[rear].p=b;		//树根入队
		que[rear].lno=1;		//树根所在层次号设为1
		while(front!=rear){
			++front;
			q=que[front].p;
			Lno=que[front].lno;	//关键语句：Lno用来存取当前节点的层次号
			if(q->lchild!=NULL){
				++rear;
				q=que[rear].p=q->lchild;
				que[rear].lno=Lno+1;	//关键语句：根据当前结点的层次号推知其孩子 结点的层次号
				if(q->rchild!=NULL){
					++rear;
					que[rear].p=q->rchild;
					que[rear].lno=Lno+1; 	//关键语句：根据当前结点的层次号推知其孩子 结点的层次号
				} 
			}
			//注意：循环结束后，Lno中保存的时这棵二叉树的最大层数
			/*以下代码找出了含有节点最多的层中的节点数*/
			max=0;
			for(i=1;i<Lno;++i){
				n=0;						//每一层都对应n，每次都得给他清零
				for(j=0;j<rear;++j)			//循环遍历每个数组元素，一共有rear个
					if(que[j].lno==i)		//如果遍历的元素的层数==某一层，
						++n;				//计数++ 
					if(max<n)
						max=n;
			}
			return max; 
		}
		else return 0;		//空树直接返回0 
	}
}

先定义了一个基础的BTNode,在定义了一个结构体，这个结构体包含了BTNode这个结点，也包含了层数。用这个新结构体定义一个数组类型的结构体，这样，每一个节点都对应了一个层数。

也没什么太难的操作，就是给根节点了一个层数Lno = 1，然后正常的找左右孩子入队，然后把层数在原来上一层的基础上++。操作完成后，St数组里存满了元素，对应着也有层号。一共有多少层呢？front是出队列，虽然出，但是元素还是在数组里面的，而rear却是一直往后移动的，所以rear = 节点的个数，又只Lno保存的是当前节点的层数，循环结束后，Lno保存的就是最大层数。

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAXSIZE 100


typedef struct bnode
{
    char data;
    struct bnode *lchild,*rchild;
}BNode,*bitree;


bitree create()
{
    bitree bt=NULL;
    char ch;
    scanf("%c",&ch);
    if(ch==' ')
        return NULL;
    bt=new BNode;
    bt->data=ch;
    bt->lchild=create();
    bt->rchild=create();
}


void level(bitree bt)
{
    bitree q[MAXSIZE];
    int f,r;
    f=r=0;
    int i,j;
    if(bt)
    {
        r++;
        q[r]=bt;
        while(f!=r)
        {
            f++;
            bitree p=q[f];
            cout<<p->data<<" ";
            if(p->lchild)
            {
                r++;
                q[r]=p->lchild;
            }
            if(p->rchild)
            {
                r++;
                q[r]=p->rchild;
            }
        }
    }
}


int width(bitree bt)
{
    int wid=0;
    int i,j;
    bitree q[MAXSIZE];
    int f,r;
    f=r=0;
    if(bt)
    {
        r++;
        q[r]=bt;
        while(f!=r)
        {
            int len=abs(f-r);
            if(len>wid)
                wid=len;
            for(i=0;i<len;i++)
            {
                f++;
                bitree p=q[f];
                if(p->lchild)
                {
                    r++;
                    q[r]=p->lchild;
                }
                if(p->rchild)
                {
                    r++;
                    q[r]=p->rchild;
                }
            }
        }
        cout<<"wid"<<wid<<endl;
        return wid;
    }


}


int main()
{
    bitree bt;
    bt=create();
    level(bt);
    cout<<endl;
    cout<<width(bt);
}