2123 求二叉树的高和宽

admin2024-05-15  0

描述

以二叉链表为存储结构,分别写出求二叉树高度及宽度的算法,所谓宽度是指二叉树的各层上,具有结点数最多的那一层上的结点总数。

输入

括号表示的二叉树,如:

A(B,C)

输出

二叉树的高度和宽度,用空格分隔,如:

2 2

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node{
	char data;
	struct node*lchild;
	struct node*rchild;
}tree;
char s[1001];
int cnt=0;
tree* creattree()
{
	char c=s[cnt];
	tree* link = (tree*)malloc(sizeof(tree));
	while(c!=')')
	{
		if(c>='A'&&c<='Z')
		{
			link->data=c;
			link->lchild=NULL;
			link->rchild=NULL;
			cnt++;
			c=s[cnt];
		}
		if(c=='(')//疑似有左孩子
		{
			cnt++;
			if(s[cnt]!=',')//左孩子不空,创建左子树
			link->lchild=creattree();
			c=s[cnt];
			if(c==',')//疑似有右孩子
			{
				cnt++;
				if(s[cnt]==')')//右孩子空的
				{
					cnt++;
					return link;
				}
				link->rchild=creattree();
				cnt++;
				if(cnt>=(int)strlen(s))
					break;
				c=s[cnt];
			}
		}
		if(c==',')//遇到右孩子前面的一个节点,先返回父节点
		{
			return link;
		}
	}
	return link;
}
int maxdepth=0;//最大层数
void depth(tree* head,int d)//深度,d表示当前层数
{
	if(d>maxdepth)maxdepth=d;
	if(head->lchild!=NULL)
	{
		d++;
		depth(head->lchild,d);
		d--;
	}
	if(head->rchild!=NULL)
	{
		d++;
		depth(head->rchild,d);
		d--;
	}
}
int wid[1001],maxwid=0;//wid[i]表示第i层拥有的节点个数
int curdepth=0;//当前在树中的层数
void width(tree* head)//宽度
{
	wid[curdepth]++;
	if(wid[curdepth]>maxwid)maxwid=wid[curdepth];
	if(head->lchild!=NULL)
	{
		curdepth++;
		width(head->lchild);
		curdepth--;
	}
	if(head->rchild!=NULL)
	{
		curdepth++;
		width(head->rchild);
		curdepth--;
	}
}
int main()
{
	scanf("%s",s);
	tree*head=creattree();
	depth(head,1);
	memset(wid,0,sizeof(wid));
	width(head);
	printf("%d %d",maxdepth,maxwid);
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!