在标准二叉搜索树中，每个新节点都会插入到树的底层的某个地方，替换某个外部节点。这种状态并不是一个绝对的要求；也可以从根节点插入，方法是先插入到相应外部节点然后在通过旋转，转到根节点，下面给出实现：
#include <stdio.h>
#include <stdlib.h>
struct Tree
{
int item;
struct Tree* l;
struct Tree* r;
};
struct Tree* rotR( struct Tree* h)
{
if( h == NULL )
return NULL;
struct Tree* x = NULL;
x = h->l;
h->l = x->r;
x->r = h;
return x;
}
struct Tree* rotL( struct Tree* h )
{
if( h == NULL )
return NULL;
struct Tree*x = NULL;
x = h->r;
h->r = x->l;
x->l = h;
return x;
}
struct Tree* insertT( struct Tree* h, int item )
{
if( h == NULL )
{
h = malloc( sizeof(struct Tree) );
if( h == NULL )
{
printf("malloc error\n");
return NULL;
}
else
{
h->item = item;
h->l = NULL;
h->r = NULL;
return h;
}
}
if( h->item > item )
{
h->l = insertT(h->l,item);
h = rotR(h);
}
else
{
h->r = insertT(h->r,item);
h = rotL(h);
}
return h;
}
void travel( struct Tree* t )
{
if( t->l != NULL)
travel(t->l);
printf("%d\n",t->item);
if( t->r != NULL )
travel(t->r);
}
int main( int argc, char* argv[] )
{
struct Tree *t = NULL;
t = insertT(t,8);
t = insertT(t,7);
t = insertT(t,9);
t = insertT(t,6);
t = insertT(t,10);
t = insertT(t,5);
t = insertT(t,11);
t = insertT(t,4);
t = insertT(t,12);
t = insertT(t,3);
t = insertT(t,13);
travel(t);
return 0;
}