6-8 最宽层次结点数 分数 10

1.题目描述

2.本题ac答案

2.1法一: 代码复用

//二叉树第i层结点个数
int LevelNodeCount(BiTree T, int i)
{
	if (T == NULL || i < 1)
		return 0;
	if (i == 1) 
		return 1;
	return LevelNodeCount(T->lchild, i - 1) + LevelNodeCount(T->rchild, i - 1);
}
int GetDepthOfBiTree(BiTree T)
{
	if (T == NULL)
		return 0;
	return GetDepthOfBiTree(T->lchild) > GetDepthOfBiTree(T->rchild) ? 
		   GetDepthOfBiTree(T->lchild) + 1
		 : GetDepthOfBiTree(T->rchild) + 1;
}
int MaxWidth(BiTree T)
{
	int per = 0;
	int max = 0;
	for (int i = 1; i <= GetDepthOfBiTree(T); i++)
	{
		per = LevelNodeCount(T, i);
		if (per > max)
			max = per;
	}
	return max;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2.2法二: 顺序队列实现层序遍历

int MaxWidth(BiTree T) 
{
	if (T == NULL)
		return 0;
	
	BiTree queue[100] = { 0 };
	BiTree cur = NULL;
	int begin = 0, end = 0;
	int perLevel = 0, max = 0;

	//每入队一个结点 end++表示有效数据加一
	queue[end++] = T;

	//begin != end: 队中还有结点 还未取到上一层所有结点的子结点
	while (begin != end)
	{
		perLevel = end - begin;

		if (perLevel > max)
			max = perLevel;

		//cur指向队头结点 (马上就要被遗弃 因为已经被访问)
		//begin++表示当前结点已被遍历 当前结点被遗弃
		cur = queue[begin++];

		if (cur->lchild)
			queue[end++] = cur->lchild; 
		if (cur->rchild)
			queue[end++] = cur->rchild;
	}
	return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3.C++层序遍历求最大宽度

3.1层序遍历代码

void LevelTraverse(BiTNode* T)
{
	if (T == nullptr)
		return;

	queue<struct BiTNode*> q;
	q.push(T);

	while (!q.empty())
	{
		BiTNode* front = q.front();
		cout << front->data;
		q.pop();

		if (front->lchild)
			q.push(front->lchild);
		if (front->rchild)
			q.push(front->rchild);
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.2求最大宽度

typedef char ElemType;
typedef struct BiTNode
{
	ElemType data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
int MaxWidth(BiTree T)
{
	if (T == nullptr)
		return 0;

	queue<BiTree> q;
	q.push(T);
	int max = 0;

	while (!q.empty())
	{
		//当前层结点数
		int perLevel = q.size();  
		if (perLevel > max)
			max = perLevel;

		//for循环的作用:
		//遍历当前栈中的结点 拿出一个结点node 把它的孩子入栈后就删除node
		//此时栈中存的结点是下一层结点
		for (int i = 0; i < perLevel; i++)
		{
			BiTree front = q.front();
			q.pop();

			if (front->lchild) 
				q.push(front->lchild);
			if (front->rchild)
				q.push(front->rchild);
		}
	}
	return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38