Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 17 kết quả

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

  1. #1
    Ngày gia nhập
    07 2010
    Bài viết
    37

    Mặc định 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)
    {
    head->left=create(preorder[i]);
    head=head->left;
    k=m;
    }
    else if(m>k)
    {

    head->right=create(preorder[i]);
    head=head->right;
    k=m;
    }
    else
    {

    traversal(head);
    head=create(preorder[i]);
    tmp=head;
    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++;
    head->left=create(inorder[high]);
    }
    else if (high > k)
    {
    i++;
    head->right=create(inorder[high]);
    }
    }
    }
    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};
    tree *head;
    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.

  2. #2
    Ngày gia nhập
    11 2010
    Nơi ở
    Black Hole
    Bài viết
    824

    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 >.<

  3. #3
    Ngày gia nhập
    07 2010
    Bài viết
    37

    Trích dẫn Nguyên bản được gửi bởi clamvn Xem bài viết
    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 .

  4. #4
    Ngày gia nhập
    11 2010
    Nơi ở
    Black Hole
    Bài viết
    824

    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. {
    60. head->left=create(preorder[i]);
    61. head=head->left;
    62. k=m;
    63. }
    64. else if(m>k)
    65. {
    66.  
    67. head->right=create(preorder[i]);
    68. head=head->right;
    69. k=m;
    70. }
    71. else
    72. {
    73.  
    74. traversal(head);
    75. head=create(preorder[i]);
    76. tmp=head;
    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++;
    88. head->left=create(inorder[high]);
    89. }
    90. else if (high > k)
    91. {
    92. i++;
    93. head->right=create(inorder[high]);
    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};
    103. tree *head;
    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. {
    3. head->left=create(preorder[i]);
    4. head=head->left;
    5. k=m;
    6. }
    7. else if(m>k)
    8. {
    9.  
    10. head->right=create(preorder[i]);
    11. head=head->right;
    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.

  5. #5
    Ngày gia nhập
    07 2010
    Bài viết
    37

    Trích dẫn Nguyên bản được gửi bởi clamvn Xem bài viết
    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. {
    60. head->left=create(preorder[i]);
    61. head=head->left;
    62. k=m;
    63. }
    64. else if(m>k)
    65. {
    66.  
    67. head->right=create(preorder[i]);
    68. head=head->right;
    69. k=m;
    70. }
    71. else
    72. {
    73.  
    74. traversal(head);
    75. head=create(preorder[i]);
    76. tmp=head;
    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++;
    88. head->left=create(inorder[high]);
    89. }
    90. else if (high > k)
    91. {
    92. i++;
    93. head->right=create(inorder[high]);
    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};
    103. tree *head;
    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. {
    3. head->left=create(preorder[i]);
    4. head=head->left;
    5. k=m;
    6. }
    7. else if(m>k)
    8. {
    9.  
    10. head->right=create(preorder[i]);
    11. head=head->right;
    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)

  6. #6
    Ngày gia nhập
    11 2010
    Nơi ở
    Black Hole
    Bài viết
    824

    Mặc định 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. {
    3. head->left=create(preorder[i]);
    4. head=head->left;
    5. k=m;
    6. }
    7. else if(m>k)
    8. {
    9.  
    10. head->right=create(preorder[i]);
    11. head=head->right;
    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:
    1. traversal(head);
    2. head=create(preorder[i]);
    3. tmp=head;
    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"

  7. #7
    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.

  8. #8
    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
    Attached Thumbnails Attached Thumbnails Screenshot.png  

  9. #9
    Ngày gia nhập
    07 2010
    Bài viết
    37

    Code:
    if(m<k)
    {
    head->left=create(preorder[i]);
    head=head->left;
    k=m;
    }
    else if(m>k)
    {
    
    head->right=create(preorder[i]);
    head=head->right;
    k=m;
    }
    You maybe forget the punch of code

    Code:
    	else
    { 
    	  traversal(head);
    	  head=create(preorder[i]);
    	  tmp=head;
    	  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

  10. #10
    Ngày gia nhập
    07 2010
    Bài viết
    37

    Sorry , I must to read the above reply , so forget about the previous reply about problem "head->left and head->right"
    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[0] , 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!

Các đề tài tương tự

  1. nghĩa của 3 từ "principals", "artifacts", "securables" là như thế nào?
    Gửi bởi ntbao trong diễn đàn English for IT | Tiếng anh cho dân CNTT
    Trả lời: 2
    Bài viết cuối: 02-09-2017, 06:36 PM
  2. Sự khác nhau giữa input type="text" và input type="submit" và type ="button"
    Gửi bởi tuanngocpt trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 2
    Bài viết cuối: 04-04-2012, 12:55 AM
  3. Lỗi"error C2275: 'T' : illegal use of this type as an expression" khi dùng "list<T>::iterator it"
    Gửi bởi doicanhden trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 6
    Bài viết cuối: 19-01-2012, 01:59 AM
  4. Trả lời: 1
    Bài viết cuối: 01-12-2011, 07:32 PM
  5. Trả lời: 4
    Bài viết cuối: 14-09-2011, 11:01 PM

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