C 算法精介绍---二叉树的定义和介绍
前面对二叉树有了简单的认识，下面就先介绍下二叉树的定义和分析（以下是自己对函数分析）：值得一说的就是在bitree_ins_left（）函数中定义的二级指针position的使用。如何不是在图纸上画了下，我可能还没有理解用法。这个可能需要修改下，更容易理解。
/*bitree.h*/#ifndef BITREE_H#define BITREE_H#include <stdlib.h>/*为节点定义二叉树结构体*/typedef struct BiTreeNode_ { void *data;/*存放数据*/ struct BiTreeNode_ *left;/*左孩子*/ struct BiTreeNode_ *right;/*右孩子*/}BiTreeNode; /*定义二叉树结构体*/typedef struct BiTree_ { int size;/*存放数据个数*/ int (*compare) (const void *key1,const void *key2);/*预留的一个接口*/ void (*destroy)(void *data);/*封装的析构函数，作用是释放data空间*/ BiTreeNode *root;/*指向根节点的一个指针*/}BiTree;/*函数接口*/void bitree_init(BiTree *tree, void (*destroy)(void *data));void bitree_destroy(BiTree *tree);int bitree_ins_left(BiTree *tree,BiTreeNode *node,const void *data);int bitree_ins_right(BiTree * tree, BiTreeNode * node, const void * data);void bitree_rem_left(BiTree *tree,BiTreeNode *node);void bitree_rem_right(BiTree * tree, BiTreeNode * node);int bitree_merge(BiTree *merge,BiTree *left,BiTree *right,const void *data);#define bitree_size(tree) ((tree) -> size)#define bitree_root(tree) ((tree) -> root)/*node标识是树的分子结束*/#define bitree_is_eob(node) ((node) == NULL)/*判断是不是叶子结点*/#define bitree_is_leaf(node) ((node)->left == NULL && (node) ->right == NULL)#define bitree_data(node) ((node) ->data)#define bitree_left(node) ((node)->left)#define bitree_right(node) ((node)->right)#endif
/*bitree.c*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include "../include/bitree.h"/*二叉树初始化*/void bitree_init(BiTree * tree, void(* destroy)(void * data)){ tree ->size = 0; tree ->destroy = destroy; tree ->root = NULL; return ;}/*二叉树销毁*/void bitree_destroy(BiTree * tree){ /*从二叉树中移除所有的节点*/ bitree_rem_left( tree, NULL); memset(tree,0,sizeof(BiTree); return;}/* 将节点插入到二叉树中，插入到有参数指定节点的左子树 *如果节点为空，且树为空树，就是讲此节点设为root * return 成功返回0，失败-1 */int bitree_ins_left(BiTree * tree, BiTreeNode * node, const void * data){ BiTreeNode *new_node,**position; /*判断该插入到那个节点*/ if (node == NULL){ /*当node==NULL，说明是根节点，但是如果树不为空，则出错返回-1*/ if (bitree_size(tree) > 0){ return -1; } /*这个意思是position指向根节点*/ position = &tree ->root; } else { /*判断node节点左孩子是否为空*/ if (bitree_left(node) != NULL){ return -1; } position = &node->left; } /*申请node空间保存data*/ if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL) return -1; /*将节点插入到二叉树中*/ new_node ->data = (void *)data; new_node ->left = NULL; new_node ->right = NULL; tree->size ++; return 0;}/*将节点插入到二叉树中，插入到有参数指定节点的右子树 *如果节点为空，且树为空树，就是讲此节点设为root * return 成功返回0，失败-1 */ int bitree_ins_right(BiTree * tree, BiTreeNode * node, const void * data){ BiTreeNode *new_node,**position; /*判断该插入到那个节点*/ if (node == NULL){ /*当node==NULL，说明是根节点，但是如果树不为空，则出错返回-1*/ if (bitree_size(tree) > 0){ return -1; } /*这个意思是position指向根节点*/ position = &tree ->root; } else { /*判断node节点左孩子是否为空*/ if (bitree_right(node) != NULL){ return -1; } position = &node->right; } /*申请node空间保存data*/ if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL) return -1; /*将节点插入到二叉树中*/ new_node ->data = (void *)data; new_node ->left = NULL; new_node ->right = NULL; *position = new_node; tree->size ++; return 0;}/*移除node节点的左孩子如果node=NULL 则移除所有节点 *无返回值 */void bitree_rem_left(BiTree * tree, BiTreeNode * node){ BiTreeNode **position; /*当为空树时返回*/ if (bitree_size(tree) == 0) return; /* 决定删除那个节点*/ if (node == NULL) position = &tree ->root; else position = &node->left; /*删除这个节点*/ if (*position != NULL){ bitree_rem_left(tree, *position); bitree_rem_right(tree, *position); if (tree->destroy != NULL) tree->destroy(*position -> data); } free(*position); *position = NULL; tree->size --; }/*移除node节点的右孩子如果node=NULL 则移除所有节点 *无返回值 */void bitree_rem_right(BiTree * tree, BiTreeNode * node){ BiTreeNode **position; /*当为空树时返回*/ if (bitree_size(tree) == 0) return; /* 决定删除那个节点*/ if (node == NULL) position = &tree ->root; else position = &node->right; /*删除这个节点*/ if (*position != NULL){ bitree_rem_left(tree, *position); bitree_rem_right(tree, *position); if (tree->destroy != NULL) tree->destroy(*position -> data); } free(*position); *position = NULL; tree->size --; }/*合并二叉树*/int bitree_merge(BiTree * merge, BiTree * left, BiTree * right, const void * data){ /*初始化merger*/ bitree_init(merge, left->destroy); /*如何插入失败则返回-1*/ if (bitree_ins_left(merge, NULL, data) != 0){ bitree_destroy(merge); return -1; } bitree_root(merge)->left = bitree_root(left); bitree_root(merge)->right = bitree_root(right); merge->size += bitree_size(left) + bitree_size(right); left ->root = NULL; left->size = 0; right->root = NULL; right ->size = 0; return 0; }