数据结构——二叉树深度与宽度【递归算法】（C语言）

递归当时参考了一下网上的，没有严格测试，目前存在点问题，复习紧张，有空了再更，见谅。这是非递归版本。（正确的）https://blog.csdn.net/weixin_42468092/article/details/108961202 -二叉树的深度与宽度的计算（递归版本） 示例：(A)1，(B)2，0，（C）3，0，0，(D)4，0，0 #include<stdio.h> #include<stdlib.h> #include<math.h> #define MAXSIZE 10010 #define ElemType int 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 PreOrderTravel(BTree tree){ if(tree == NULL) return; printf("%d ",tree->data); PreOrderTravel(tree->lchild); PreOrderTravel(tree->rchild); } //中序遍历 void MedOrderTravel(BTree tree){ if(tree == NULL) return; MedOrderTravel(tree->lchild); printf("%d ",tree->data); MedOrderTravel(tree->rchild); } //后序遍历 void AftOrderTravel(BTree tree){ if(tree == NULL) return; AftOrderTravel(tree->lchild); AftOrderTravel(tree->rchild); printf("%d ",tree->data); } 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 main(){ printf("二叉树的建立\n"); BTree tree; tree=CreateTree(); printf("二叉树的先序遍历\n"); PreOrderTravel(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); return 0; }