二叉树的遍历

Question

二叉树的遍历是数据结构最基础的功能，二叉树的基本数据结构由一个父节点，一个左子节点和右子节点构成。

数据结构：

typedef struct TreeNode {
    void *data; // 泛型数据
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode ;

二叉树之间可以相互拼接，变成一个大的二叉树，二叉树的遍历有 4 中方法，即：前序遍历，中序遍历，后续遍历和层级遍历。

实现二叉树的遍历主要使用递归的方法，前序遍历（pre-order）即先从跟节点开始，然后到左节点，再到右节点，当遍历到子节点时，将它当作跟节点，依次递归遍历。中序遍历（in-order）即从左子节点开始，然后到跟节点，再到右子节点。后序遍历（post-order）即先从左子节点遍历，然后到右子节点，再到跟节点。因为数据是保存在跟节点，可以通过跟节点的遍历位置来记忆遍历次序。

我们用 C 语言构建一个如下图的二叉树：

用代码实现前三种遍历方法：

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

typedef struct TreeNode {

    void *data; // 泛型数据
    struct TreeNode *left;
    struct TreeNode *right;

} TreeNode ;

typedef struct String {
    char *data;
    size_t length;
} String;


void string_free(String *str) {
    free(str);
}

void tree_node_free(TreeNode *tree) {
    free(tree);
}

String *string_new(char *data) {
    String *str = malloc(sizeof(String));
    str->data = data;
    str->length = strlen(data);

    return str;
}

TreeNode *tree_node_new(void *value) {
    TreeNode *node = malloc(sizeof(TreeNode));
    node->data = value;
    node->left = node->right = NULL;

    return node;
}

void tree_insert_left(TreeNode *tree, TreeNode *node) {
    tree->left = node;
}

void tree_insert_right(TreeNode *tree, TreeNode *node) {
    tree->right = node;
}

// 先序遍历  parent -> left -> right
void front_order(TreeNode *tree) {
    if (tree != NULL) {
        String *str = tree->data;
        printf("data: %s, len: %d\r\n", str->data, str->length);
        front_order(tree->left);
        front_order(tree->right);
    }
}

// 中序遍历  left -> parent -> right
void mid_order(TreeNode *tree) {
    if (tree != NULL) {
        mid_order(tree->left);
        String *str = tree->data;
        printf("data: %s, len: %d\r\n", str->data, str->length);
        mid_order(tree->right);
    }
}

// 后序遍历  left -> right -> parent
void back_order(TreeNode *tree) {
    if (tree != NULL) {
        back_order(tree->left);
        back_order(tree->right);
        String *str = tree->data;
        printf("data: %s, len: %d\r\n", str->data, str->length);
    }
}

int main() {
    TreeNode *css_tree = tree_node_new(string_new("CSS"));
    tree_insert_right(css_tree, tree_node_new(string_new("C")));
    TreeNode *java_node = tree_node_new(string_new("Java"));
    tree_insert_left(java_node, tree_node_new(string_new("JS")));
    tree_insert_right(java_node, css_tree);
    TreeNode *go_node = tree_node_new(string_new("Go"));
    tree_insert_right(go_node, tree_node_new(string_new("Python")));
    TreeNode *php_tree = tree_node_new(string_new("PHP"));
    tree_insert_left(php_tree, java_node);
    tree_insert_right(php_tree, go_node);


    back_order(php_tree);
}