首頁猿問請問在先序中序建立二叉樹，該怎么實現(xiàn)？

請問在先序中序建立二叉樹，該怎么實現(xiàn)？

Redis 數(shù)據(jù)結(jié)構(gòu)

烙印99 2022-06-17 18:11:52

1二叉樹中存儲的數(shù)據(jù)范圍僅限于26個英文字母2程序要提示用戶從鍵盤分別輸入二叉樹的先序和中序序列，接受輸入后，調(diào)用相應(yīng)的函數(shù)完成二叉樹的創(chuàng)建3成功創(chuàng)建二叉樹后，程序自動輸出該二叉樹的后序遍歷次序#include<stdio.h>#include<stdlib.h>#include<string.h>#define size 100typedef struct JD{char data;struct JD *lchild,*rchild;}BiTree;int Search(char ino[],char ch){int i=0;//puts(ino)while(ino[i]!=ch&&ino[i])i++;if(ino[i]==ch)return i;elsereturn -1;}void CrtBT(BiTree *T, char pre[], char ino[], int ps, int is, int n ) /*已知pre[ps..ps+n-1]為二叉樹的先序序列,ino[is..is+n-1]為二叉樹的中序序列,本算法由此兩個序列構(gòu)造二叉鏈表*/{int k;if (n==0) T=NULL;else{k=Search(ino, pre[ps]);/*在中序序列中查詢*/if (k== -1) {T=NULL;puts("錯誤！??！\n");}else{T= (BiTree*)malloc(sizeof(BiTree));if (T==NULL) exit(1);T->data = pre[ps];if (k==is) T->lchild = NULL;elseCrtBT(T->lchild ,pre ,ino ,ps+1 ,is ,k-is );if (k=is+n-1) T->rchild = NULL;elseCrtBT(T->rchild, pre, ino, ps+1+(k-is), k+1, n-(k-is)-1 );}}} /* end CrtBT */void postorder(BiTree *t)//遞歸先序遍歷{if(t!=NULL){ printf("%c\t",t->data);postorder(t->lchild);postorder(t->rchild);}}void main(){char pre[size],ino[size];int ps,is,n;BiTree *T=NULL;puts("enter:");scanf("%s",pre);scanf("%s",ino);CrtBT(T,pre,ino,0,0,strlen(pre));postorder(T);getchar();}修改或者新程序都可以

查看完整描述

2 回答

繁花如伊

TA貢獻(xiàn)2012條經(jīng)驗獲得超12個贊

#include<stdio.h>
#include<stdlib.h>
#define size 100
typedef struct node//定義結(jié)點
{
char data;
struct node *lchild,*rchild;
} JD,*BitTree;
int search(char ino[],char pre)//在中序序列中查找先序中該元素所在位置
{
int i=0;
while(ino[i]!=pre&&ino[i])
i++;
if(ino[i]==pre)
return i;
else
return -1;
}
void CrtBT(BitTree &T,char pre[],char ino[],int ps,int is,int n)/*遞歸算法構(gòu)造函數(shù)，建立二叉鏈表*/
{
int k;
if(n==0)
T=NULL;
else
{
k=search(ino,pre[ps]);
if(k==-1)
puts("error!");
else
{
T=(JD*)malloc(sizeof(JD));
T->data=pre[ps];
if(k==is)
T->lchild=NULL;
else
CrtBT(T->lchild,pre,ino,ps+1,is,k-is);
if(k==is+n-1)
T->rchild=NULL;
else
CrtBT(T->rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);
}
}
}
//先序遍歷
void PreOrder(BitTree T)
{
if(T)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍歷
void InOrder(BitTree T)
{
if(T)
{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}

//后序遍歷(左->右->根)，
int PostOrder(BitTree T)
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
else
return 1;
}
void main()
{
char pre[size],ino[size];
puts("輸入先序序列：");
gets(pre);
puts("輸入中序序列：");
gets(ino);
BitTree T=NULL;
CrtBT(T,pre,ino,0,0,7);
printf("先序遍歷的二叉樹：");
PreOrder(T);
printf("\n");
printf("中序遍歷的二叉樹：");
InOrder(T);
printf("\n");
printf("后序遍歷的二叉樹：");
PostOrder(T);
printf("\n");
}

調(diào)試過的

反對回復(fù) 2022-06-20

回首憶惘然

TA貢獻(xiàn)1847條經(jīng)驗獲得超11個贊

參考一下吧！
程序1
#include<stdio.h>
#include<stdlib.h>
typedef struct BiT{
char data;
struct BiT *lchild;
struct BiT *rchild;
}BiT;
BiT* CreateBiTree(BiT *T) {
//構(gòu)造二叉鏈表表示的二叉樹T
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
T = (BiT *)malloc(sizeof(BiT));
T->data = ch;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return T;
}
void PreOrderTraverse(BiT *T) {
// 先序遍歷二叉樹T
if (T) {
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiT *T) {
// 中序遍歷二叉樹T
if (T) {
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiT *T) {
// 后序遍歷二叉樹T
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
void main() {
printf("先序建樹:");
BiT *T=CreateBiTree(T);
printf("\n先序遍歷:");
PreOrderTraverse(T);
printf("\n中序遍歷:");
InOrderTraverse(T);
printf("\n后序遍歷:");
PostOrderTraverse(T);
getchar();getchar();
}
來源http://zhidao.baidu.com/question/29259767.html?si=9

程序2
#define EL 10
#define TEL 2*EL+1
#define LEN sizeof(struct node)
#include "stdio.h"
#include "stdlib.h"

char pre[TEL]="ABCDEFGHIJ";
char pin[TEL]="CBEDAGHFJI";

typedef struct node
{ char data;
struct node * lch,*rch;
}BTNode,*BTree;
BTNode root;
BTree rt=&root;

int pos(char c,char s[],int st)
{char *p;
p=s+st;
while(*p!=c && *p!='\0') p++;
return p-s;
}

void create(BTree *t,int i1,int i2,int len)
{int r,llen,rlen;
if(len<=0) *t=NULL;
else
{*t=(BTree)malloc(LEN);
(*t)->data=pre[i1];
r=pos(pre[i1],pin,i2);
llen=r-i2;
rlen=len-(llen+1);
create(&(*t)->lch,i1+1,i2,llen);
create(&(*t)->rch,i1+llen+1,r+1,rlen);
}
}

void travel(BTree t)
{if(t)
{travel(t->lch);
travel(t->rch);
putchar(t->data);
}
}

int main()
{create(&rt,0,0,EL);
if(rt) travel(rt);
}