【数据结构】二叉树深度的计算
二叉树的深度计算
我们先看一个深度为3的二叉树。想求得此二叉树深度，先计算左孩子深度，再计算右孩子深度，比较得出最大值，即二叉树深度。
通过先序序列键盘输入一个二叉树 ABD##E##CF###。
注：
二叉树的输入方式：先左后右，深度遍历，没子树的结点为#。
设计算法则先遍历二叉树的左子树的深度，然后再遍历二叉树右子树的深度。最后判断左子树和右子树的深度，如果左子树比右子树深则返回左子树深度+1,否则返回右子树深度+1。
完整代码展示
#include <stdio.h> #include <malloc.h> typedef struct BiTNode { char data; /*结点的数据域*/ struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/ } BiTNode , *BiTree; /*创建一棵二叉树*/ void CreatBiTree(BiTree *T) { char c; scanf("%c",&c); if(c == '#') *T = NULL; else { *T = (BiTNode * )malloc(sizeof(BiTNode)); /*创建根结点*/ (*T)->data = c; /*向根结点中输入数据*/ CreatBiTree(&((*T)->lchild)); /*递归地创建左子树*/ CreatBiTree(&((*T)->rchild)); /*递归地创建右子树*/ } } //计算二叉树的深度 int getBitreeDepth(BiTree T) { int leftHeight, rightHeight, maxHeight;//左子树，右子树，最大深度 if (T != NULL) //如果为空树 { leftHeight = getBitreeDepth(T->lchild);//左子树深度 rightHeight = getBitreeDepth(T->rchild);//右子树深度 maxHeight = leftHeight>rightHeight?leftHeight:rightHeight;//最大深度 return maxHeight+1;//二叉树深度=最大深度+1 } else { return 0; } } void main() { BiTree T = NULL; /*最开始T指向空*/ printf("请您输入一个二叉树（以#为空子树）：\n"); CreatBiTree(&T); /*创建二叉树*/ printf("\n二叉树的深度为%d\n",getBitreeDepth(T)); getchar() ; getchar() ; }
程序结果
