Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.c
- // Construct_a_binary_tree
- //
- // Created by 馮謙 on 2018/3/20.
- // Copyright © 2018年 馮謙. All rights reserved.
- //
- #include <stdlib.h>
- #include <stdio.h>
- typedef struct _node {
- int value;
- struct _node *left;
- struct _node *right;
- } Node;
- int pre = 0;
- Node *create_node(int value){
- Node *p = malloc(sizeof(Node));
- p->value = value;
- return p;
- }
- void Postorder(Node *root){
- if (root != NULL) {
- Postorder(root->left);
- Postorder(root->right);
- printf("%d ", root->value);
- }
- }
- void destroy(Node* root){
- if (root != NULL) {
- destroy(root->left);
- destroy(root->right);
- free(root);
- }
- }
- Node *build(int *inorder, int *preorder, int inorder_start, int inorder_end){
- int i;
- for (i=inorder_start; i<=inorder_end; i++) {
- if (inorder[i] == preorder[pre]) {
- pre++;
- Node *root;
- root = create_node(inorder[i]);
- root->left = build(inorder, preorder, inorder_start, i-1);
- root->right = build(inorder, preorder, i+1, inorder_end);
- return root;
- }
- }
- return NULL;
- }
- int main(int argc, const char * argv[]) {
- int N;
- int i=0;
- scanf("%d", &N);
- int inorder[N];
- int preorder[N];
- for (i=0; i<N-1; i++) {
- scanf("%d ", &inorder[i]);
- }
- scanf("%d", &inorder[i]);
- for (i=0; i<N-1; i++) {
- scanf("%d ", &preorder[i]);
- }
- scanf("%d", &preorder[i]);
- Node *root;
- root = build(inorder, preorder, 0, N-1);
- Postorder(root);
- printf("\n");
- destroy(root);
- return 0;
- }
- /*
- 9
- 3 7 8 6 11 2 5 4 9
- 2 7 3 6 8 11 5 9 4
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement