二叉树的建立与遍历(C语言)

Question

[问题描述] 建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
[基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
[测试数据] ABCффDEфGффFффф（其中ф表示空格字符）
则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA

求编程源代码！！！！！！！！

Answer 1

楼主你好~~~“ф”字符的源代码我忘记了，我这里有一个自己写过的遍历算法
#include<iostream.h>
typedef struct btnode
{
char data;
struct btnode *Lchild,*Rchild;
}*bitreptr;

void Create(bitreptr &p)
{
char n;
p=new btnode;
cin>>n;
if(n!='#')
{
p->data=n;
Create(p->Lchild);
Create(p->Rchild);

}
else
p=NULL;

}

void preorder(bitreptr &p)
{
if(p)
{
cout<<p->data<<" ";
preorder(p->Lchild);
preorder(p->Rchild);
}
}

void midorder(bitreptr &p)
{
if(p)
{
midorder(p->Lchild);
cout<<p->data<<" ";
midorder(p->Rchild);
}
}

void postorder(bitreptr &p)
{
if(p)
{
postorder(p->Lchild);
postorder(p->Rchild);
cout<<p->data<<" ";
}
}

void change(bitreptr &p)
{
bitreptr t,q;
if(p)
{
t=p->Lchild;
q=p->Rchild;
p->Lchild=q;
p->Rchild=t;
change(p->Lchild);
change(p->Rchild);
}
}

void main()
{
char i;
cout<<"请选择所需功能（'A'输出该二叉树序列，'B'输出交换后二叉树序列)"<<endl;
cin>>i;
bitreptr p;
cout<<"输入数据：";
Create(p);
switch(i)
{
case 'A':
{
cout<<"前序:";
preorder(p);
cout<<endl;
cout<<"中序:";
midorder(p);
cout<<endl;
cout<<"后序:";
postorder(p);
cout<<endl;
}break;
case 'B':
{
change(p);
cout<<"交换二叉树前序:";
preorder(p);
cout<<endl;
cout<<"交换二叉树中序:";
midorder(p);
cout<<endl;
cout<<"交换二叉树后序:";
postorder(p);
cout<<endl;
}break;
}

}

这个算法输入时要以“#”代表空节点，及将[测试数据] “ABCффDEфGффFффф”改成“ABC##DE#G##F###”即可。另外我的算法包括了二叉树左右子树交换的代码“change(bitreptr &p)”，只要楼主稍作修改就可以得到你想要的完美结果~

Answer 2

#include <stdio.h>//头文件
#include <stdlib.h>
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}
BiTNode,*BiTree;//定义结点类型
BiTree CreateBiTree()//创建树
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}
void PreOrder(BiTree T)//先序
{
if(T!=NULL)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);

}
}
void InOrder(BiTree T)//中序
{
if(T!=NULL)
{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);

}
}
void PostOrder(BiTree T)//后序
{
if(T!=NULL)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
void main()//主函数
{
BiTree Ta;
Ta=CreateBiTree();
printf("先序遍历:");
printf("\n");
PreOrder(Ta);
printf("\n");
printf("中序遍历:");
printf("\n");
InOrder(Ta);
printf("\n");
printf("后序遍历:");
printf("\n");
PostOrder(Ta);
}本回答被提问者采纳

Answer 3

Answer 4

楼主你好~~~“ф”字符的源代码我忘记了，我这里有一个自己写过的遍历算法
#include
typedef
struct
btnode
{
char
data;
struct
btnode
*Lchild,*Rchild;
}*bitreptr;
void
Create(bitreptr
&p)
{
char
n;
p=new
btnode;
cin>>n;
if(n!='#')
{
p->data=n;
Create(p->Lchild);
Create(p->Rchild);
}
else
p=NULL;
}
void
preorder(bitreptr
&p)
{
if(p)
{
cout<
data<<"
";
preorder(p->Lchild);
preorder(p->Rchild);
}
}
void
midorder(bitreptr
&p)
{
if(p)
{
midorder(p->Lchild);
cout<
data<<"
";
midorder(p->Rchild);
}
}
void
postorder(bitreptr
&p)
{
if(p)
{
postorder(p->Lchild);
postorder(p->Rchild);
cout<
data<<"
";
}
}
void
change(bitreptr
&p)
{
bitreptr
t,q;
if(p)
{
t=p->Lchild;
q=p->Rchild;
p->Lchild=q;
p->Rchild=t;
change(p->Lchild);
change(p->Rchild);
}
}
void
main()
{
char
i;
cout<<"请选择所需功能（'A'输出该二叉树序列，'B'输出交换后二叉树序列)"<
cin>>i;
bitreptr
p;
cout<<"输入数据：";
Create(p);
switch(i)
{
case
'A':
{
cout<<"前序:";
preorder(p);
cout<
cout<<"中序:";
midorder(p);
cout<
cout<<"后序:";
postorder(p);
cout<
}break;
case
'B':
{
change(p);
cout<<"交换二叉树前序:";
preorder(p);
cout<
cout<<"交换二叉树中序:";
midorder(p);
cout<
cout<<"交换二叉树后序:";
postorder(p);
cout<
}break;
}
}
这个算法输入时要以“#”代表空节点，及将[测试数据]
“ABCффDEфGффFффф”改成“ABC##DE#G##F###”即可。另外我的算法包括了二叉树左右子树交换的代码“change(bitreptr
&p)”，只要楼主稍作修改就可以得到你想要的完美结果~