1.红黑树简介 1.1 红黑树概念
红黑树(Red-Black Tree，简称R-B Tree)是一棵特殊的二叉搜索树（任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值）。
它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或者BLACK。通过对一条从根节点到NIL叶节点（指空结点或者下面说的哨兵）的简单路径上各个结点在颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似平衡的。
1.2 红黑树特征 1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。对于查找、插入、删除、最大、最小等动态操作的时间复杂度为O(lgn).常见的用途有以下几种：
STL（标准模板库）中在set map是基于红黑树实现的。
epoll在内核中的实现，用红黑树管理事件块。
linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
2. 红黑树C语言实现 2.1 树形结构基本实现红黑树属于特殊的查找树，因此先对树形结构进行基本讲解。
首先，树形结构有各个节点组成，节点的描述如下：
struct BTNode{ int data； }；
节点需要有自己的左右子孩子，因此需要两个指针
typedef struct BTNode{ int data； struct BTNode *lChild； struct BTNode *rChild； }BiNode;
对二叉树进行创建
//先序创建
int CreateBiTree(BiTNode **T)
{
int ch;
scanf("%d",&ch);
if (ch == -1)
{
*T = NULL;
return 0;
}
else
{
*T = (BiTNode *)malloc(sizeof(BiTNode)); //为此节点申请内存空间，返回指针强制转换成BiNode*类型
if (T == NULL)
{
printf("failed\n");
return 0;
}
else
{
(*T)->data = ch;
printf("输入%d的左子节点：",ch);
CreateBiTree(&((*T)->lChild)); //递归方式存储左子节点数据
printf("输入%d的右子节点：",ch);
CreateBiTree((&(*T)->rChild)); //递归方式存储右子节点数据
}
}
return 1;
}
最开始时对二叉树的遍历难以理解，不过从算法中的递归角度进行理解将会简单很多。
二叉树先序遍历
void PreOrderBiTree(BiTNode *T) { if (T == NULL) { return; } else { printf("%d ",T->data); PreOrderBiTree(T->lChild); PreOrderBiTree(T->rChild); } }
二叉树中序遍历
void MiddleOrderBiTree(BiTNode *T) { if (T == NULL) { return; } else { MiddleOrderBiTree(T->lChild); printf("%d ",T->data); MiddleOrderBiTree(T->rChild); } }
二叉树后序遍历
void PostOrderBiTree(BiTNode *T) { if (T == NULL) { return; } else { PostOrderBiTree(T->lChild); PostOrderBiTree(T->rChild); printf("%d ",T->data); } }
二叉树深度计算
int TreeDeep(BiTNode *T) { int deep = 0; if (T != NULL) { int leftdeep = TreeDeep(T->lChild); int rightdeep = TreeDeep(T->rChild); deep = leftdeep >= rightdeep?leftdeep+1:rightdeep+1; //从最后节开始，递归逐步后退，每退回一个节点 深度+1 } return deep; }
二叉树叶子结点个数