已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中,试编写算法建立该二叉树的二叉链表。
分两行分别输入一棵二叉树的前序序列和中序序列。
输出该二叉树的后序序列。
知识点回顾:二叉树
1、二叉树的定义 二叉树是n(n≥0)个节点的有限集合,它或者是空树(n=0),或者是有一个根节点及两颗不相交的且分别称为左、右子树的二叉树所组成。可见,二叉树同样具有递归性质。
特别需要注意的是,尽管树和二叉树的概念之间有许多联系,但它们是两个不同的概念,树和二叉树之间最主要的区别是:二叉树结点的子树要区分左子树和右子树,即使在节点只有一个子树的情况下,也要明确指出该子树是左子树还是右子树。另外,二叉树结点最大度为2,二树中不限制节点的度数。
2、二叉树的性质 (1)二叉树第i层(i≥1)上至多有个节点
(2)高度为k的二叉树之多有个节点(k≥1)
(3)对于任一颗二叉树,若其终端的节点数为,度为2的节点数为,则
(4)具有n个节点的完全二叉树的深度为
3、二叉树的存储结构 1)二叉树的顺序存储结构
用一组地址连续的存储单元存储二叉树中的节点,必须把节点排成一个适当的线性序列,并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。
2)二叉树的链式存储结构
由于二叉树的节点中包含有数据元素、左子树的根、右子树的根及双亲等信息,因此可以用三叉链表或二叉链表(即一个节点含有三个指针或两个指针)来存储二叉树,链表的头指针指向二叉树的根节点。
4、二叉树的遍历 遍历二叉树的方法分别有先序遍历、中序遍历、后序遍历。
先序遍历:先遍历根节点,然后是左子树,最后是右子树;根节点->左子树->右子树
中序遍历:先遍历左子树,然后是根节点、最后是右子树;左子树->根节点->右子树
后序遍历:先遍历左子树,然后是右子树,最后是根节点;左子树->右子树->根节点
下面给出一种已知二叉树前中序,求其二叉链表的算法,递归~
前:ABDFGCEH 中:BFDGACEH 后:FGDBHECA
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 1000005
#define lb(x) (x&(-x))
const double eps = 1e-6;
using namespace std;
inline ll read()
{
char ch = getchar(); ll s = 0, w = 1;
while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
return s * w;
}
inline void write(ll x)
{
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
}
typedef struct node
{
char val;
struct node*lchild,*rchild;
}Binode,*Bitree;
inline void Print(Bitree T)
{
if(T)
{
Print(T->lchild);
Print(T->rchild);
cout<<T->val<<" ";
}
else return ;
}
char pre[maxn],mid[maxn];
inline Binode* work(ll pre_b,ll pre_e,ll mid_b,ll mid_e)
{
Bitree root=(Bitree)malloc(sizeof(Binode));
root->lchild=root->rchild=NULL;
root->val=pre[pre_b];
rg i=0;
while(mid[i]!=root->val)i++;
ll llen=i-mid_b,rlen=mid_e-i;
if(llen>0)root->lchild=work(pre_b+1,pre_b+llen,mid_b,i-1);
if(rlen>0)root->rchild=work(pre_b+llen+1,pre_e,i+1,mid_e);
return root;
}
int main()
{
Bitree T=(Bitree)malloc(sizeof(Binode));
scanf("%s%s",pre,mid);
ll len=strlen(pre);
T=work(0,len-1,0,len-1);
Print(T);
return 0;
}