欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

由某习题联想到的二叉树广义表表示法求深度(C语言)

程序员文章站 2022-07-14 16:16:49
...

二叉树求深度(C语言)

  • 习题详情及解法
  • 二叉树的深度求解

阅读之前注意:

本文阅读建议用时:31min
本文阅读结构如下表:

项目 下属项目 测试用例数量
习题详情及解法 1
二叉树的深度求解 1

习题详情及解法

习题详情:链接:https://www.nowcoder.com/questionTerminal/a2d5b1875bb0408384278f40d1f236c9
来源:牛客网
题目名称:”括号匹配深度“
一个合法的括号匹配序列有以下定义:
1、空串”“是一个合法的括号匹配序列
2、如果”X”和”Y”都是合法的括号匹配序列,”XY”也是一个合法的括号匹配序列
3、如果”X”是一个合法的括号匹配序列,那么”(X)”也是一个合法的括号匹配序列
4、每个合法的括号序列都可以由以上规则生成。
例如: “”,”()”,”()()”,”((()))”都是合法的括号序列
对于一个合法的括号序列我们又有以下定义它的深度:
1、空串”“的深度是0
2、如果字符串”X”的深度是x,字符串”Y”的深度是y,那么字符串”XY”的深度为max(x,y) 3、如果”X”的深度是x,那么字符串”(X)”的深度是x+1
例如: “()()()”的深度是1,”((()))”的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

输入描述:
输入包括一个合法的括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含’(‘和’)’。
输出描述:
输出一个正整数,即这个序列的深度。
示例1
输入
(())
输出
2

这题并不难,所以这里直接给出我的解法,思路是这样:遇到左括号深度就加一,遇到右括号深度就减一,因为左右括号是对称存在的,所以只需要比较出哪一次走得最深即可。参考以下代码:

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

int main()
{
    int i = 0;
    int len = 0;//字符串长度
    int dep = 0;//要输出的深度
    int depTmp = 0;//临时深度
    char str[100];
    scanf("%s", str);
    len = strlen(str);//计算字符串长度
    for (i = 0; i < len; i++)
    {
        if (str[i] == '(')
        {
            depTmp++;
        }
        if (str[i] == ')')
        {
            if (dep < depTmp)//要输出的深度和临时深度比较
                dep = depTmp;
            depTmp--;
        }
    }
    printf("%d", dep);
    system("pause");
    return 0;
}

后来在我学习二叉树的时候,知道了广义表表示法,突然就想起了这道题。不如说这道题就是抽离了二叉树的背景知识,只是单纯测试逻辑而已。

二叉树的深度求解

从以上的深度求解来看,对于任意一个二叉树,其深度也可以类似的求解。以下代码思路是:进入一层递归深度加一,跳出一层递归深度减一,最深的深度即为二叉树深度。和以上括号求解深度的思路是一样的。
参考以下代码:

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define max_num 15

int max = 0;//最大深度
int depth = 0;//临时深度

typedef struct _BitNode
{
    int data;
    struct _BitNode *lchild, *rchild;
}BitNode, *BitTree;

void find(BitTree t)
{
    if (t == NULL)
        return;
    depth++;//深度加一
    if (depth > max)
        max = depth;
    find(t->lchild);
    find(t->rchild);
    printf("%d ", t->data);
    depth--;//深度减一
}

void main()
{
    BitNode b[max_num];
    memset(b, 0, sizeof(BitNode)*max_num);
    for (int i = 1; i < max_num; i++)//自动生成类似完全二叉树的树
    {
        b[i].data = i;
        if (2 * i < max_num)
            b[i].lchild = &b[2 * i];
        if (2 * i+1 < max_num)
            b[i].rchild = &b[2 * i + 1];
        printf("%d ", b[i].data);
    }
    printf("\n");
    find(b + 1);
    printf("\n%d\n", max);
    system("pause");
}

为了方便读者理解,这里定义了两个全局变量max和depth,但实际应用场合的话,应该把全局变量变为指针作函数参数。
至于这里的自动生成二叉树,只是利用了完全二叉树的特性:如果根为一号,那么对于以后的每个父亲,号码为i,那么其左孩子号码就是2*i,右孩子号码是2*i+1。