hnust 1803: 二叉树遍历1
题目描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串：
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);
/****在此下面完成代码***************/
/***********************************/
} //CreateBiTree
//用算法5.1 中序遍历的递归算法
void InOrderTraverse(BiTree T)
{
//中序遍历二叉树T的递归算法
/****在此下面完成代码***************/
/***********************************/
}
void DestroyBitree(BiTree& T)
{
/****在此下面完成代码***************/
/***********************************/
}
int main()
{
BiTree tree;
while(1) {
CreateBiTree(tree);
InOrderTraverse(tree);
cout << endl;
DestroyBitree(tree);
}
}
输入
输入包括1行字符串，长度不超过100。
输出
可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。
样例输入 Copy
a#b#cdef#####
a##
样例输出 Copy
a b f e d c
a
代码解析
这段C++代码实现了二叉树的创建、中序遍历和销毁。
1. 数据结构定义
BiTNode：定义了二叉树的节点结构，包含数据域data和指向左右孩子的指针lchild,rchild。BiTree：二叉树的类型定义，指向BiTNode的指针。
2. 函数 CreateBiTree
- 作用：根据用户输入的先序序列创建二叉树。
- 输入参数：二叉树的引用
T。 - 过程：
- 读取一个字符
ch，如果是'#'，则将T设置为NULL。 - 否则，创建一个新的节点，将
ch存储在节点的数据域中，并递归地创建左子树和右子树。
- 读取一个字符
3. 函数 InOrderTraverse
- 作用：中序遍历二叉树。
- 输入参数：二叉树
T。 - 过程：
- 如果
T不为空，先递归遍历左子树，打印当前节点的数据，然后递归遍历右子树。
- 如果
4. 函数 DestroyBitree
- 作用：销毁二叉树，释放占用的内存。
- 输入参数：二叉树的引用
T。 - 过程：
- 如果
T不为空，递归地销毁左子树和右子树，然后释放当前节点的内存，并将T设置为NULL。
- 如果
5. 主函数 main
- 声明一个
BiTree类型的指针tree。 - 使用无限循环
while(1)来创建、遍历和销毁二叉树。 - 每次循环都重新创建二叉树，然后中序遍历并打印节点数据，最后销毁二叉树。
解题过程分析
问题分析
本文将讨论如何使用C++实现二叉树的创建、遍历和销毁。二叉树是一种常见的数据结构，广泛应用于计算机科学中。在本例中，我们将使用先序遍历的方式来创建二叉树，并进行中序遍历。
创建二叉树
创建二叉树的过程是通过先序遍历实现的。先序遍历的顺序是：首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。在创建过程中，我们使用字符作为节点的值，并根据输入的 '#' 来确定空树的位置。
中序遍历
中序遍历是二叉树遍历的一种方式，其顺序是：首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。这种遍历方式可以有效地展示二叉树的结构。
销毁二叉树
由于二叉树的节点是通过动态内存分配创建的，因此在不需要二叉树时，需要手动释放每个节点占用的内存，以避免内存泄漏。
代码分解
- 数据结构定义：定义了二叉树节点的结构
BiTNode和二叉树类型BiTree。 - 创建函数：
CreateBiTree函数使用递归方法根据先序输入创建二叉树。 - 遍历函数：
InOrderTraverse函数使用递归方法实现中序遍历。 - 销毁函数：
DestroyBitree函数使用递归方法销毁二叉树，释放所有节点的内存。 - 主函数：在
main函数中，使用无限循环来不断创建、遍历和销毁二叉树。
总结
本文通过一段C++代码，展示了如何创建、遍历和销毁二叉树。这种技术在数据结构和算法的学习中非常重要。通过实现这些基本操作，我们可以更好地理解二叉树的性质和应用。
注意事项
- 在读取输入时，要注意处理文件结束（EOF）的情况。
- 在创建二叉树时，确保正确处理空树的情况。
- 在销毁二叉树时，要确保所有节点的内存都被正确释放。
- 使用递归方法时，要注意避免栈溢出的风险，尤其是在处理大型数据结构时。
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.1 中序遍历的递归算法
void InOrderTraverse(BiTree T)
{
//中序遍历二叉树T的递归算法
/****在此下面完成代码***************/
if(T)
{
InOrderTraverse(T->lchild);
cout<<T->data<<" ";
InOrderTraverse(T->rchild);
}
/***********************************/
}
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);
InOrderTraverse(tree);
cout << endl;
DestroyBitree(tree);
}
}
