树

如果单向线性链式物理结构中每个结点
可以找到多个其他结点就成为了树
树里的所有结点可以分成几层，不同层
之间符合线性规律(任意两层之间
有前后顺序)
树的最上面一层应该只有一个结点，这个
结点叫做树的根结点
根结点可以用来代表整棵树
如果树里两个结点之间有直接联系，这种联系
叫做父子关系。其中靠近根结点的叫做
父结点，另外一个结点叫子结点。
任何结点最多有一个父结点（根结点没有父
结点）
如果任何一个结点最多只有两个子结点则
这种树叫做二叉树
二叉树是最简单的树
二叉树中某个结点的两个子结点分别叫做它的
左子结点和右子结点
二叉树里任何结点都可以作为根结点代表
一棵二叉树
一个结点左子结点代表的树叫做这个结点的
左子树，右子结点代表的树叫做它的右
子树

树的操作大多数都是通过遍历实现的
通常采用递归函数实现树的遍历
遍历的时候左子树一定在右子树前面处理
先处理根结点的遍历方式叫前序遍历
在两个子树之间处理根结点的遍历方式叫
中序遍历
在最后处理根结点的遍历方式叫后序遍历

/*
    二叉树演示
*/
#ifndef    __02TREE_H__
#define    __02TREE_H__
struct node;
typedef struct {
    struct node *p_node;
} tree;
typedef struct node {
    int num;
    tree left;
    tree right;
} node;
//初始化函数
void tree_init(tree *);
//清理函数
void tree_deinit(tree *);
//在有序二叉树里查找某个数字所在的位置
tree *tree_search_in_order(const tree *, int );
//在有序二叉树里插入新数字
void tree_insert_in_order(tree *, int );
//中序遍历函数
void tree_miter(tree *, void (*)(int));
//前序遍历函数
void tree_fiter(tree *, void (*)(int));
//后序遍历函数
void tree_liter(tree *, void (*)(int));
//从有序二叉树里删除数字的函数
void tree_remove(tree *, int);
#endif        //__02TREE_H__







/*
    二叉树演示
*/
#include <stdlib.h>
#include "02tree.h"
//初始化函数
void tree_init(tree *p_tree) {
    p_tree->p_node = NULL;
}
//清理函数
void tree_deinit(tree *p_tree) {
    if (!(p_tree->p_node)) {
        return ;
    }
    tree_deinit(&(p_tree->p_node->left));
    tree_deinit(&(p_tree->p_node->right));
    free(p_tree->p_node);
    p_tree->p_node = NULL;
}
//在有序二叉树里查找某个数字所在的位置
tree *tree_search_in_order(const tree *p_tree, int num) {
    if (!(p_tree->p_node)) {
        return (tree *)p_tree;
    }
    if (p_tree->p_node->num == num) {
        return (tree *)p_tree;
    }
    else if (p_tree->p_node->num > num) {
        return tree_search_in_order(&(p_tree->p_node->left), num);
    }
    else {
        return tree_search_in_order(&(p_tree->p_node->right), num);
    }
}
//在有序二叉树里插入新数字
void tree_insert_in_order(tree *p_tree, int num) {
    tree *p_tr = tree_search_in_order(p_tree, num);
    if (p_tr->p_node) {
        return ;
    }
    node *p_tmp = (node *)malloc(sizeof(node));
    if (!p_tmp) {
        return ;
    }
    p_tmp->num = num;
    p_tmp->left.p_node = NULL;
    p_tmp->right.p_node = NULL;
    p_tr->p_node = p_tmp;
}
//中序遍历函数
void tree_miter(tree *p_tree, void (*p_func)(int)) {
    if (!(p_tree->p_node)) {
        return ;
    }
    tree_miter(&(p_tree->p_node->left), p_func);
    p_func(p_tree->p_node->num);
    tree_miter(&(p_tree->p_node->right), p_func);
}
//前序遍历函数
void tree_fiter(tree *p_tree, void (*p_func)(int)) {
    if (!(p_tree->p_node)) {
        return ;
    }
    p_func(p_tree->p_node->num);
    tree_fiter(&(p_tree->p_node->left), p_func);
    tree_fiter(&(p_tree->p_node->right), p_func);
}
//后序遍历函数
void tree_liter(tree *p_tree, void (*p_func)(int)) {
    if (!(p_tree->p_node)) {
        return ;
    }
    tree_liter(&(p_tree->p_node->left), p_func);
    tree_liter(&(p_tree->p_node->right), p_func);
    p_func(p_tree->p_node->num);
}
//从有序二叉树里删除一个数字的函数
void tree_remove(tree *p_tree, int num) {
    node *p_remove = NULL, *p_left = NULL, *p_right = NULL;
    tree *p_tmp = tree_search_in_order(p_tree, num);
    if (!(p_tmp->p_node)) {
        return ;
    }
    p_remove = p_tmp->p_node;
    p_left = p_remove->left.p_node;
    p_right = p_remove->right.p_node;
    if (!p_left) {
        p_tmp->p_node = p_right;
    }
    else if (!p_right) {
        p_tmp->p_node = p_left;
    }
    else {
        tree *p_tmp1 = tree_search_in_order(&(p_remove->left), p_right->num);
        p_tmp1->p_node = p_right;
        p_tmp->p_node = p_left;
    }
    free(p_remove);
    p_remove = NULL;
}







/*
    树测试
*/
#include <stdio.h>
#include "02tree.h"
void print_cb(int num) {
    printf("%d ", num);
}
int main() {
    tree tr = {0};
    tree_init(&tr);
    tree_insert_in_order(&tr, 50);
    tree_insert_in_order(&tr, 25);
    tree_insert_in_order(&tr, 80);
    tree_insert_in_order(&tr, 13);
    tree_insert_in_order(&tr, 37);
    tree_insert_in_order(&tr, 61);
    tree_insert_in_order(&tr, 93);
    tree_insert_in_order(&tr, 7);
    tree_remove(&tr, 25);
    tree_miter(&tr, print_cb);
    printf("
");
    tree_deinit(&tr);
    return 0;
}