欢迎光临
我们一直在努力

PTA 树与二叉树 3 中序+后序序列构建二叉树

作者 张鏖烽

单位 湖南工程学院

(1)根据某二叉树的后序+中序遍历序列,构建出这棵二叉树;

(2)输出二叉树bt中等于ch的结点的所有祖先结点;

(3)输出二叉树bt中所有单分支结点;

(4) 以括号表达式形式输出二叉树;

函数接口定义:

在这里描述函数接口。例如:
BTNode * CreateBT_InPost(char *post,char *in,int n);//根据二叉树的后序+中序遍历序列构造出这棵二叉树
bool Print_Ancestor(BTNode *b,char ch);//输出二叉树b中等于ch的节点的所有祖先节点
void Print_SingleChild(BTNode *b); //输出二叉树b的所有单分支结点
void DisplayBT(BTNode *b); //以括号表达式形式输出二叉链树

其中post表示后序遍历序列的开始地址,in表示中序序列的开始地址,n表示遍历序列的长度;ch表示从键盘输入的结点数据;

裁判测试程序样例:

在这里给出函数被调用进行测试的例子。例如:
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define MaxSize 100

typedef struct Node{
char data;
struct Node *lchild,*rchild;
}BTNode;

BTNode * CreateBT_InPost(char *post,char *in,int n);//根据后序+中序遍历序列创建二叉链树
bool Print_Ancestor(BTNode *b,char ch);//输出等于ch的节点的所有祖先节点
void Print_SingleChild(BTNode *b); //输出二叉树b的所有单分支结点
void DisplayBT(BTNode *b); //以括号表达式形式输出二叉链树

int main()
{ char postctr[MaxSize],Inctr[MaxSize];
char *post,*in;
char ch;
int n;
BTNode *bt;
scanf("%s",Inctr);
scanf("%s",postctr);

getchar();
scanf("%c",&ch);
post=postctr;
n=strlen(postctr);
in=Inctr;
bt=CreateBT_InPost(post,in,n);

printf("\\n二叉树的括号表达式:");
DisplayBT(bt);
printf("\\n");

if(!Print_Ancestor(bt,ch))
printf("\\n二叉树没有等于%c的节点!",ch);

printf("\\n二叉树的所有单分支节点:");
Print_SingleChild(bt);

return 0;

}

/* 请在这里填写答案 */

输入样例:

在这里给出一组输入。例如:

第1行:后序遍历序列

第2行:中序遍历序列

第3行:结点数据ch

JGDHEBKLIFCA
DJGBEHACKILF
K

输出样例:

在这里给出相应的输出。例如:

第1行:二叉树的括号表达式

第2行:二叉树中等于ch的结点的所有祖先结点

第3行:所有单分支结点

二叉树的括号表达式:A(B(D(,G(J)),E(,H)),C(,F(I(K,L))))
I F C A
二叉树的所有单分支节点:D G E C F

参考代码:

BTNode*CreateBT_InPost(char*post,char*in,int n){
if(n<=0)return NULL;
BTNode*b=(BTNode*)malloc(sizeof(BTNode));
b->data=post[n-1];
int i;
for(i=0;i<n;i++){
if(in[i]==post[n-1])break;
}
b->lchild=CreateBT_InPost(post,in,i);
b->rchild=CreateBT_InPost(post+i,in+i+1,n-i-1);
return b;
}
bool Print_Ancestor(BTNode*b,char ch){
if(!b)return false;
if(b->data==ch)return true;
if(Print_Ancestor(b->lchild,ch)||Print_Ancestor(b->rchild,ch)){
printf("%c ",b->data);
return true;
}
return false;
}
void Print_SingleChild(BTNode*b){
if(!b)return;
if((b->lchild&&!b->rchild)||(!b->lchild&&b->rchild)){
printf("%c ",b->data);
}
Print_SingleChild(b->lchild);
Print_SingleChild(b->rchild);
}
void DisplayBT(BTNode*b){
if(b){
printf("%c",b->data);
if(b->lchild||b->rchild){
printf("(");
if(b->lchild)DisplayBT(b->lchild);
if(b->rchild){
printf(",");
DisplayBT(b->rchild);
}
printf(")");
}
}
}

赞(0)
未经允许不得转载:171主机测评 » PTA 树与二叉树 3 中序+后序序列构建二叉树
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址