由某习题联想到的二叉树广义表表示法求深度(C语言)
二叉树求深度(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。
上一篇: Thread.sleep()概述
下一篇: tty中文乱码