数据结构——二叉树的宽度【非递归算法与层次遍历】（C语言）

层次遍历与树的宽度非递归算法求解此处用到了< queue >为C++语言STL的队列库，其操作原理与队列相同。 #include<stdio.h> #include<stdlib.h> #include<queue> #include <iostream> #define MAXSIZE 10010 #define ElemType int using namespace std; typedef struct BTNode{ ElemType data; BTNode *lchild,*rchild; }*BTree; //先序建树 BTree CreateTree(){ ElemType ch; printf("输入结点元素值："); scanf("%d",&ch); if(ch == 0) return NULL; else{ BTree tree=(BTree)malloc(sizeof(BTree)); tree->data=ch; printf("%d 结点左子树\n",ch); tree->lchild=CreateTree(); printf("%d 结点右子树\n",ch); tree->rchild=CreateTree(); return tree; } } //层次遍历 void LayeredOrderTravel(BTree tree){ queue<BTree> queue1; BTree p; if(tree){//树非空 //入队与队列指针（下标）初始化 queue1.push(tree); while(!queue1.empty()){//队列非空 p=queue1.front();//队头元素出队并访问 queue1.pop(); printf("%d ",p->data);//访问 if(p->lchild)//左孩子不为空则入队 queue1.push(p->lchild); if(p->rchild)//右孩子不为空则入队 queue1.push(p->rchild); } } } int getDepth(BTree tree){ if(!tree) return 0; else{ int leftDepth=getDepth(tree->lchild); int rightDepth=getDepth(tree->rchild); return leftDepth > rightDepth ? (leftDepth+1):(rightDepth+1); } } //计算树的宽度（结点最多的那一层的结点总个数） int getWidth(BTree tree){ if(!tree)//为空 return 0; int maxWidth=0; if(!tree->lchild&& !tree->rchild) {//叶子结点 return 1; }else{//递归到叶子结点，计算该层的宽度，然后依次回溯到根结点，取整个过程中宽度的最大值 maxWidth=(getWidth(tree->lchild)+getWidth(tree->rchild)) > maxWidth ? (getWidth(tree->lchild)+getWidth(tree->rchild)) : maxWidth; } return maxWidth; } int getWidth2(BTree tree){ if(!tree) return 0; queue<BTree> queue1; BTree p; int maxWidth=1,lastWidth=0,templateWidth=0; if(tree){//树非空 //入队与队列指针（下标）初始化 queue1.push(tree); lastWidth=1; while(!queue1.empty()){//队列非空[未遍历完所有结点] templateWidth=lastWidth; while(templateWidth){//当前层所有结点 p=queue1.front();//队头元素出队并访问 queue1.pop(); //printf("%d ",p->data); if(p->lchild) queue1.push(p->lchild); if(p->rchild) queue1.push(p->rchild); templateWidth--;//取出队头元素【上一层元素】，记录的上一层结点的宽度减一 }//while int nowWidth=queue1.size(); maxWidth= nowWidth > maxWidth ? nowWidth : maxWidth; lastWidth= nowWidth; }//while }//if return maxWidth; } int main(){ printf("二叉树的建立\n"); BTree tree; tree=CreateTree(); printf("二叉树的层序遍历\n"); LayeredOrderTravel(tree); printf("\n获取二叉树深度\n"); int maxDepth=0,maxWidth=0; maxDepth=getDepth(tree); printf("树的深度为：%d\n",maxDepth); printf("\n递归算法获取二叉树宽度\n"); maxWidth=getWidth(tree); printf("树的宽度为：%d\n",maxWidth); printf("\n非递归算法获取二叉树宽度\n"); maxWidth=getWidth2(tree); printf("树的宽度为：%d\n",maxWidth); return 0; }