【数据结构】计算二叉树深度完整C语言代码

╰半橙微兮° 2023-03-03 08:54 8阅读 0赞

### 【数据结构】二叉树深度的计算 ###

*  二叉树的深度计算
 *  完整代码展示
 *   *   *  程序结果

# 二叉树的深度计算 #

我们先看一个深度为3的二叉树。想求得此二叉树深度，先计算左孩子深度，再计算右孩子深度，比较得出最大值，即二叉树深度。  
通过先序序列键盘输入一个二叉树 ABD\#\#E\#\#CF\#\#\#。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODcwMTUyMQ_size_16_color_FFFFFF_t_70]  
注：  
二叉树的输入方式：先左后右，深度遍历，没子树的结点为\#。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODcwMTUyMQ_size_16_color_FFFFFF_t_70 1]

设计算法则先遍历二叉树的左子树的深度，然后再遍历二叉树右子树的深度。最后判断左子树和右子树的深度，如果左子树比右子树深则返回左子树深度+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() ;
    }

### 程序结果 ###

![在这里插入图片描述][20200730195545151.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODcwMTUyMQ_size_16_color_FFFFFF_t_70]: /images/20230208/86ed0cb9a0a847f1a0da524ed97c3b04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODcwMTUyMQ_size_16_color_FFFFFF_t_70 1]: /images/20230208/39e297ecc5ea4165ac512f169103d837.png
[20200730195545151.png]: /images/20230208/5c4f9a82c84143399da2f1ffa9e87a21.png