本文的主要内容是针对二叉树这种数据结构的实现细节进行设计与分析，理论与实践相结合可以加深对系统知识的掌握。二叉树这种数据结构，应用非常广泛，在linux内核中随处可见，因此，如果能够熟练的掌握这项技能，将有助于理解其它系统。

　　一、“初识”二叉树

　　在代码的实现中，二叉树究竟是什么 请看下面代码：

　　[cpp]

　　/*

　　* filename: bitree.h

　　* author: zhm

　　* date: 2012-01-08

　　*/

　　#ifndef BITREE_H

　　#define BITREE_H

　　#include

　　/* define a binary tree node */

　　typedef struct BiTreeNode_

　　{

　　void *data;

　　struct BiTreeNode_ *left; //point to left node.

　　struct BiTreeNode_ *right; //point to right node.

　　}BiTreeNode;

　　这是一段关于二叉树结点的数据结构，一共有3个域，数据域和左右指针域，数据域包含了二叉树每个结点的关键信息，左右指针域分别指向它的左右孩子结点。

　　[html]

　　/* define a binary tree */

　　typedef struct BiTree_

　　{

　　int size; //number of the elements in the tree.

　　BiTreeNode *root; //root node.

　　int (*compare)(const void *key1, const void *key2);

　　void (*destroy)(void *data);

　　}BiTree;

　　这里定义了一个结构体，这个结构体就是一棵二叉树了。因为它维护了一棵二叉树的重要信息，如，二叉树中结点总数size，根结点的位置root，结点数据信息的比较操作，销毁二叉树的destroy函数等。可以通过这个结构体的root域就可以方便的按深度及广度遍历整个二叉树，寻找到任何一个结点了。