# Đề tài: Problems : " recover tree " with input as " preorder" and "inorder"

1.  Thành viên chính thức Ngày gia nhập
07 2010
Bài viết
37

## Problems : " recover tree " with input as " preorder" and "inorder"

For example :
We are given the input :
inorder [ ]={4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90};
preorder [ ]={25, 15, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90};
We have to reconstruct a binary tree (the above tree is binary search tree, but whatever , the algorithm works with binary search tree as well as binary tree )
1> Overview : (To give everything is clear , i )
The inorder tell us , which nodes will be the left side of the current node , and which nodes will be the right side of current node , if you know the node
For example : with root 25 , the left side : 4, 10, 12, 15, 18, 22, 24
the right side : 31, 35, 44, 50, 66, 70, 90
The inorder gives us the current node
For example : 25 is root , 15 is also the node
=> (1) From the preorder , we will have the current node
=>(2) From the inorder , we will have the right nodes and left nodes of current node
From ( 1 ) and ( 2 ) we can reconstruct a binary tree recuvisely
2> Here is the code :
#include<stdio.h>
#include<stdlib.h>
/*construct the tree type*/
typedef struct tree
{

int value; int i;
struct tree *left;
struct tree *right;
}tree;
/*Global variables using in "recover " function*/
int i=0;
tree *tmp;
/*Print the postorder of tree , to check the binary tree which has created is right or wrong*/
void traversal(tree *t)
{
if(t!=NULL)
{

traversal(t->left);

traversal(t->right);
printf("%d ",t->value);
}
}
/*create a newnode*/
tree *create(int val)
{
tree *newnode;
newnode=(tree *)malloc(sizeof(tree));
if(newnode==NULL)
return NULL;
newnode->value=val;
newnode->right=newnode->left=NULL;
return newnode;
}
/*to find the position of elements */
int find(int a[],int key,int size)
{
int i;
for(i=0;i<size;i++)
{
if(key==a[i])
return i;
}
return 0;
}
/*Here is the the function recover tree*/
int recover(tree *head,int preorder[],int inorder[],int low ,int high,int k)
{
int m;
int number;
printf("a");
if(high-low>0)/*the element is a node*/
{
number=preorder[i];
m=find(inorder,number,14);
if(m<k)
{
k=m;
}
else if(m>k)
{

k=m;
}
else
{

k=m;
}
i++;
recover(head,preorder,inorder,low,m-1,k);/*recall the function recover the tree on the left side*/
recover(head,preorder,inorder,m+1,high,k);/*recall the function recover the tree on the right side*/
}
else if(high == low)/*the element is a leaf*/
{
if(high <k)
{
i++;
}
else if (high > k)
{
i++;
}
}
}
int main ()
{
int inorder1[]={4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90};
int preorder1[]={25, 15, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90};
int preorder[]={12,9,8,6,2,1,7,5,4};
int inorder[]={8,9,2,6,1,12,5,7,4};
int k=0;
recover(head,preorder1,inorder1,0,14,7);/*0 is the lowest position of the array ,14 is higest position of the array, 7 is the root of tree*/

printf("\n");
traversal(tmp);
}
P/s: Idon't know exactly the program is correct or not , but I have tried with 3 kind of input , and they are correct . If you see anything wrong , please feedback.  Trả lời cùng với trích dẫn

