Given two arrays as a first-order traversal and a middle-order traversal, how to construct a tree?

jy2880668

Given two arrays as a first-order traversal and a middle-order traversal, how to construct a tree?

typedef struct node {
  int i;
  struct node* lchild, rchild;
} node, * tree;

. . . Excuse you.

哈哈大侠

Take a look at the data structure book, there seems to be the one from Tsinghua University

jy2880668

Nothing inside! !

stoneboy4000

The result is not unique, just like the problem of the stacking and unstacking order of an array, as long as it can be eliminated.

clarkr

If it is an array, why not use subscripts but use pointers struct node* lchild, rchild?


Pre-order traversal and middle-order traversal are different access methods when outputting, which can be implemented by recursion or stack
How to construct the tree is not necessarily related to the access method

maloneliu

LZ may confuse the logical data structure with the physical implementation. What we are talking about here should be the logical data structure, and its internal physical implementation can be completely different, it can be a chain structure, an array structure, or other data structures. The data structure here is more ADT.
Asclarkrsaid, how to construct a tree is not necessarily related to the access method. But for a complete binary tree, we use an array to implement it, you can think about the specific reasons for yourself :)

rbjojo

Pre-order traversal, middle-order traversal, and post-order traversal are the access methods of binary trees. Binary trees are constructed by linked lists. Look at the data structure book, there must be some

zjwzjw

A classic problem in binary trees is that given the pre-order traversal sequence and middle-order traversal sequence of a given binary tree, find the subsequent traversal sequence. It is easier to solve with the idea of ​​recursion. code show as below:
/*
a is the preorder sequence
b is the in-order sequence
The subsequent sequence will be saved in c
*/
void PostOrder(const char a[], const char b[], char c[], int starta, int startb, int startc, int len)
{
if(len==0) return;
if(len==1) {c[startc] = a[starta]; return;}

c[startc+len-1] = a[starta];//Handle tree root

int i = startb;
while(b[i]!=a[starta]) ++i;
int leftlen = i-startb;
int rightlen = len-leftlen-1;
PostOrder(a,b,c,starta+1,startb,startc,leftlen);//Construct the PostOrder of the left subtree
PostOrder(a,b,c,starta+leftlen+1,startb+leftlen+1,startc+leftlen,rightlen);//Construct the PostOrder of the right subtree
}

void PostOrder(const char a[], const char b[], char c[])
{
int len ​​= strlen(a);
PostOrder(a,b,c,0,0,0,len);
c[len] = '\0';
}

Among them is the process of construction,
You can study it. . . . . . .

jy2880668

Thankszjwzjw, and everyone else!