数据结构二叉树实验报告_计算二叉树的宽度实验结果

第一个实验是求一颗树的结点个数,叶子结点个数,某一个结点的深度,以及整颗树的宽度.
先来考虑一下如何读入一颗树.其实递归的读入左右子树即可.
参考代码:
树的结构体:

struct Tree{
   
    char data;
    Tree * lson,* rson;
};
1
2
3
4
5

读入部分

bool input(Tree *now){
    // 这部分只是读入这颗树,不一定要这么写
    cin >> now->data;
    if(now->data == '0') return false; // 空节点就用'0'来识别返回false
    now->lson = new Tree;
    now->rson = new Tree;
    if(!input(now->lson)) now->lson = NULL; // 空节点
    if(!input(now->rson)) now->rson = NULL; // 空节点
    return true;
}
1
2
3
4
5
6
7
8
9
10

前两个很好求,深度和宽度我们用两个数组dep和wid来记录一下(因为树上结点权值是互异的,这样做比较方便).代码里的注释写的应该比较清楚了.

int num,lefnum;
int wid[100],dep[100],l=0,r=0;
void bfs(Tree 
1
2