Advertisement
Guest User

Untitled

a guest
Mar 20th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.74 KB | None | 0 0
  1. //
  2. // main.c
  3. // Construct_a_binary_tree
  4. //
  5. // Created by 馮謙 on 2018/3/20.
  6. // Copyright © 2018年 馮謙. All rights reserved.
  7. //
  8.  
  9. #include <stdlib.h>
  10. #include <stdio.h>
  11. typedef struct _node {
  12. int value;
  13. struct _node *left;
  14. struct _node *right;
  15. } Node;
  16.  
  17. int pre = 0;
  18.  
  19. Node *create_node(int value){
  20. Node *p = malloc(sizeof(Node));
  21. p->value = value;
  22. return p;
  23. }
  24.  
  25. void Postorder(Node *root){
  26. if (root != NULL) {
  27. Postorder(root->left);
  28. Postorder(root->right);
  29. printf("%d ", root->value);
  30. }
  31. }
  32.  
  33. void destroy(Node* root){
  34. if (root != NULL) {
  35. destroy(root->left);
  36. destroy(root->right);
  37. free(root);
  38. }
  39. }
  40.  
  41. Node *build(int *inorder, int *preorder, int inorder_start, int inorder_end){
  42. int i;
  43. for (i=inorder_start; i<=inorder_end; i++) {
  44. if (inorder[i] == preorder[pre]) {
  45. pre++;
  46. Node *root;
  47. root = create_node(inorder[i]);
  48. root->left = build(inorder, preorder, inorder_start, i-1);
  49. root->right = build(inorder, preorder, i+1, inorder_end);
  50. return root;
  51. }
  52. }
  53. return NULL;
  54. }
  55.  
  56. int main(int argc, const char * argv[]) {
  57.  
  58. int N;
  59. int i=0;
  60. scanf("%d", &N);
  61.  
  62. int inorder[N];
  63. int preorder[N];
  64.  
  65. for (i=0; i<N-1; i++) {
  66. scanf("%d ", &inorder[i]);
  67. }
  68. scanf("%d", &inorder[i]);
  69. for (i=0; i<N-1; i++) {
  70. scanf("%d ", &preorder[i]);
  71. }
  72. scanf("%d", &preorder[i]);
  73.  
  74. Node *root;
  75. root = build(inorder, preorder, 0, N-1);
  76. Postorder(root);
  77. printf("\n");
  78. destroy(root);
  79.  
  80. return 0;
  81. }
  82. /*
  83. 9
  84. 3 7 8 6 11 2 5 4 9
  85. 2 7 3 6 8 11 5 9 4
  86. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement