struct/treeGenerateFromTraversals.c at main · Quartz1605/struct · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<stdio.h>
#include<stdlib.h>

typedef struct Node{

  int data;
  struct Node* left;
  struct Node* right;

}Node;

Node* createNode(int data){

  Node* node = (Node*)malloc(sizeof(Node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return node;

}

int preIndex = 0;


int findIndex(int inorder[],int start,int end,int n){

  for(int i=start;i<=end;i++){

    if(inorder[i] == n) return i;

  }

  return -1;

}


Node* buildTree(int preorder[],int inorder[],int start,int end){


  if(end < start) return NULL;

  int val = preorder[preIndex++];


  Node* node = createNode(val);

  if(start == end) return node;

  int pos = findIndex(inorder,start,end,val);

  node->left = buildTree(preorder,inorder,start,pos-1);
  node->right = buildTree(preorder,inorder,pos+1,end);

  return node;

}

void postorder(Node* root){


  if(root != NULL){


    postorder(root->left);
    postorder(root->right);
    printf("%d ",root->data);

  }

}


int main() {

    int n;
    int inorder[] = {4,2,5,1,6,3,7};
    int preorder[] = {1,2,4,5,3,6,7};

    Node* root = buildTree(preorder, inorder, 0, 6);


    postorder(root);
    printf("\n");

    return 0;
}