การท่องต้นไม้

การท่องต้นไม้คืออะไร

การท่องแบบเรียงลำดับ

void in_order(Node *root) {
    if (root == NULL) return;
    in_order(root->left);
    printf("%d ", root->value);
    in_order(root->right);
}

การท่องแบบก่อน

void pre_order(Node *root) {
    if (root == NULL) return;
    printf("%d ", root->value);
    pre_order(root->left);
    pre_order(root->right);
}

การท่องแบบหลัง

void post_order(Node *root) {
    if (root == NULL) return;
    post_order(root->left);
    post_order(root->right);
    printf("%d ", root->value);
}

รูปแบบร่วม

/* visit position decides the order:
 * pre  : VISIT, left, right
 * in   : left, VISIT, right
 * post : left, right, VISIT
 */

การท่องแบบเรียงลำดับจะแสดงค่าที่เรียงแล้ว

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7,12};
    for(int i=0;i<6;i++) root=insert(root,d[i]);
    in_order(root);
    printf("\n");
    return 0;
}

เปรียบเทียบทั้งสามลำดับ

/*        10
 *       /  \
 *      5    15
 * pre : 10 5 15
 * in  : 5 10 15
 * post: 5 15 10
 */

การท่องตามระดับ

void level_order(Node *root) {
    if (!root) return;
    Node *queue[100];
    int head = 0, tail = 0;
    queue[tail++] = root;
    while (head < tail) {
        Node *n = queue[head++];
        printf("%d ", n->value);
        if (n->left)  queue[tail++] = n->left;
        if (n->right) queue[tail++] = n->right;
    }
}

การท่องต้นไม้ขับเคลื่อนงานจริง

int sum_tree(Node *root) {
    if (root == NULL) return 0;
    return root->value
         + sum_tree(root->left)
         + sum_tree(root->right);
}

ต้นทุนของการท่องต้นไม้

ทั้งสามแบบในคราวเดียว

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }

int main(void){
    Node *root = cn(10);
    root->left = cn(5); root->right = cn(15);
    pre(root);  printf("\n");
    ino(root);  printf("\n");
    post(root); printf("\n");
    return 0;
}

ตรวจสอบอย่างรวดเร็ว

สรุปทบทวน