最近在学习Linux内核里的红黑树，发现网站上都没有一点好的实例能直观表达。参考了网上一些大神的技巧，终于在

终端上实现直观表达红黑树。

我们这次使用的红黑树代码是从Linux内核拷贝出来的：include/linux/rbtree.h 和 lib/rbtree.c

由于我们的代码是应用程序上实现的，所以要对这两个文件做一些修改：

rbtree.h：

注：注释掉两行头文件，加入offsetof和container_of的宏定义

rbtree.c：

注：注释掉头文件，加入自己改过的rbtree.h，注释掉原来所有的EXPORT_SYMBOL

接下去我们开始正式红黑树编程，这次红黑树实例是下图：

实现的代码test.c：

#include <stdio.h>
#include "rbtree.h"
#include <stdlib.h>
#include <time.h>

struct mytype {
struct rb_node node;
int key;
};

struct rb_root mytree = RB_ROOT;

/** Same as binary sort tree**/
struct mytype *my_search(struct rb_root *root, int key)
{
struct rb_node *node = root->rb_node;
struct mytype *data;
while (node) {
data = http://www.mamicode.com/container_of(node, struct mytype, node);
int result;

if(key < data->key) result = -1;
else if(key > data->key) result = 1;
else result = 0;

if (result < 0)
node = node->rb_left;
else if (result > 0)
node = node->rb_right;
else
return data;
} 
return NULL;
}

int my_insert(struct rb_root *root, struct mytype *data)
{
struct rb_node **new = &(root->rb_node), *parent = NULL;
        struct mytype *this;
/* Figure out where to put new node */
while (*new) {
this = container_of(*new, struct mytype, node);


int result;

if(this->key > data->key) result = -1;
else if(this->key  < data->key) result = 1;
else result = 0;

parent = *new;
if (result < 0)
new = &((*new)->rb_left);
else if (result > 0)
new = &((*new)->rb_right);
else
return 0;
}

/* Add new node and rebalance tree. */
rb_link_node(&(data->node), parent, new);
rb_insert_color(&(data->node), root);

return 1;
}
int array[]={13,15,11,8,17,1,6,22,25,27};    //上图所示红黑树实例

#define TAB_SIZE(array) (sizeof(array)/sizeof(array[0])) 

void padding ( char ch, int n )
{
int i;
if(n>0)
{
for ( i = 0; i < (n-1); i++ )
printf ( "%c",ch );
printf ( "--------" );
}
}

void print_node ( struct rb_node *node, int level )
{
if ( node == NULL )
{
padding ( ‘\t‘, level );
printf ( "\033[42;37m%s\033[0m\n", "null" );
}
else
{
print_node ( node->rb_right, level + 1 );
padding ( ‘\t‘, level );
if(rb_is_black(node))
{
       struct mytype *black = container_of(node, struct mytype, node);
printf ( "\033[47;30m%3d\033[0m\n", black->key );
}
else
{
       struct mytype *red = container_of(node, struct mytype, node);
printf ( "\033[41;37m%3d\033[0m\n", red->key );
}
print_node ( node->rb_left, level + 1 );
}
}

void print_tree(struct rb_root* tree)
{
    printf("-------------------------------------------\n");
print_node(tree->rb_node,0);
printf("-------------------------------------------\n");
}
int  main(void)
{
struct rb_node *node;
struct mytype *mynode;
int i;


for(i = 0; i < TAB_SIZE(array); i++)
{
mynode = malloc(sizeof(struct mytype));
//array[i]=(rand()%100);
mynode->key= array[i];
printf("i = %d, key is %d\n", i,mynode->key);
my_insert(&mytree, mynode); 
}


printf("*********** Up ****************************\n");
i = 0;
for(node = rb_first(&mytree); node; node = rb_next(node))
{
printf("i = %d, key = %d\n", i, (rb_entry(node, struct mytype, node))->key);
i++;
}
printf("------------Down---------------------------\n");
i = 0;
for(node = rb_last(&mytree); node; node = rb_prev(node))
{
printf("i = %d, key = %d\n", i, (rb_entry(node, struct mytype, node))->key);
i++;
}
        /*
printk("------------Erase and Up---------------------------\n");
mynode = my_search(&mytree, array[2]);
if(mynode) 
{
rb_erase(&(mynode->node), &mytree);
kfree(mynode);
printk("Erased %d node !\n",array[2]);
}
*/

    print_tree(&mytree);
    printf("-------------------------------------------------------\n");
return 0;
}
编译：gcc -o rbtree rbtree.c test.c 

运行结果如下图：

非常直观表示红黑树，有助于学习和测试。

遗留问题：

在测试时发现，在内核当中不能用，好像递归函数在内核中使用会有问题，网上查好像是内核栈不够。

红黑树的元素插入顺序不一样，生成的树也不一样：

int array[]={8,25,1,13,15,11,17,6,22,27};   //上图所示红黑树实例顺序改变

运行结果：

希望各大神指点指点，谢谢！

Linux红黑树编程实例，图形化显示红黑树