请问二叉树前、中、后遍历后要用括号表示法输出；那关于主函数该怎么写？

Question

一、给定二叉树如下图所示，编程完成下列要求：1、用二叉链存储结构将其生成一棵二叉树；2、分别用三种遍历算法将二叉树的遍历序列输出；3、用括号表示法输出二叉树。GDBEA C FH上面是个图。。。由于我分不多了，所以不是很多。但是我很想学这方面知识，到时我有分了再给你叫啊。高手帮忙啊。我把图详细说下。A是树根；B、C分别是A的左右孩子；D、E分别是B的左右孩子；G是D的右孩子；F是C的右孩子；H是F的左孩子。相信我已经表达清楚了吧。谢谢各位大虾了。

Answer 1

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

//using namespace std;

typedef struct BiTNode {

char data;

struct BiTNode *Lchild, *Rchild; // 左、右孩子指针

} *BiTree;

void CreateBiTree(BiTree &T){

以B为根节点的左子树 A根节点 以C为根节点的右子树

以D为根节点的左子树 B根节点 以E为根节点的右子树

以G为根节点的左子树 D根节点 以H为根节点的右子树

以K为根节点的左子树 C根节点 以F为根节点的右子树

以I为根节点的左子树 F根节点 右子树为空

左子树为空 I根节点 以J为根节点的右子树

扩展资料：

主函数的两个形参形式中的形参，允许从执行环境中传递任意的多字节字符串（它们通常被称为命令行参数），各个指针 argv[1] .. argv[argc-1] 指向每个这些字符串的第一个字符。argv[0] 是指向一个表示用于执行该程序自身的名字的空结尾多字节字符串（或者当执行环境不支持时，为空字符串 ""）的开头字符的指针。

这些字符串是可以改动的，虽然对它们的改动并不会被传回给执行环境：比如可以用 std::strtok 来使用它们。由 argv 所指向的数组的大小至少为 argc+1，其最后一个元素 argv[argc] 保证为一个空指针。

Answer 2

#include
<iostream>
using
std::cin;
using
std::cout;
using
std::endl;
//using
namespace
std;
typedef
struct
BiTNode
{
char
data;
struct
BiTNode
*Lchild,
*Rchild;
//
左、右孩子指针
}
*BiTree;
void
CreateBiTree(BiTree
&T){
//
在先序遍历二叉树的过程中输入二叉树的"先序字符串"，
//
建立根指针为
T的二叉链表存储结构。在先序字符串中，
//
字符'#'表示空树，其它字母字符为结点的数据元素
char
ch;
cin
>>
ch
;
if
(ch=='#'){
T=NULL;
//
建空树
}else
{
T
=
new
BiTNode
;
//
"访问"操作为生成根结点
T->data
=
ch;
CreateBiTree(T->Lchild);
//
递归建(遍历)左子树
CreateBiTree(T->Rchild);
//
递归建(遍历)右子树
}//else
}//CreateBiTree
//先序遍历以T为根指针的二叉树
void
PreOrder(BiTree
&T){
if(T){
//
T=NULL时，二叉树为空树，不做任何操作
cout<<
T->data
<<
"
";
//
通过函数指针
*visit
访问根结点
PreOrder(T->Lchild);
//
先序遍历左子树
PreOrder(T->Rchild);
//
先序遍历右子树
}//
if
}
//中序遍历以T为根指针的二叉树
void
InOrder(BiTree
&T){
if(T){
//
T=NULL时，二叉树为空树，不做任何操作
InOrder(T->Lchild);
//
先序遍历左子树
cout<<
T->data
<<
"
";
//
通过函数指针
*visit
访问根结点
InOrder(T->Rchild);
//
先序遍历右子树
}//
if
}
//后序遍历以T为根指针的二叉树
void
PostOrder(BiTree
&T){
if(T){
//
T=NULL时，二叉树为空树，不做任何操作
PostOrder(T->Lchild);
//
先序遍历左子树
PostOrder(T->Rchild);
//
先序遍历右子树
cout<<
T->data
<<
"
";
//
通过函数指针
*visit
访问根结点
}//
if
}
//用括号表示法输出二叉树
void
DispBTree(BiTree
&bt)
{
if
(bt!=NULL)
{
cout<<bt->data;
if
(bt->Rchild!=NULL||bt->Lchild!=NULL)
{
cout<<"(";
DispBTree(bt->Lchild);
if
(bt->Rchild!=NULL)cout<<",";
DispBTree(bt->Rchild);
cout<<")";
}
}
}
int
main()
{
cout
<<
"请依次输入字符:
ABD#G##E##C#FH###"
<<
endl;
BiTree
T;
CreateBiTree(T);
cout
<<
"先序遍历:
"
<<
endl;
PreOrder(T);
cout
<<
endl
<<
"中序遍历:
"
<<
endl;
InOrder(T);
cout
<<
endl
<<
"后序遍历:
"
<<
endl;
PostOrder(T);
cout<<"\n用括号表示法输出二叉树:\n";
DispBTree(T);
cout<<endl;
return
(0);
}

Answer 3

//
中序遍历伪代码：非递归版本，用栈实现，版本2
void
inorder2(tnode*
root)
{
stack
s;
if(
root
!=
null
)
{
s.push(root);
}
while
(
!s.empty()
)
{
tnode*
node
=
s.pop();
if
(
node->bpushed
)
{
//
如果标识位为true,则表示其左右子树都已经入栈，那么现在就需要访问该节点了
visit(node);
}
else
{
//
左右子树尚未入栈，则依次将
右节点，根节点，左节点
入栈
if
(
node->right
!=
null
)
{
node->right->bpushed
=
false;
//
左右子树均设置为false
s.push(node->right);
}
node->bpushed
=
true;
//
根节点标志位为true
s.push(node);
if
(
node->left
!=
null
)
{
node->left->bpushed
=
false;
s.push(node->left);
}
}
}
}
对比先序遍历，这个算法需要额外的增加o(n)的标志位空间。另外，栈空间也扩大，因为每次压栈的时候都压入根节点与左右节点，因此栈空间为o(n)。时间复杂度方面，每个节点压栈两次，作为子节点压栈一次，作为根节点压栈一次，弹栈也是两次。因此无论从哪个方面讲，这个方法效率都不及inorder1。
后序
void
postorder(treenode
*root)
{
stack
*>
st;
treenode
*p
=
root;
treenode
*pre
=
null;//pre表示最近一次访问的结点
while(p
||
st.size()!=0)
{
//沿着左孩子方向走到最左下
。
while(p)
{
st.push(p);
p
=
p->left;
}
//get
the
top
element
of
the
stack
p
=
st.top();
//如果p没有右孩子或者其右孩子刚刚被访问过
if(p->right
==
null
||
p->right
==
pre)
{
/
isit
this
element
and
then
pop
it
cout
<<
"visit:
"
<<
p->data
<<
endl;
st.pop();
pre
=
p;
p
=
null;
}
else
{
p
=
p->right;
}
}//end
of
while(p
||
st.size()!=0)
}