c++二叉树中序遍历题解（爱思创）

这是我第一次写题解

为了帮助一些像我这样的菜鸟

找到简单的题解

老师画了一棵二叉树，要求小A同学写出这棵二叉树的中序遍历的序列。

你的任务：判定小A同学写的序列 s是否正确，如果正确则输出 Right，如果错误则输出 No，同时输出正确的序列。

第一行为二叉树的节点数 n（1≤n≤26）。

后面 n 行，每一个字母为节点，后两个字母分别为其左右儿子，空节点用 # 表示。

最后一行为一个字符串 s，均由小写字母组成，长度不超过 26。

保证：

• 读入的第一个结点就是根结点。

如果小A同学的序列是正确的，则输出 Right ；

如果小A同学的序列是错误的，则输出两行：

• 第一行：No
• 第二行：正确的中序遍历的序列。

6
abc
bdi
cj#
d##
i##
j##
abdicj

No
dbiajc

这道题我们可以先写一个中序遍历程序

然后把输入的S和中序遍历后的字符串比较

如果相同输出 Right

否则输出 No 和 中序遍历的结果

我们先把二叉树和变量写好

需要结构体 左 右孩子

struct tree
{
	char lc;//左孩子 全称leftchild
	char rc;//右孩子 全称rightchild
}lt[130];//创建二叉树

然后是其他变量

char h;//输入的字符
string r,s;//r是中序遍历的字符 s是输入的字符串如题
int n;//一共几行
int i;//循环变量

变量设完后进入正题遍历部分

这里把三种遍历(先序遍历、中序遍历、后序遍历)都写上了

但是这道题我们只需要中序遍历

万一考别的遍历我们也会

void xianxu(char root)//根节点
{
	if(root=='#') return;//如果访问到空节点 返回
    cout< 
   中序遍历(按照题目稍加修改) 
   
void zhongxu(char root)
{
	if(root=='#') return;//判断是否为空
	zhongxu(lt[root].lc);//左孩子
	r+=root;//添加字符到字符串里 也可以cout< 
   后序遍历 
   
void houxu(char root)
{
	if(root=='#') return;//判断是否为空
	sm(lt[root].lc);//左孩子
	sm(lt[root].rc);//右孩子
    cout< 
   
  
 
遍历完成后
 
就是主函数部分了 
 
写完主函数就大功告成了
 
int main()
{
    int h1;//定义临时变量存储根节点
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>h;//读入二叉树
		cin>>lt[h].lc;
		cin>>lt[h].rc;
        if(i==1)
        {
            h1=h;//获取根节点
        }
	}
	cin>>s;
	zhongxu(h1);//中序遍历二叉树
	if(r==s) cout<<"Right";//判断是否先等
	else
	{
		cout<<"No"< 
完整代码: 
#include//有时会报错
using namespace std;
struct tree
{
	char lc;//左孩子 全称leftchild
	char rc;//右孩子 全称rightchild
}lt[130];//创建二叉树
char h;//输入的字符
string r,s;//r是中序遍历的字符 s是输入的字符串如题
int n;//一共几行
int i;//循环变量
void zhongxu(char root)
{
	if(root=='#') return;//判断是否为空
	zhongxu(lt[root].lc);//左孩子
	r+=root;//添加字符到字符串里 也可以cout<>n;
	for(i=1;i<=n;i++)
	{
		cin>>h;//读入二叉树
		cin>>lt[h].lc;
		cin>>lt[h].rc;
        if(i==1)
        {
            h1=h;//获取根节点
        }
	}
	cin>>s;
	zhongxu(h1);//中序遍历二叉树
	if(r==s) cout<<"Right";//判断是否先等
	else
	{
		cout<<"No"< 
题目测评: 
 
 样例通过了
 
 
 成功AC