2. So , if the programme work good, what is your worry ?
You need to put the code in a tag (with help of the symbol {#} and CODE =c ). It's easy to read and to find some problems.
Your code hurts my eyes >.<  Trả lời cùng với trích dẫn

3.  Thành viên chính thức Ngày gia nhập
07 2010
Bài viết
37 Nguyên bản được gửi bởi clamvn So , if the programme work good, what is your worry ?
You need to put the code in a tag (with help of the symbol {#} and CODE =c ). It's easy to read and to find some problems.
Your code hurts my eyes >.<
Sorry , the next time i wil pay more attention
p/s : I worry , because I don't know whether it can be wrong in some special cases or nnot . But , I even don't know what are the special cases lol , that's why I put this code here .  Trả lời cùng với trích dẫn

4. C Code:
1. #include<stdio.h>
2. #include<stdlib.h>
3. /*construct the tree type*/
4. typedef struct tree
5. {
6.
7. int value; int i;
8. struct tree *left;
9. struct tree *right;
10. }tree;
11. /*Global variables using in "recover " function*/
12. int i=0;
13. tree *tmp;
14. /*Print the postorder of tree , to check the binary tree which has created is right or wrong*/
15. void traversal(tree *t)
16. {
17. if(t!=NULL)
18. {
19.
20. traversal(t->left);
21.
22. traversal(t->right);
23. printf("%d ",t->value);
24. }
25. }
26. /*create a newnode*/
27. tree *create(int val)
28. {
29. tree *newnode;
30. newnode=(tree *)malloc(sizeof(tree));
31. if(newnode==NULL)
32. return NULL;
33. newnode->value=val;
34. newnode->right=newnode->left=NULL;
35. return newnode;
36. }
37. /*to find the position of elements */
38. int find(int a[],int key,int size)
39. {
40. int i;
41. for(i=0;i<size;i++)
42. {
43. if(key==a[i])
44. return i;
45. }
46. return 0;
47. }
48. /*Here is the the function recover tree*/
49. int recover(tree *head,int preorder[],int inorder[],int low ,int high,int k)
50. {
51. int m;
52. int number;
53. printf("a");
54. if(high-low>0)/*the element is a node*/
55. {
56. number=preorder[i];
57. m=find(inorder,number,14);
58. if(m<k)
59. {
62. k=m;
63. }
64. else if(m>k)
65. {
66.
69. k=m;
70. }
71. else
72. {
73.
77. k=m;
78. }
79. i++;
80. recover(head,preorder,inorder,low,m-1,k);/*recall the function recover the tree on the left side*/
81. recover(head,preorder,inorder,m+1,high,k);/*recall the function recover the tree on the right side*/
82. }
83. else if(high == low)/*the element is a leaf*/
84. {
85. if(high <k)
86. {
87. i++;
89. }
90. else if (high > k)
91. {
92. i++;
94. }
95. }
96. }
97. int main ()
98. {
99. int inorder1[]={4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90};
100. int preorder1[]={25, 15, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90};
101. int preorder[]={12,9,8,6,2,1,7,5,4};
102. int inorder[]={8,9,2,6,1,12,5,7,4};
104. int k=0;
105. recover(head,preorder1,inorder1,0,14,7);/*0 is the lowest position of the array ,14 is higest position of the array, 7 is the root of tree*/
106.
107. printf("\n");
108. traversal(tmp);
109. }
Well , i don't understand good what you want to do but i found 2 errors in the code :
1- Don't have "return" in the function "main"
2- In function recover() ,the pointer "head" isn't allocated, how can you use it ? (look in the code )

C Code:
1. if(m<k)
2. {
5. k=m;
6. }
7. else if(m>k)
8. {
9.
12. k=m;
13. }

I tried compile your code and suddenly i had the error " Segment fault ".
I don't understand how you can success compile on your computer.  Trả lời cùng với trích dẫn

5.  Thành viên chính thức Ngày gia nhập
07 2010
Bài viết
37 Nguyên bản được gửi bởi clamvn C Code:
1. #include<stdio.h>
2. #include<stdlib.h>
3. /*construct the tree type*/
4. typedef struct tree
5. {
6.
7. int value; int i;
8. struct tree *left;
9. struct tree *right;
10. }tree;
11. /*Global variables using in "recover " function*/
12. int i=0;
13. tree *tmp;
14. /*Print the postorder of tree , to check the binary tree which has created is right or wrong*/
15. void traversal(tree *t)
16. {
17. if(t!=NULL)
18. {
19.
20. traversal(t->left);
21.
22. traversal(t->right);
23. printf("%d ",t->value);
24. }
25. }
26. /*create a newnode*/
27. tree *create(int val)
28. {
29. tree *newnode;
30. newnode=(tree *)malloc(sizeof(tree));
31. if(newnode==NULL)
32. return NULL;
33. newnode->value=val;
34. newnode->right=newnode->left=NULL;
35. return newnode;
36. }
37. /*to find the position of elements */
38. int find(int a[],int key,int size)
39. {
40. int i;
41. for(i=0;i<size;i++)
42. {
43. if(key==a[i])
44. return i;
45. }
46. return 0;
47. }
48. /*Here is the the function recover tree*/
49. int recover(tree *head,int preorder[],int inorder[],int low ,int high,int k)
50. {
51. int m;
52. int number;
53. printf("a");
54. if(high-low>0)/*the element is a node*/
55. {
56. number=preorder[i];
57. m=find(inorder,number,14);
58. if(m<k)
59. {
62. k=m;
63. }
64. else if(m>k)
65. {
66.
69. k=m;
70. }
71. else
72. {
73.
77. k=m;
78. }
79. i++;
80. recover(head,preorder,inorder,low,m-1,k);/*recall the function recover the tree on the left side*/
81. recover(head,preorder,inorder,m+1,high,k);/*recall the function recover the tree on the right side*/
82. }
83. else if(high == low)/*the element is a leaf*/
84. {
85. if(high <k)
86. {
87. i++;
89. }
90. else if (high > k)
91. {
92. i++;
94. }
95. }
96. }
97. int main ()
98. {
99. int inorder1[]={4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90};
100. int preorder1[]={25, 15, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90};
101. int preorder[]={12,9,8,6,2,1,7,5,4};
102. int inorder[]={8,9,2,6,1,12,5,7,4};
104. int k=0;
105. recover(head,preorder1,inorder1,0,14,7);/*0 is the lowest position of the array ,14 is higest position of the array, 7 is the root of tree*/
106.
107. printf("\n");
108. traversal(tmp);
109. }
Well , i don't understand good what you want to do but i found 2 errors in the code :
1- Don't have "return" in the function "main"
2- In function recover() ,the pointer "head" isn't allocated, how can you use it ? (look in the code )

C Code:
1. if(m<k)
2. {
5. k=m;
6. }
7. else if(m>k)
8. {
9.
12. k=m;
13. }

I tried compile your code and suddenly i had the error " Segment fault ".
I don't understand how you can success compile on your computer.
I can explain :
1> The program doesn't work , maybe I use the different compiler (I used GCC as compiler and Emacs as editor based on Unix)
2>The function main 's not necessary return some thing , return means that the code below " return " never be touched , or in another way, " return" is the signal which announces the compiler " here , it's the end program"
For example
include<stdio.h>
int main ()
{
printf("k");
return 0;
printf("k");

}
Output: " k "
3> They are allocated ! , but in another function called "create"
For example head->left=create(5) , that means I create a node left which has the value "5"
you should reread "create " function ... Maybe it will help.
4> Another case explain why you gets "segmatation fault" , maybe you change something in my code , I means you maybe want to try whether the program is still run with other input . But Because of limited time , I just does such that it works with my input " preorder 1" and "inorder 1" ( to modify this code works in any inputs is quite easy)  Trả lời cùng với trích dẫn

6. ## Problems : " recover tree " with input as " preorder" and "inorder"

1) i work too on Unix and the version of my gcc is 4.2.1
2) You're wrong."return" is necessary, especially on Unix. It gives the signal system and to tell it that the program is working or not.
3) You don't understand the pointer. In "main" , you have declared á a pointer but you didn't allocate a memory for it. And in the function recover() , you use :
C Code:
1. if(m<k)
2. {
5. k=m;
6. }
7. else if(m>k)
8. {
9.
12. k=m;
13. }

it's impossible. Look the code on top , you make head->right, head->left but "head" doesn't exist, how it know what is its right, its left.

i saw where you make "head"
C Code:
4. k=m;

it isn't normal. if m isn't equal k (in the function recover() ), you think what is happening?

4) I change nothing your code, i have just copy and paste . when i compile it on Terminal , i received the error "Segment fault"  Trả lời cùng với trích dẫn

