每日一题(二) 7.28

每日一题 7.28

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

思路：

• 建立二叉树结构
• 建立二叉树，创造结点
• 递归求解二叉树深度
• 释放结点

代码：

#include<stdio.h>
#include<stdlib.h>

//二叉树结构
typedef struct tree //结构体的名字为tree
{
    char ch;
    struct tree *lchild;//指向tree型变量的指针（指向自己结构体的指针）
    struct tree *rchild;
}tree;
//按先序建立二叉树
tree *CreateTree()  //创建树；
{
    tree *bt;  //定义节点的指针bt
    char str;  //屏幕输入的字符
    scanf("%c",&str);  //把屏幕输入字符赋予str
    if(str=='0')
        return NULL;
    else
    {
        bt=(tree *)malloc(sizeof(tree));//为指针bt申请内存空间
        bt->ch=str;
        bt->lchild=CreateTree();
        bt->rchild=CreateTree();
        return bt;
    }
}
//先定义两个变量，初始化为0 int ld=0，int rd=0；分别表示左子树和右子树的深度；
//先判断二叉树bt是否为空，为空直接return返回；
//不为空，进入左子树的递归调用，此时ld=1，一直到某个结点的左子树为空，if条件不成立，返回上一层递归调用；
//之后进入右子树的递归调用，再进入这个结点的左子树一直到左子树为空，返回上一层递归调用，继续进入右子树的递归调用；
//一直循环判断使用哪个递归调用；
//一直到某个结点的左右子树为空，返回ld和rd的最大值，并将所带回的值+1，重新赋给ld或者rd；
//重复上述过程，直到根结点，说明bt为空，无法继续返回，所以结束调用函数；
//返回main函数带回一个整型的值；


//求二叉树的深度,递归实现；
int DeepOrder(tree *bt)
{
    int ld=0,rd=0;
    if(bt)
    {
        //先找到最左边的左右孩子为空的结点，之后找到相对位置靠近第一个结点的结点，依次类推；
        ld=DeepOrder(bt->lchild)+1;
        rd=DeepOrder(bt->rchild)+1;
    }
    return ld>=rd?ld:rd;
}

//释放树的结点；
void DestroyTree(tree *bt)
{
    if(bt)
    {
        DestroyTree(bt->lchild);
        DestroyTree(bt->rchild);
        free(bt);
    }
}

int main(void)
{
    tree *bt;
    printf("请以先序输入二叉树(0表示该结点的子结点为空):\n");
    bt=CreateTree();
    printf("bt为： %s",bt);
    int deep=DeepOrder(bt);
    printf("\n二叉树的深度为:  %d\n",deep);
    printf("\n");
    DestroyTree(bt);  //释放树结点；
    return 0;
}