说到二叉树，这可是数据结构里面的非常重要的一种数据结构，二叉树是树的一种，本身具有递归性质，所以基于二叉树的一些算法很容易用递归算法去实现。作为一种非线性结构，比起线性结构还是相对复杂的，很多人甚至看不懂算法的意思，不能理解。其实一开始接触这些东西还是挺晕的，不过你多看几遍，上机实现可能你就会觉得没那么复杂。因为你最后会发现，这些数据结构对于提高程序设计的能力有很大帮助，也是软件开发中必不可少的。
二叉树表示方法一般有两种，第一种一般是顺序存储结构，将二叉树中的节点信息存入一个一维数组中。
第二种也是比较常用的方法，用链表表示，其节点有值，左子树指针和右子树指针，有时候为了算法方便，也许会有双亲节点指针。其结构一般如下：
//BLG树的链表表示形式
typedef struct BLGNode
{
int data;//数据域
struct BLGNode *lchild;//左孩子
struct BLGNode *rchild;//右孩子
}BLGNode,* BLGTree;
这里没有用到泛型，就用了整型值作为代表。
二叉排序树也是一种二叉树，也叫做二叉搜索树，是一种动态的搜索结构，它的左子树的节点的值小于根节点的值，右子树节点的值大于根节点的值，左右子树也分别是一棵二叉排序树。它的中序遍历就是值得升序排序。所以这种树叫做排序树。
下面就是相关的实现代码，
void initBTree(struct BLGNode **bt)
{
*bt = NULL;
}
bool emptyBLGTree(BLGTree bt)
{
if (bt != NULL)
{
return true;
}
return 0;
}
int blgtreeDepth(BLGTree &bt)
{
//如果树为空,则返回0结束递归
if (NULL == bt)
{
return 0;
}
else
{
int depth1 = blgtreeDepth(bt->lchild);//左子树深度
int depth2 = blgtreeDepth(bt->rchild);//右子树深度
if (depth1 > depth2)
{
return depth1 + 1;
}
else
{
return depth2 + 1;
}
}
}
void ClearBLGTree(BLGTree *bt)
{
//
if (*bt != NULL)
{
ClearBLGTree(&((*bt)->lchild));
ClearBLGTree(&((*bt)->rchild));
free(*bt);
*bt = NULL;
}
return;
}
void preOrder(BLGTree &bt)
{
//
if (bt != NULL)
{
printf("%d\t",bt->data);
preOrder(bt->lchild);
preOrder(bt->rchild);
}
return;
}
void inOrder(BLGTree &bt)
{
if (bt != NULL)
{
inOrder(bt->lchild);
printf("%d\t",bt->data);
inOrder(bt->rchild);
}
return;
}
void postOrder(BLGTree &bt)
{
if (bt != NULL)
{
postOrder(bt->lchild);
postOrder(bt->rchild);
printf("%d\t",bt->data);
}
return;
}
int InsertBLG(BLGTree& bt,int e)
{
//为新增的一个节点分配空间
BLGNode* p = (BLGNode *)malloc(sizeof(BLGNode));
p->data = e;
p->lchild = NULL;
p->rchild = NULL;
if (bt == NULL)
{
bt = p;
return 1;
}
else
{
if (e < bt->data)
{
InsertBLG(bt->lchild,e);//插入到左子树
}
else
{
InsertBLG(bt->rchild,e);//插入到右子树
}
return 1;
}
return 0;
}
void CreateBLGTree(BLGTree& bt,int* value,int cnt)
{
int i = 0;
initBTree(&bt);//先把树根置为空
for (;i < cnt; i ++)
{
InsertBLG(bt,value[i]);
}
return;
}
上面的代码经过测试可用，如果还需要什么地方改进，大家都可以讨论。