1501 二叉树最大宽度和高度

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 白银 Silver

题目描述 Description

给出一个二叉树，输出它的最大宽度和高度。

输入描述 Input Description

第一行一个整数n。

下面n行每行有两个数，对于第i行的两个数，代表编号为i的节点所连接的两个左右儿子的编号。如果没有某个儿子为空，则为0。

输出描述 Output Description

输出共一行，输出二叉树的最大宽度和高度，用一个空格隔开。

样例输入 Sample Input

2 3

4 5

0 0

样例输出 Sample Output

2 3

数据范围及提示 Data Size & Hint

n<16

默认第一个是根节点

以输入的次序为编号

2-N+1行指的是这个节点的左孩子和右孩子

注意：第二题有极端数据！

0 0

这题你们别想投机取巧了，给我老老实实搜索！

分类标签 Tags 点此展开

#include<cstdio>
#include<iostream>
using namespace std;
int a[30][3],b[30];
int main(){
    int n,x,y,k,wide=0,deep=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        a[i][0]=x;a[i][1]=y;//储存左右孩子 
        a[x][2]=i;a[y][2]=i;//储存其父节点    
    }
    for(int i=1;i<=n;i++){
        k=1;
        x=a[i][2];
        while(x!=0){
            k++;
            x=a[x][2];
        }
        b[k]++;
        if(k>deep) deep=k;
        if(b[k]>wide) wide=b[k];    
    }
    printf("%d %d
",wide,deep);
    //wide--最下一层的宽度（上一层的某节点最多有几个孩子）；deep--深度 
    return 0;
}

复习二叉树

一般的树都可以转换为二叉树，且二叉树的存储结构及操作都较为简单，因此先介绍下树中的二叉树类型。

二叉树是n个结点的有限集，它或者是空集（n=0），或者有一个根结点及最多两棵互不相交的，分别称作这个根的左子树和右子树的二叉树组成。

二叉树有五种基本形态：（1）空集（2）根的左右子树都为空（3）根的右子树为空（4）根的左子树为空（5）根的左右子树皆不为空。

二叉树的逻辑结构：

二叉树与无序树不同，二叉树中，每个结点最多只能有两棵子树，并且无左右之分。另外，二叉树与度数为2的有序树不同，在有序树中，虽然一个极点的孩子之间是有左右次序的，但若该结点只有一个孩子，就无须区分其左右次序；而二叉树中，即使是一个孩子也有左右之分。所以，二叉树不是树的特殊情形。

二叉树的特殊性质（在此不证明）：

（1）二叉树第i层上的结点数目最多为2^i-1（i>=1）;

(2)深度为k的二叉树至多有2^k-1个结点（k>=1）;

(3)在任意一颗二叉树中，若终端结点的个数为n0，度为2的结点数为n_2,则n0=n₂+1_；

完全二叉树：若二叉树的高度为h，除第h层外，其他各层（1-h-1）的结点数都达到最大个数，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树被称为完全二叉树。

满二叉树：一颗深度为k且有2^k-1个结点的二叉树称为满二叉树。

还有很多性质，在这不在多讨论。可以参考其他书籍。

顺序存储结构实现的主要思想：将一般二叉树填上一些空结点，使之成为“完全二叉树”，并且按完全二叉树形式给结点编号。其中的空结点便是顺序存储过程中浪费的空间。

参考：http://www.360doc.com/content/13/0422/18/3777348_280168665.shtml

http://www.jb51.net/article/37334.htm