文章目录
问题描述reference思路code广义表方式创建二叉树总
测试用例总结注意
问题描述
广义表输入二叉树,“#”表示空树
例 A(B(D,E),C(F,#))
reference
思路
老规矩，举几个例子分析下。 创建左子树之前，要输入一个"("，遇到“，”表示输入结束 创建右子树之前，要输入一个“，”，遇到“）”表示输入结束 遇到#表示是空树。 怎么创建？递归？状态转换机？这里用状态转换机不能做吧？因为有好多节点啊，要怎么保存？那就用递归吧，不过每次还得把节点的孩子找出来，就是提取出（）中的内容来传递下去。 试着用递归来做： 所以输入的可能情况
大写字母 （ ） # ，
观察发现，每个大写字母或者#后面跟着（ ）或者， 递归结构为A(X,Y)（X,Y为子树）或者A 若是第一种结构，那么对他的左右子树进行创建，若是第二种结构， 每次递归时，先看第一个字符是什么，然后看他后面的字符是什么，这样能判断递归结构是什么，进而判断下一步怎么做。 第一个字符之后，有以下几种情况
1.( ——>说明这个递归结构是A(X,Y) 2. ，或者 ）——>说明这个递归结构是A
还有一种特殊情况就是，可能一个字母后面跟着两个符号。比如A(B(D,E),C(F,#))这样的话进行下一步之前需要把那个“，”读入，不要影响下一步。
code
广义表方式创建二叉树
void create(nodePtr
&a
)
{
char ch
;
cin
>>ch
;
if(ch
== ',')
{
cin
>>ch
;
}
if(ch
== '#')
{
a
= NULL;
return;
}
else
{
a
= new node
;
a
->ch
= ch
;
cin
>>ch
;
if(ch
== '(')
{
create(a
->left
);
cin
>>ch
;
create(a
->right
);
}
else
{
a
->left
= NULL;
a
->right
= NULL;
return;
}
}
}
总
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std
;
typedef struct node
{
char ch
;
struct node
*left
;
struct node
*right
;
}node
, *nodePtr
;
void create(nodePtr
&a
);
void destroy(nodePtr a
);
void print(nodePtr a
);
int main()
{
nodePtr a
= NULL;
create(a
);
print(a
);
}
void create(nodePtr
&a
)
{
char ch
;
cin
>>ch
;
if(ch
== '#')
{
a
= NULL;
return;
}
else
{
a
= new node
;
a
->ch
= ch
;
cin
>>ch
;
if(ch
== '(')
{
create(a
->left
);
cin
>>ch
;
create(a
->right
);
}
else
{
a
->left
= NULL;
a
->right
= NULL;
return;
}
}
}
void destroy(nodePtr a
)
{
if(a
== NULL)
{
return;
}
else
{
destroy(a
->left
);
destroy(a
->right
);
delete a
;
}
}
void print(nodePtr a
)
{
if(a
== NULL)
{
cout
<<" ";
}
else
{
cout
<<a
->ch
;
print(a
->left
);
print(a
->right
);
}
}
测试用例
总结
上面的思路边想边写的，感觉，emmm，乱七八糟，这里再写一个。 举几个例子观察一下广义表输入的特征，发现：
对每次递归的子树的结构，有两种情况，A（X,Y）和A每个大写字母后边跟着一个或者两个符号
步骤： 特殊情况：需要先判断字符是不是,，若是，则无效，需要再读一个 1.判断是不是空树。若是空树，给传入的指针赋值NULL，否则继续准备判断递归结构 2.通过该字符的下一个字符来判断递归结构。 若下一个是，或）则为A结构，赋值之后return 若下一个是(则为A(B,C)结构，需要递归创建其左子树，右子树。
注意
不要忘记给空指针赋值NULL啊！！！
