基础知识|还原二叉树 && 根据后序和中序遍历输出先序遍历&&树的遍历
还原二叉树 给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。
输入格式:
输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。
输出格式:
输出为一个整数，即该二叉树的高度。
输入样例:
9
ABDFGHIEC
FDHGIBEAC
输出样例:
5
#include
#include
typedef struct snode * bintree;
struct snode{
bintree left,right;
};
int n;
char a[50],b[50];
bintree fact(int pmin,int min,int max)
{
bintree bt=(bintree)malloc(sizeof(struct snode));
bt->left=bt->right=NULL;
for(int i=min;
i<=max;
i++){
if(a[pmin]==b[i]){
if(i!=min) bt->left=fact(pmin+1,min,i-1);
if(i!=max) bt->right=fact(pmin+i-min+1,i+1,max);
/*pmin+i-min+1：pmin是先序排列中间节点,i-min就是左边子节点的长度，+1就是右节点的位置了.
先序排列在创建右节点时 ，右节点右边的位置可以不写*/
break;
}
}
return bt;
}
int high(bintree bt)
{
int m,a,b;
if(bt){
a=high(bt->left);
b=high(bt->right);
m=a>b?a:b;
return m+1;
}
else return 0;
}
int main()
{ scanf("%d %s %s",&n,&a,&b);
// scanf("%d",&n);
getchar();
gets(a);
gets(b);
// 这样写是错的。。。我也不知道为什么
bintree bt=fact(0,0,n-1);
printf("%d",high(bt));
return 0;
}
根据后序和中序遍历输出先序遍历 戳我点开题
本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。
输入格式:
第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。
【基础知识|还原二叉树 && 根据后序和中序遍历输出先序遍历&&树的遍历】输出格式:
在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。
输入样例:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例:
Preorder: 4 1 3 2 6 5 7
#include
#include
char a[50],b[50];
typedef struct snode * bintree;
struct snode{
int data;
bintree left,right;
};
bintree creat(int pmax,int min,int max){
bintree bt=(bintree)malloc(sizeof(struct snode));
bt->data=https://www.it610.com/article/a[pmax];
bt->left=bt->right=NULL;
for(int i=min;
i<=max;
i++){
if(a[pmax]==b[i]){
if(i!=min) bt->left=creat(pmax-(max-i)-1,min,i-1);
//pmax可以说是一个树的节点长度，max-i就是右子树的长度，相减再-1就是左子树的根节点
if(i!=max) bt->right=creat(pmax-1,i+1,max);
break;
}
}
return bt;
}
void xianxun(bintree bt){
if(bt){
printf(" %d",bt->data);
xianxun(bt->left);
xianxun(bt->right);
}
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=0;
i树的遍历 戳我点开题
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
做了两道以前的天梯赛的原题，一个堆栈，一个二叉树，都是一遍过，哈哈哈哈
另外感觉自己写代码有层次了，还是挺不错的
#include
#include
typedef struct snode * bintree;
struct snode{
int data;
bintree left,right;
};
typedef struct node * queue;
struct node{
bintree *data;
int front,roar;
};
int a[50],b[50];
bintree creat_bintree(int pmax,int min,int max);
void print(bintree bt);
int main()
{
int n,i;
bintree bt=(bintree)malloc(sizeof(struct snode));
scanf("%d",&n);
for(i=0;
idata=https://www.it610.com/article/a[pmax];
bt->left=bt->right=NULL;
for(int i=min;
i<=max;
i++){
if(a[pmax]==b[i]){
if(i!=min) bt->left=creat_bintree(pmax-(max-i)-1,min,i-1);
if(i!=max) bt->right=creat_bintree(pmax-1,i+1,max);
}
}
return bt;
}
void print(bintree bt)
{
if(!bt) return;
int f=0;
bintree t;
queue s=(queue)malloc(sizeof(struct node));
s->data=https://www.it610.com/article/(bintree *)malloc(sizeof(bintree)*100);
s->front=s->roar=0;
s->data[++(s->roar)]=bt;
while(s->front!=s->roar){
if(f!=0){
printf(" ");
}
else f=1;
t=s->data[++(s->front)];
printf("%d",t->data);
if(t->left)
s->data[++(s->roar)]=t->left;
if(t->right)
s->data[++(s->roar)]=t->right;
}
}
推荐阅读
- gitlab|gitlab 通过备份还原 admin/runner 500 Internal Server Error
- java中如何实现重建二叉树
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- 自我修养--基础知识
- 微信小程序基础知识
- 1-Java基础知识
- Excel基础知识-打印的那些事（上）
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 生命致简｜还原生命的本质及认知生命的极限