求二叉树的宽度，就是求二叉树某一层上的节点数最多的数。


	public static int getHeight(BiNode head)
	{
		int deep = 0;
		if(head != null)
		{
			int left = getHeight(head.left);
			int right = getHeight(head.right);
			deep = (left>=right)?(left+1):(right+1);
		}
		return deep;
	}
	public static int getWidth(BiNode head)
	{
		if(head == null)
		{
			return 0;
		}
		
		int nWidth = 0;
		int nLastLevelWidth = 0;
		int nTempLastLevelWidth = 0;
		int nCurLevelWidth = 0; 
		
		Queue<BiNode> myQueue = new LinkedList<Demo.BiNode>();
		myQueue.add(head);
		nLastLevelWidth = 1;
		nWidth = 1;
		
		while(!myQueue.isEmpty())
		{
			nTempLastLevelWidth = nLastLevelWidth;
			BiNode tmp = null;
			while(nTempLastLevelWidth != 0)
			{
				tmp = myQueue.peek();
				myQueue.poll();

				if(tmp.left != null)
				{
					myQueue.add(tmp.left);
				}
				if(tmp.right != null)
				{
					myQueue.add(tmp.right);
				}
				nTempLastLevelWidth--;
			}
			
			nCurLevelWidth = myQueue.size();
			nWidth = nCurLevelWidth>nWidth?nCurLevelWidth:nWidth;
			nLastLevelWidth = nCurLevelWidth;
		}
		return nWidth;
	}


参考：http://zhidao.baidu.com/link?url=K1xVilT0OyF_e_FbYr9FVycdq4MBgacNU-1iCOWtGvFJqwb28q1e5j1EJ4QefSy6Qe15ZHD9qV10Bi439AWbuq
http://zhidao.baidu.com/link?url=K1xVilT0OyF_e_FbYr9FVycdq4MBgacNU-1iCOWtGvFJqwb28q1e5j1EJ4QefSy6Qe15ZHD9qV10Bi439AWbuq

求二叉树宽度算法
void width(Tree T)              //求二叉树宽度
{
	int w = 0, wmax = 1, last = -1;
	Tree p;
	queue q;
	q.front = q.rear = -1;
	if(T == NULL)
		printf("该二叉树宽度为0!\n");
	else
	{
		q.data[++q.rear] = T;
		last = q.rear;
		while(q.front < q.rear)
		{
			p = q.data[++q.front];
			if(p->lchild != NULL)
				q.data[++q.rear] = p->lchild;
			if(p->rchild != NULL)
				q.data[++q.rear] = p->rchild;
			w++;
			if(q.front == last)
			{
				if(w > wmax)
					wmax = w;
				w = 0;
				last = q.rear;
			}
		}
		printf("该二叉树宽度为%d!\n", wmax);
	}
}

所谓二叉树宽度,就是至每一层节点数多的那一层的节点数

我的算法大致思路是:

开辟一个数组count[二叉树高度],遍历每一个节点,然后根据当前节点所在层次i,则执行count[i]++;

最后遍历完求出最大的count即为二叉树宽度，代码很简单如下

int  count[100];

int MAX=-1;

 

void FindWidth(BitNode T,int k)

{

    if(T==NULL)  return;

    count[k]++;

    if(MAX<count[k]) MAX=count[k];

    FindWidth(T->lchild,k+1);

    FindWidth(T->rchild,k+1);

}

 

--------------------- 

作者：FightingBa 

来源：CSDN 

原文：https://blog.csdn.net/mcb199175mcb/article/details/12031217 

版权声明：本文为博主原创文章，转载请附上博文链接！

二叉树宽度优先搜索( Breadth - first Search )使用队列来进行进行。
算法步骤：
                1. 从根节点开始，使根节点入队；
                2. 当队列不为空，使队头元素出队，打印其结点的数据域，若其有左右孩子，使其左右孩子按顺序入队；
                3. 队列为空时，已经按照宽度遍历整个二叉树；
实现代码：
struct Tnode;
typedef struct TNode *SearchTree;

struct TNode
{
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};

void bfs( SearchTree T )
{
    Queue Q;

    Q.Enqueue( T ); // Q存储指针，指针指向结点
    while ( !Q.IsEmpty() )
    {
    	SearchTree TmpCell = Q.Dequeue;

    	if ( TmpCell->Left != NULL )
    		Q.Enqueue( TmpCell->Left );
    	if ( TmpCell->Right != NULL )
    		Q.Eequeue( TmpCell->Right );

    	// 对结点Q进行打印等操作
    }
}