[游戏开发]计算二叉树的深度和宽度

计算二叉树的最大深度和最大宽度

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxSize 500             //假设循环队列足够长，因为下面要用到Q.rear来计算每一层的宽度

typedef struct BiTNode{
    char data[5];
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct SqQueue{
    BiTNode *t[MaxSize];
    int rear,front;
}SqQueue;

int Length(BiTree T);
BiTNode *CreateBiTree();
int high(BiTree T);
int main(){
	BiTNode *p=CreateBiTree();
	int l=Length(p);
	int h=high(p);
	printf("the length:%d\nthe high:%d",l,h);
	return 0;
}
//构造二叉树有很多的方法（例如递归等等），这里我是用了最笨的一种方法
BiTNode *CreateBiTree(){
    BiTNode *T=(BiTNode *)malloc(sizeof(BiTNode));
    strcpy(T->data,"A");
   
	BiTNode *p=(BiTNode *)malloc(sizeof(BiTNode));
	strcpy(p->data,"B");
	T->lchild=p;
   
    p=(BiTNode *)malloc(sizeof(BiTNode));
	strcpy(p->data,"C");
	T->rchild=p;
  
    p=(BiTNode *)malloc(sizeof(BiTNode));
    strcpy(p->data,"D");
    T->lchild->lchild=p;
    T->lchild->lchild->lchild=NULL;
    T->lchild->lchild->rchild=NULL;
   
    p=(BiTNode *)malloc(sizeof(BiTNode));
    strcpy(p->data,"E");
    T->lchild->rchild=p;
    T->lchild->rchild->lchild=NULL;
    T->lchild->rchild->rchild=NULL;
  
    p=(BiTNode *)malloc(sizeof(BiTNode));
    strcpy(p->data,"F");
    T->rchild->lchild=p;
    T->rchild->lchild->lchild=NULL;
    T->rchild->lchild->rchild=NULL;
  
    T->rchild->rchild=NULL;

    return T;
}
//返回二叉树最大宽度
int Length(BiTree T){
    SqQueue Q;
    Q.rear=Q.front=0;           //队列初始化
    int lno[MaxSize];           //设一个数组存放层次遍历顺序下的每个结点所在的层号
    int Lno=0,max=0,n;
    BiTNode *p;
    if(T){
        Q.t[Q.rear]=T;       //根节点入队,等同于EnQueue(Q,T)入队操作
        lno[Q.rear]=1;              //根节点所在的那一层为第1层
        Q.rear++;
        while(Q.front!=Q.rear){     //当队列非空时循环继续
            p=Q.t[Q.front];    //p指向出队结点，等同于DeQueue(Q,p)出队操作
            Lno=lno[Q.front];  //本函数的核心语句，Lno用来存放当前结点的层次号
            Q.front++;
            if(p->lchild){
                Q.t[Q.rear]=p->lchild;
                lno[Q.rear]=Lno+1; //根据当前结点的层次号算出其孩子结点的层次号，也就是孩子结点比父结点多一层，加一即可
                Q.rear++;
            }
            if(p->rchild){
                Q.t[Q.rear]=p->rchild;
                lno[Q.rear]=Lno+1; //根据当前结点的层次号算出其孩子结点的层次号，也就是孩子结点比父结点多一层，加一即可
                Q.rear++;
            }
        }       //while循环结束时，Lno变量存放的是二叉树的最大层数，顺道把二叉树的深度也给求出来了
        for(int i=1;i<=Lno;i++){
            n=0;
            for(int j=0;j<Q.rear;j++){
                if(lno[j]==i){
                    n++;                //统计相同层号的结点数
				}
            }
            if(max<n){                  //max变量记录最大的结点数，也就是宽度！！！
                max=n;
            }
        }
        return max;
    }else{
        return 0;
    }
}
//返回最大高度
int high(BiTree T){
	int m,n;
	if(T){
		m=high(T->lchild);
		n=high(T->rchild);
		return m>n?m+1:n+1;
	}else{
		return 0;
	}
	
	
	
}

程序运行截图：