树10——求二叉树的高度和宽度

二叉树

二叉树采用二叉链表存储。（1）编写计算整个二叉树高度的算法。（2）编写计算二叉树最宽的算法。二叉树的最大宽度是指二叉树左右层中结点个数的最大值。

这是西北大学考研试题。
二叉树的高度递归定义为：

当二叉树为空时，其深度为0。当二叉树只有根结点时，即结点的左、右子树为空，二叉树的深度为1。其他情况下，二叉树的左、右子树高度的最大值再加1（根结点）就是二叉树的高度。

求二叉树的最大宽度可以通过层次遍历二叉树实现。具体思路为：依次将每一层中结点指针入队列，然后再分别将当前的指针出队，统计其结点个数，并将下一层结点指针入队，记录每一层结点个数，可得出结点个数最大值。遍历完毕后，结点个数最大值就是二叉树的最大宽度。

code:

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
using namespace std;
#define MAXSIZE 100
typedef struct Node 
{
	char data;
	struct Node* lchild, *rchild;

}BitNode,*BiTree;
void CreateBitTree(BiTree *T, char str[]);
void PrintLevel(BiTree T);
void CreateBitTree(BiTree *T, char str[])
{
	char ch;
	BiTree stack[MAXSIZE];
	int top = -1;
	int flag, k;
	BitNode *p;
	*T = NULL, k = 0;
	ch = str[k];
	while (ch!='\0')
	{
		switch (ch)
		{
		case '(':
			stack[++top] = p;
			flag = 1;
			break;
		case ')':
			top--;
			break;
		case ',':
			flag = 2;
			break;

		default:
			p = (BiTree)malloc(sizeof(BitNode));
			p->data = ch;
			p->lchild = NULL;
			p->rchild = NULL;
			if (*T==NULL)
			{
				*T = p;
			} 
			else
			{
				switch (flag)
				{
				case 1:
					stack[top]->lchild = p;
					break;
				case 2:
					stack[top]->rchild = p;
					break;
				}
			}
			
		}

		ch = str[++k];
	}
}
void TreePrint(BiTree T, int level)
{
	int i;
	if (T==NULL)
	{
		return;
	}
	TreePrint(T->rchild, level + 1);
	for (i = 0; i < level;i++)
	{
		printf("    ");
	}
	printf("%c\n",T->data);
	TreePrint(T->lchild, level + 1);
}

int BiTreeDepth(BiTree T)
{
	if (T==NULL)
	{
		return 0;
	}
	return BiTreeDepth(T->lchild) > BiTreeDepth(T->rchild) ? 1 + BiTreeDepth(T->lchild) : 1 + BiTreeDepth(T->rchild);
}

int BiTreeWidth(BiTree T)
{
	int front, rear, last, maxw, temp;
	BiTree Q[MAXSIZE];
	BitNode *p;
	if (T==NULL)
	{
		return 0;
	} 
	else
	{
		front = 1, rear = 1, last = 1;
		temp = 0;
		maxw = 0;
		Q[rear] = T;
		while (front<=last)
		{
			p = Q[front++];
			temp++;
			if (p->lchild!=NULL)
			{
				Q[++rear] = p->lchild;
			}
			if (p->rchild!=NULL)
			{
				Q[++rear] = p->rchild;
			}
			if (front>last)
			{
				last = rear;
				if (temp>maxw)
				{
					maxw = temp;

				}
				temp = 0;
			}
		}

		return maxw;
	}

}


void main()
{
	BiTree T;
	char str[MAXSIZE];
	cout << "请输入二叉树的广义表形式：" << endl;
	cin >> str;
	cout << "由广义表形式的字符串构造二叉树：" << endl;
	CreateBitTree(&T, str);
	cout << endl;
	TreePrint(T, 1);
	cout << endl;
	cout << "这棵树的高度为：" << BiTreeDepth(T) << endl;
	cout << "这棵树的最大宽度为：" << BiTreeWidth(T) << endl;
	system("pause");
	//A(B(D(H,I),E),C(F,G))
}

结果：