7.  Thành viên chính thức Ngày gia nhập
07 2010
Bài viết
37
I recompiled , and it works , I don't know why ! But may be in function " main " , You need put "head =NULL" , maybe this can solve the problem .
" But segmentation faults do not *always* happen. It depends on internal issues of how memory is laid out, etc.    Trả lời cùng với trích dẫn

8.  Thành viên chính thức Ngày gia nhập
07 2010
Bài viết
37
And about "return " , maybe I just understand how to use it, I'm a kind of person always know and learn enough for my job . So , maybe you're right
And the below attach show that this program worked  Trả lời cùng với trích dẫn

9.  Thành viên chính thức Ngày gia nhập
07 2010
Bài viết
37
Code:
```if(m<k)
{
k=m;
}
else if(m>k)
{

k=m;
}```
You maybe forget the punch of code

Code:
```	else
{
k=m;
}```
This only case that k == m, that mean the first element in preorder will be created as a root of the tree , and then other cases will be "k>m" or "k<m   Trả lời cùng với trích dẫn

10.  Thành viên chính thức Ngày gia nhập
07 2010
Bài viết
37
To solve this problem , I use 2 variable k,and m
k: is a counter variable that represent the position of "the node" in inorder , and start from the root of tree , (in my code , it's default 7 , because it's very easy to find , it's the first element of inorder , but you can replace by inorder , it's more comprehensive)
m: is also a counter variable , but it store the child node of the node " k "
For example :
Inorder 25 , 15, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90
Preorder: , 4 ,10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90
The position in array 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
number = inorder [i];
First : k= 7 , and m = 7 (Because m=find(inorder,number,14) will find where "number" is in inorder) , it reaches the case k==m , then create the root , and k=m
Second k = 7 , and m = 3 it reach the case m<k , create the left node of the root , and k = m
continue do this , Then we will have the result
"it isn't normal. if m isn't equal k (in the function recover() ), you think what is happening?"
It's always equal, because I modify everything such that it work as my wish , but if you see anything wrong , please feedback . Welcome!  Trả lời cùng với trích dẫn

#### Quyền hạn của bạn

• Bạn không thể gửi đề tài mới
• Bạn không thể gửi bài trả lời
• Bạn không thể gửi các đính kèm
• Bạn không thể chỉnh sửa bài viết của bạn