要求是先用数组存储字符二叉树实现前中后遍历,然后将数组改为链表存储结构前中后序遍历
不会改变存储的方法
#include<string.h>
#include<iostream>
using namespace std;
int A = 0;
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}*BiT, BiTNode;
void preorder(char *a, int start, int end)
{
if (start<end)
{
printf("%c", a[start]);
preorder(a, 2 * start, end);
preorder(a, 2 * start + 1, end);
}
}
void midorder(char *a, int start, int end)
{
if (start<end)
{
midorder(a, 2 * start, end);
printf("%c", a[start]);
midorder(a, 2 * start + 1, end);
}
}
void lasorder(char *a, int start, int end)
{
if (start < end)
{
lasorder(a, 2 * start, end);
lasorder(a, 2 * start + 1, end);
printf("%c", a[start]);
}
}
BiT crtBT(char *a,int n)
{
char ch = a[A];
BiT bt = new BiTNode();
bt->data = ch;
A++;
bt->lchild = crtBT(a,n);
bt->rchild = crtBT(a,n);
return bt;
}
void pre(BiT bt)
{
if(bt)
{
cout<<bt->data;
pre(bt->lchild);
pre(bt->rchild);
}
}
void mid(BiT bt)
{
if (bt)
{
mid(bt->lchild);
cout << bt->data;
mid(bt->rchild);
}
}
void las(BiT bt)
{
if (bt)
{
las(bt->lchild);
las(bt->rchild);
cout << bt->data;
}
}
void main()
{
int n;
scanf("%d", &n);
char* a = new char[n + 1];//防止输入n后的回车键的干扰
for (int i = 0; i<n + 1; i++)
a[i] = getchar();
printf("前序遍历");preorder(a, 1, n + 1); printf("\n");
printf("中序遍历"); midorder(a, 1, n + 1); printf("\n");
printf("后序遍历"); lasorder(a, 1, n + 1); printf("\n");
crtBT(a, n);
BiT bt=crtBT(a,n);
pre(bt); cout << endl;
mid(bt); cout << endl;
las(bt); cout << endl;
}