swust oj 971
2024-10-18 18:27:55
统计利用先序遍历创建的二叉树的深度
10000(ms)
10000(kb)
3331 / 8436
利用先序递归遍历算法创建二叉树并计算该二叉树的深度。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建,否则创建该结点。最后再统计创建完成的二叉树的深度(使用二叉树的后序遍历算法)。需要注意输入数据序列中的"#"字符和非"#"字符的序列及个数关系,这会最终决定创建的二叉树的形态。
输入
输入为先序遍历二叉树结点序列。
输出
对应的二叉树的深度。
样例输入
A##
ABC####
AB##C##
ABCD###E#F##G##
A##B##
样例输出
1
3
2
4
1
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cstdio>
typedef int Datetype;
using namespace std;
typedef struct link{
Datetype date;
struct link *lchild;
struct link *rchild;
}tree; void creattree(tree *&L)
{
char c;
cin>>c;
if(c=='#')
L=NULL;
else
{
L = (tree *)malloc(sizeof(tree)) ;
L->date=c;
creattree(L->lchild);
creattree(L->rchild);
}
} void destroytree(tree *&L)
{
if(L!=NULL)
{
destroytree(L->lchild);
destroytree(L->rchild);
free(L);
}
} int deep(tree *L)
{
int ldep,rdep,max;
if(L!=NULL)
{
ldep=deep(L->lchild);
rdep=deep(L->rchild);
max=ldep>rdep?ldep+:rdep+;
return max;
}
else
return ;
} int main()
{
tree *L = NULL;
int x;
creattree(L);
x=deep(L);
cout<<x;
destroytree(L);
return ;
}
最新文章
- 奇 arch/i386/kernel/head.o(.text+0x3e): undefined reference to `stack_start&#39;
- Bootstrap3.0学习教程十七:JavaScript插件模态框
- 掌握Tiles 框架 (一)---Tiles入门和Tiles 框架和体系结构
- Add an IPv6 route through an interface
- SDRAM操作说明
- java提高(6)---Serializable
- MySQL数据库优化_索引
- [iOS] KVC 和 KVO
- html中&;lt;a&;gt;标签的种类
- Pomelo分布式游戏服务器框架
- 关于面试总结2-SQL学生表
- clapack在android上移植
- 关于kvm虚拟机的克隆方法总结
- 快速搭建一个简易的KMS 服务
- c语言转移符和三字母序列
- DevExpress.XtraLayout.LayoutControl 动态添加控件
- xargs详解
- Python @ddt.file_data() 为.yml 文件实例
- SpringMVC学习 -- 使用 @RequestMapping 映射请求
- TCP(一)