C/C++数据结构：用递归方法建立一棵二叉树，并对该二叉树进行遍历（分别进行先序、中序、后序遍历。）

Question

如题所述

Answer 1

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>

using namespace std;

struct node;

typedef node *tree;

struct node{
char data;
tree lchild,rchild;
};

tree bt;

void build(tree &bt){
char ch;
ch=getchar();
if(ch!='.'){
bt=new node;
bt->data=ch;
build(bt->lchild);
build(bt->rchild);
}
else
bt=NULL;
}

void prework(){
ios::sync_with_stdio(false);
//freopen("data.in","r",stdin);
build(bt); //建树 
}

void preorder(tree bt){
if(bt){
cout<<bt->data;
preorder(bt->lchild);
preorder(bt->rchild);
}
}

void midorder(tree bt){
if(bt){
preorder(bt->lchild);
cout<<bt->data;
preorder(bt->rchild);
}
}

void backorder(tree bt){
if(bt){
preorder(bt->lchild);
cout<<bt->data;
preorder(bt->rchild);
}
}

void mainwork(){
preorder(bt);
cout<<endl;
midorder(bt);
cout<<endl;
backorder(bt);
}

int main(){
prework();
mainwork();
return 0;
}
//我这里输入的东西是要求叶子节点的子节点为'.'

 表示好像不太记得自己怎么打的了.....似乎不记得样例的样子.....但是思想保证是对的哈，这个程序还是可以的。

追问

运行调试中序，后序结果重复，你写代码错误
我把后序代码改成这样还是重复
void backorder(tree bt){
if(bt){
preorder(bt->lchild);
preorder(bt->rchild);
coutdata;

追答

对哦....嗯嗯，你改了就好啦

追问

改了还是不行

追答

哦？...
大概知道思想了么，递归建树就是先记录根节点再记录左子树，再是右子树。
然后前序中序后序就是分别为先根，第二根，最后根的三种遍历方法啊？
然后是不是不会输入啊......
我看看我的代码：AE...BC..D..建的树应该长成：(如果连的是空就打个.)
A
/ \
E B
/ \
C D

大概这样吧...如果还是错的就对不起啦...可能我程序就是错的

Answer 2

void BuildTree(Tree **root)
{
int value;
scanf("%d", &value);
if (value == '#')
return;
Tree *node = new Tree();
node->value = value;
node->left = NULL;
node->right = NULL;
*root = node;
BuildTree(&(node->left));
BuildTree(&(node->right));
}
void first(Tree *root)
{
if (root == NULL)
return;
printf("%d ", root->value);
first(root->left);
first(root->right);
}
void middle(Tree *root)
{

if (root == NULL)
return;
middle(root->left);
printf("%d ", root->value);
middle(root->right);
}
void after(Tree *root)
{
if (root == NULL)
return;
after(root->left);
after(root->right);
printf("%d ", root->value);
}
void main()
{
Tree *root = NULL;
BuildTree(&root);
first(root);
printf("\n");
middle(root);
printf("\n");
after(root);
printf("\n");
return 0;

}