hnust 2179:创建二叉树并计算深度
题目描述
编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。
例如如下的先序遍历字符串:
ABC##DE#G##F###
其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再计算二叉树的深度并输出。
下面提供代码框架,请同学完成指定的部分。
//算法5.3 先序遍历的的顺序建立二叉链表
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
typedef char TElemType;
//二叉树的二叉链表存储表示
typedef struct BiTNode {
TElemType data; //结点数据域
struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;
void CreateBiTree(BiTree &T)
{
//按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T
TElemType ch;
//此处和教材的不同是,要处理多组数据,输入ch如果遇到EOF,应该结束程序
//所以main函数用while(1)
if(!(cin >> ch)) exit(0); //用此行替换教材上的语句:cin>>ch; 实现若读入失败就退出,避免死循环。
/****在此下面完成代码***************/
/***********************************/
} //CreateBiTree
//用算法5.5 计算二叉树的深度
int Depth(BiTree T)
{
//计算二叉树T的深度
/****在此下面完成代码***************/
/***********************************/
}
void DestroyBitree(BiTree& T)
{
/****在此下面完成代码***************/
/***********************************/
}
int main()
{
BiTree tree;
while(1) {
CreateBiTree(tree);
cout << Depth(tree);
cout << endl;
DestroyBitree(tree);
}
}
输入
输入有多组测试数据。
每组数据为一行字符串,长度不超过100。
输出
可能有多组测试数据,对于每组数据,
输出对应二叉树的深度。
每个输出结果占一行。
样例输入 Copy
a#b#cdef#####
a##
样例输出 Copy
6
1
代码解析
这段C++代码实现了二叉树的创建、深度计算和销毁。
1. 数据结构定义
BiTNode
:定义了二叉树的节点结构,包含数据域data
和指向左右孩子的指针lchild
,rchild
。BiTree
:二叉树的类型定义,指向BiTNode
的指针。
2. 函数 CreateBiTree
- 作用:根据用户输入的先序序列创建二叉树。
- 输入参数:二叉树的引用
T
。 - 过程:
- 读取一个字符
ch
,如果是'#'
,则将T
设置为NULL
。 - 否则,创建一个新的节点,将
ch
存储在节点的数据域中,并递归地创建左子树和右子树。
- 读取一个字符
3. 函数 Depth
- 作用:计算二叉树的深度。
- 输入参数:二叉树
T
。 - 过程:
- 如果
T
为空,返回0。 - 否则,递归地计算左子树和右子树的深度,取较大者加1作为当前节点的深度。
- 如果
4. 函数 DestroyBitree
- 作用:销毁二叉树,释放所有节点的内存。
- 输入参数:二叉树的引用
T
。 - 过程:
- 如果
T
不为空,递归地销毁左子树和右子树,然后释放当前节点的内存,并将指针设置为NULL
。
- 如果
5. 主函数 main
- 声明一个
BiTree
类型的指针tree
。 - 使用无限循环
while(1)
来创建、计算深度和销毁二叉树。 - 每次循环都重新创建二叉树,计算其深度,然后销毁二叉树。
解题过程分析
问题分析
本文将讨论如何使用C++实现二叉树的创建、深度计算和销毁。二叉树是一种常见的数据结构,广泛应用于计算机科学中。在本例中,我们将使用先序遍历来创建二叉树,并计算其深度。
创建二叉树
创建二叉树的过程是通过先序遍历实现的。先序遍历的顺序是:首先访问根节点,然后递归地遍历左子树,最后递归地遍历右子树。在创建过程中,我们使用字符作为节点的值,并根据输入的 '#'
来确定空树的位置。
计算二叉树深度
二叉树的深度是指从根节点到最远叶子节点的最长路径上的节点数。我们可以通过递归地计算左右子树的深度,然后取较大者加1来得到整棵树的深度。
销毁二叉树
由于二叉树的节点是通过动态内存分配创建的,因此在不需要二叉树时,需要手动释放每个节点占用的内存,以避免内存泄漏。
代码分解
- 数据结构定义:定义了二叉树节点的结构
BiTNode
和二叉树类型BiTree
。 - 创建函数:
CreateBiTree
函数使用递归方法根据先序输入创建二叉树。 - 深度计算函数:
Depth
函数使用递归方法实现二叉树深度的计算。 - 销毁函数:
DestroyBitree
函数使用递归方法销毁二叉树,释放所有节点的内存。 - 主函数:在
main
函数中,使用无限循环来不断创建、计算深度和销毁二叉树。
总结
本文通过一段C++代码,展示了如何创建、计算深度和销毁二叉树。这些操作是数据结构中的基本技能,对于理解和掌握二叉树的概念非常有帮助。
题目分析
这个问题要求我们实现一个程序,该程序可以读取用户输入的先序遍历字符串,并根据此字符串建立一个二叉树。然后,程序需要计算并输出这个二叉树的深度。
难点应对
- 先序遍历字符串的处理:需要识别并处理字符串中的 ‘#’ 字符,它代表空树。
- 二叉树的创建:使用递归方法根据先序遍历字符串建立二叉树。
- 二叉树深度的计算:需要递归地计算左右子树的深度,并确定整棵树的深度。
算法选择
- 先序遍历创建二叉树:使用递归方法,根据先序遍历的特点,首先创建根节点,然后递归地创建左子树和右子树。
- 深度计算:使用递归方法,计算左右子树的深度,并取较大者加1作为当前节点的深度。
解决过程
创建二叉树:
- 读取输入字符,如果是
'#'
,则当前节点为空,返回NULL
。 - 否则,创建一个新节点,并递归地为其创建左子树和右子树。
- 读取输入字符,如果是
计算二叉树的深度:
- 如果树为空,返回0。
- 否则,递归地计算左子树和右子树的深度,取较大者加1作为当前树的深度。
销毁二叉树:
- 使用递归方法,先销毁左子树和右子树,然后释放当前节点的内存。
注意事项
- 在读取输入时,使用
while(cin)
替代while(1)
来自动处理 EOF 结束输入。 - 在创建二叉树时,注意
NULL
节点的处理。 - 在计算深度时,使用
max
函数比较左右子树的深度,需要包含<algorithm>
头文件。 - 在销毁二叉树时,确保递归调用正确,避免内存泄漏。
AC代码
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
typedef char TElemType;
//二叉树的二叉链表存储表示
typedef struct BiTNode {
TElemType data; //结点数据域
struct BiTNode *lchild, *rchild; //左右孩子指针
} BiTNode, *BiTree;
void CreateBiTree(BiTree &T)
{
//按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T
TElemType ch;
//此处和教材的不同是,要处理多组数据,输入ch如果遇到EOF,应该结束程序
//所以main函数用while(1)
if(!(cin >> ch)) exit(0);
/****在此下面完成代码***************/
if(ch=='#')T=NULL;//依据题意为"#"代表为空树直接让这个节点为NULL
else//不是空树
{
T=new BiTNode;//让T指向一个空间储存数据
T->data=ch;
CreateBiTree(T->lchild);//先序遍历要求先根后左右子树,已经扫了根,则往左扫
CreateBiTree(T->rchild);//扫
}
/***********************************/
} //CreateBiTree
//用算法5.5 计算二叉树的深度
int Depth(BiTree T)
{
//计算二叉树T的深度
/****在此下面完成代码***************/
int m,n;
if(T==NULL)return 0;
else
{
m=Depth(T->lchild);
n=Depth(T->rchild);
if(m>n)return(m+1);
else return(n+1);
}
/***********************************/
}
void DestroyBitree(BiTree& T)
{
/****在此下面完成代码***************/
if(T)
{
if(T->lchild)DestroyBitree(T->lchild);
if(T->rchild)DestroyBitree(T->rchild);
free(T);
T=NULL;
}
/***********************************/
}
int main()
{
BiTree tree;
while(1) {
CreateBiTree(tree);
cout << Depth(tree);
cout << endl;
DestroyBitree(tree);
}
}