| |

VerySource

 Forgot password?
 Register
Search
View: 1054|Reply: 8

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

[Copy link]

1

Threads

3

Posts

3.00

Credits

Newbie

Rank: 1

Credits
3.00

 China

Post time: 2021-3-8 16:30:01
| Show all posts |Read mode
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.
Reply

Use magic Report

0

Threads

5

Posts

5.00

Credits

Newbie

Rank: 1

Credits
5.00

 China

Post time: 2021-3-8 17:30:01
| Show all posts
Take a look at the data structure book, there seems to be the one from Tsinghua University
Reply

Use magic Report

1

Threads

3

Posts

3.00

Credits

Newbie

Rank: 1

Credits
3.00

 Korea, Republic of

 Author| Post time: 2021-3-8 17:45:01
| Show all posts
Nothing inside! !
Reply

Use magic Report

0

Threads

22

Posts

18.00

Credits

Newbie

Rank: 1

Credits
18.00

 China

Post time: 2021-3-9 09:15:01
| Show all posts
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.
Reply

Use magic Report

0

Threads

1

Posts

2.00

Credits

Newbie

Rank: 1

Credits
2.00

 China

Post time: 2021-3-9 09:45:01
| Show all posts
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
Reply

Use magic Report

0

Threads

8

Posts

9.00

Credits

Newbie

Rank: 1

Credits
9.00

 Great Britain

Post time: 2021-3-9 10:00:01
| Show all posts
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 :)
Reply

Use magic Report

0

Threads

1

Posts

2.00

Credits

Newbie

Rank: 1

Credits
2.00

 China

Post time: 2021-3-9 10:15:01
| Show all posts
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
Reply

Use magic Report

0

Threads

78

Posts

29.00

Credits

Newbie

Rank: 1

Credits
29.00

 China

Post time: 2021-3-9 10:30:01
| Show all posts
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. . . . . . .
Reply

Use magic Report

1

Threads

3

Posts

3.00

Credits

Newbie

Rank: 1

Credits
3.00

 China

 Author| Post time: 2021-3-9 12:45:01
| Show all posts
Thankszjwzjw, and everyone else!
Reply

Use magic Report

You have to log in before you can reply Login | Register

Points Rules

Contact us|Archive|Mobile|CopyRight © 2008-2023|verysource.com ( 京ICP备17048824号-1 )

Quick Reply To Top Return to the list