今天介绍二叉树，主要介绍c的代码实现，更多关于二叉树的概念，大家可以百度或者看书。
先介绍二叉树的存储结构
typedef struct node { int data; struct node * left; struct node * right; } Node; typedef struct tree { Node * root; } Tree;
Node节点的data是数据域，left，right是指针域。
Tree节点里只记录了root，也就是根。当然可以增加一些其他信息。
先说查找操作，因为之后的很多函数都会用。
//这个结构体是为了方便插入删除操作，child是找到的节点，parent是父节点 typedef struct pair { Node * parent; Node * child; } Pair;
这个结构体主要是为了删除操作使用的，因为删除时我们要知道删除节点的父亲。而插入操作只要找到插入位置就可以了。
static Pair search_node(Tree * tree, const int key) { Pair pair; pair.parent = NULL;//parent一直是child的父节点 pair.child = tree->root; while ( pair.child != NULL ) { if ( pair.child->data > key )//如果当前结点的值大于key，则向左查找 { pair.parent = pair.child; pair.child = pair.child->left; } else if ( pair.child->data < key )//如果当前节点的值小于key，则向右查找 { pair.parent = pair.child; pair.child = pair.child->right; } else//如果相等，直接返回Pair结构体，结构体中的child就是找到的结点 { return pair; } } return pair; }
这个函数会返回一个pair结构体
如果找到关键字节点。child指向该节点，parent是该节点的父亲。
否则，child为NULL，parent是child的父亲节点。（如果是插入操作，parent的左孩子或者右孩子就是插入位置）
插入操作。
void t_insert(Tree * tree, const int data) { Pair pair; pair = search_node(tree, data);//找到要插入的位置 if ( pair.parent == NULL )//第一次插入 tree->root = make_node(data); else if (pair.child != NULL)//是否存在该节点 return;//存在则插入失败 else { if ( pair.parent->data > data)//根据新节点与父节点的比较，决定新节点的插入位置 pair.parent->left = make_node(data); else pair.parent->right = make_node(data); } }
因为我们已经实现了查找功能。所以插入变的非常容易。先判断是不是根节点，再判断是否存在该元素。最后就是根据元素的大小判断插入位置。（这里不是必须左孩子比右孩子小）
查找函数就不介绍了。只是调用了search_node函数。
接下来介绍删除操作。
相比较插入而言，删除操作有点难度，但难度并不大。
首先要找到删除节点。然后将他的孩子连接到父亲上，释放删除节点内存就OK了。
这里分两种情况。删除节点有左右孩子，和只有一个孩子或者没有孩子。
一个孩子或者没有孩子的情况好处理，只要把这个孩子的父亲变成删除节点的父亲就可以了。
如果删除节点的有两个孩子。我们可以把左孩子的父亲变成右孩子的子树中最小的值。（右孩子的左子树的左子树…）
根据我们之前的对插入操作，我们可以知道，以某一节点为根，这棵树上的最小值一定是他的左子树的左子树…（while ( current->left != NULL ) current = current->left;）
当然这里还有其他 方法，稍后会介绍一种叫替换的方法。里面涉及到删除点和真正的删除点。他是红黑树里使用的删除方法。
void t_remove(Tree * tree, const int key)
{
Pair pair = search_node(tree, key);
Node * current;
if ( pair.child == NULL )//没有找到关键字
return;
if ( pair.child->left && pair.child->right )
{
current = pair.child->right;
while ( current->left != NULL )//找到删除节点左孩子的新位置
current = current->left;
current->left = pair.child->left;
if ( pair.parent )
{
if ( pair.parent->left == pair.child )
pair.parent->left = pair.child->right;
else
pair.parent->right = pair.child->right;
}
else
tree->root = pair.child->right;
}
else
{
if ( pair.parent )
{
if ( pair.child->left )//只有左孩子
{
if ( pair.parent->left == pair.child )
pair.parent->left = pair.child->left;
else
pair.parent->right = pair.child->left;
}
else//右孩子或者没有孩子
{
if ( pair.parent->left == pair.child )
pair.parent->left = pair.child->right;
else
pair.parent->right = pair.child->right;
}
}
else
{
if ( pair.child->left )
tree->root = pair.child->left;
else
tree->root = pair.child->right;
}
}
free(pair.child);
最后是二叉树的遍历
static void treaverse_node(Node * current, void (*func)(Node * current)) { if ( current == NULL ) return; else//递归，中序遍历二叉树 { treaverse_node(current->left, func); func(current); treaverse_node(current->right, func); } }
前序遍历：根，左，右
中序遍历：左，根，右
后序遍历：左，右，根
我们可以简单的理解成，把func放到两个递归函数的前面就是前序，中间是中序，后面是后续。
之后我还会介绍非递归的遍历算法。
源码
btree.h
#ifndef _TREE_H #define _TREE_H #define MAXDEPTH 10 typedef struct node { int data; struct node * left; struct node * right; } Node; typedef struct tree { Node * root; } Tree; void t_init(Tree * tree);//初始化 void t_insert(Tree * tree, const int data);//添加 Node* t_find(Tree * tree, const int key);//查找 void t_remove(Tree * tree, const int key);//移除 void t_treaverse(Tree * tree, void (*func)(Node * current));//遍历 void t_destroy(Tree * tree);//销毁 bool t_empty(Tree * tree);//为空 int t_depth(Tree * tree);//深度 Node* t_root(Tree * tree);//根 int t_value(Node * current);//返回值 #endif //_TREE_H
btree.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include "btree.h" //这个结构体是为了方便插入删除操作，child是找到的节点，parent是父节点 typedef struct pair { Node * parent; Node * child; } Pair; static Node* make_node(const int data);//创建 static Pair search_node(Tree * tree, const int key);//查找 static void treaverse_node(Node * current, void (*func)(Node * node));//遍历 static void destroy_node(Node * current);//销毁 static int depth_node(Node * current);//度 void t_init(Tree * tree) { tree->root = NULL; } void t_insert(Tree * tree, const int data) { Pair pair; pair = search_node(tree, data);//找到要插入的位置 if ( pair.parent == NULL )//第一次插入 tree->root = make_node(data); else if (pair.child != NULL)//是否存在该节点 return;//存在则插入失败 else { if ( pair.parent->data > data)//根据新节点与父节点的比较，决定新节点的插入位置 pair.parent->left = make_node(data); else pair.parent->right = make_node(data); } } Node* t_find(Tree * tree, const int key) { return search_node(tree, key).child; }
void t_remove(Tree * tree, const int key)
{
Pair pair = search_node(tree, key);
Node * current;
if ( pair.child == NULL )//没有找到关键字
return;
if ( pair.child->left && pair.child->right )
{
current = pair.child->right;
while ( current->left != NULL )//找到删除节点左孩子的新位置
current = current->left;
current->left = pair.child->left;
if ( pair.parent )
{
if ( pair.parent->left == pair.child )
pair.parent->left = pair.child->right;
else
pair.parent->right = pair.child->right;
}
else
tree->root = pair.child->right;
}
else
{
if ( pair.parent )
{
if ( pair.child->left )//只有左孩子
{
if ( pair.parent->left == pair.child )
pair.parent->left = pair.child->left;
else
pair.parent->right = pair.child->left;
}
else//右孩子或者没有孩子
{
if ( pair.parent->left == pair.child )
pair.parent->left = pair.child->right;
else
pair.parent->right = pair.child->right;
}
}
else
{
if ( pair.child->left )
tree->root = pair.child->left;
else
tree->root = pair.child->right;
}
}
free(pair.child);
}
void t_treaverse(Tree * tree, void (*func)(Node * current)) { assert( tree != NULL ); treaverse_node(tree->root, func); } void t_destroy(Tree * tree) { treaverse_node(tree->root, destroy_node); } bool t_empty(Tree * tree) { return tree->root == NULL; } int t_depth(Tree * tree) { depth_node(tree->root); } Node* t_root(Tree * tree) { return tree->root; } int t_value(Node * current) { assert( current != NULL ); return current->data; } static Node* make_node(const int data) { Node * node = (Node *)malloc( sizeof(Node) ); if (node == NULL) exit(0); node->data = data; node->left = NULL; node->right = NULL; return node; } static Pair search_node(Tree * tree, const int key) { Pair pair; pair.parent = NULL;//parent一直是child的父节点 pair.child = tree->root; while ( pair.child != NULL ) { if ( pair.child->data > key )//如果当前结点的值大于key，则向左查找 { pair.parent = pair.child; pair.child = pair.child->left; } else if ( pair.child->data < key )//如果当前节点的值小于key，则向右查找 { pair.parent = pair.child; pair.child = pair.child->right; } else//如果相等，直接返回Pair结构体，结构体中的child就是找到的结点 { return pair; } } return pair; } static void treaverse_node(Node * current, void (*func)(Node * current)) { if ( current == NULL ) return; else//递归，中序遍历二叉树 { treaverse_node(current->left, func); func(current); treaverse_node(current->right, func); } } static void destroy_node(Node * current) { assert( current != NULL ); free( current ); } static int depth_node(Node * current) { int m, n; if ( current == NULL )//当节点为NULL时返回０ return 0; else { m = depth_node(current->left);//计算左子树深度 n = depth_node(current->right);//计算右子树深度 if ( m > n )//返回大的子树深度 return m + 1; else return n + 1; } }
好吧，里面还有一些函数没有介绍，不过都很简单。数据结构的书上都有讲。
感谢大家的阅读，如有错误，欢迎指正。