int LeafCount(BiTNode *T) { static int count; if (T != NULL) { if (T->lChild == NULL && T->rChild == NULL) { count++; } LeafCount(T->lChild); LeafCount(T->rChild); } return count; }
2.2 红黑树实现红黑树首先作为树的结构出现，包含了树形结构的基本特征，操作具有查找、添加、删除。在添加节点时必然导致红黑树的结构不符合红黑树规则，此时将对添加节点后的树进行旋转（左旋和右旋）以保证回复红黑树的特性。
下面将以红黑树的旋转、添加、删除进行逐步讲解。
红黑树基本节点定义
#define RED 0 // 红色节点 #define BLACK 1 // 黑色节点 typedef int Type; // 红黑树的节点 typedef struct RBTreeNode{ unsigned char color; // 颜色(RED 或 BLACK) Type key; // 关键字(键值) struct RBTreeNode *left; // 左孩子 struct RBTreeNode *right; // 右孩子 struct RBTreeNode *parent; // 父结点 }Node, *RBTree; // 红黑树的根 typedef struct rb_root{ Node *node; }RBRoot;
红黑树旋转
左旋（即上图从右到左）代码实现
static void left_rotate(RBRoot *root, Node *x) { // 设置x的右孩子为y Node *y = x->right; // 将 “y的左孩子” 设为 “x的右孩子”； // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲” x->right = y->left; if (y->left != NULL) y->left->parent = x; // 将 “x的父亲” 设为 “y的父亲” y->parent = x->parent; if (x->parent == NULL) { //tree = y; // 如果 “x的父亲” 是空节点，则将y设为根节点 root->node = y; // 如果 “x的父亲” 是空节点，则将y设为根节点 } else { if (x->parent->left == x) x->parent->left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” else x->parent->right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” } // 将 “x” 设为 “y的左孩子” y->left = x; // 将 “x的父节点” 设为 “y” x->parent = y; }
右旋（即上图从左向右）代码实现
static void rbtree_right_rotate(RBRoot *root, Node *y) { // 设置x是当前节点的左孩子。 Node *x = y->left; // 将 “x的右孩子” 设为 “y的左孩子”； // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲” y->left = x->right; if (x->right != NULL) x->right->parent = y; // 将 “y的父亲” 设为 “x的父亲” x->parent = y->parent; if (y->parent == NULL) { //tree = x; // 如果 “y的父亲” 是空节点，则将x设为根节点 root->node = x; // 如果 “y的父亲” 是空节点，则将x设为根节点 } else { if (y == y->parent->right) y->parent->right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子” else y->parent->left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子” } // 将 “y” 设为 “x的右孩子” x->right = y; // 将 “y的父节点” 设为 “x” y->parent = x; }
红黑树添加
插入操作需要保证插入数据后红黑树的基本特征不被破坏，红黑树的5个基本特征复习一下：