作者 张鏖烽
单位 湖南工程学院
(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(")");
}
}
}


![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
![打卡信奥刷题(3678)用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108053830-6af00ad6bdf8d-220x150.png)

