生成二叉树和红黑树的helloworld（1）

参考的这个视频
视频讲得有点烂，代码错误很多，诶，不过ptree似乎挺好，挺直观的
递归都能变成栈？ 中序遍历，先序遍历，后续遍历都是栈，层序遍历用的队列


bst数的，增删

[root@VM_253_237_tlinux ~/tree]# cat bst.c  
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define N 10
typedef struct node *link;
struct node{
        int item;link l,r;
};
link NODE(int item,link l,link r){
        link t=malloc(sizeof *t);
        t->item=item;t->l=l;t->r=r;
        return t;
}
link insert_node(link t,int item){
        if(t==NULL) return  NODE(item,NULL,NULL);
        if(item<t->item)
                t->l=insert_node(t->l,item);
        else
                t->r=insert_node(t->r,item);
        return t;
}
void pprint(link t){
        printf("(");
        if(t!=NULL){ 
                printf("%d",t->item);
                pprint(t->l);
                pprint(t->r);
        }
        printf(")");
}
int bst_search(link t,int item){
        if(t==NULL) return 0;
        if(item<t->item)return bst_search(t->l,item);
        else if(item>t->item) return bst_search(t->r,item);
        else return 1;
}
link bst_remove(link t,int item){
        if(t==NULL) return NULL;
        if(item<t->item)
                t->l=bst_remove(t->l,item);
        else if(item>t->item){
                t->r=bst_remove(t->r,item);
        }else {
                link x;
                if(t->l){
                        for(x=t->l;x->r;x=x->r){;}
                        t->item=x->item;
                        t->l=bst_remove(t->l,t->item);
                }else if(t->r){
                        for(x=t->r;x->l;x=x->l){;}
                        t->item=x->item;
                        t->r=bst_remove(t->l,t->item);
                }else{
                        free(t);t=NULL; 
                }
        }
        return t;
}
int main(){
        srand(time(NULL));
        int i ;link root=NULL;
        for(i=0;i<N;i++) root =insert_node(root,rand()%100);
        printf("\t\\tree");pprint(root);
        printf("\n");
        printf("%d\n",bst_search(root,50));
        root=bst_remove(root,root->item);
        printf("\t\\tree");pprint(root);
        return 0;
}

---------------------------------
红黑树：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define N 10
typedef struct node *link;
struct node{
        int item,red;link l,r;
};
link null;
link NODE(int item,link l,link r,int red){
        link t=malloc(sizeof *t);
        t->item=item;t->l=l;t->r=r;t->red=red;
        return t;
}
link rotR(link t){
        link x=t->l;t->l=x->r;x->r=t;return x;
}
link rotL(link t){
        link x=t->r;t->r=x->l;x->l=t;return x;
}
void pprint(link t){
        printf("(");
        if(t!=null){ 
                printf("%d%c",t->item,t->red?'+':' ');
                pprint(t->l);
                pprint(t->r);
        }
        printf(")");
}
link RBinit(){
        null=NODE(0,NULL,NULL,0);
        null->l=null;null->r=null;
        return null;
}
link insert_node(link t ,int item, int sw){
        if(t==null) return NODE(item,null,null,1);
        if(t->l->red && t->r->red){
                t->red=1;t->l->red=0;t->r->red=0;
        }
        if(item<t->item){
                t->l=insert_node(t->l,item,0);
                if(t->red && t->l->red && sw) t=rotR(t);
                if(t->l->red && t->l->l->red)
                { t=rotR(t); t->red=0; t->r->red=1; }
        }else{
                t->r=insert_node(t->r,item,1);
                if(t->red && t->r->red && !sw) t=rotL(t);
                if(t->r->red && t->r->r->red)
                { t=rotL(t); t->red=0; t->l->red=1; }
        }
        return t;
}
link RBinsert(link root,int item){
        root=insert_node(root,item,0);
        root->red=0;
        return root;
}
int main(){
        int i=0;
        srand(time(NULL));
        link root=RBinit();
        for(i=0;i<N;i++)
                root=RBinsert(root,rand()%100);
        printf("\t\\tree");
        pprint(root);
        printf("\n");
        return 0;
}

视频中的ptree应该是自己写的一个层序遍历的例子
层序遍历大概这样，还需要完善下：

[root@VM_253_237_tlinux ~/tree]# cat ltree.c 
#include <stdlib.h>
#include <stdio.h>
#define max(a,b) (a>b?a:b)
typedef struct Node *link;
struct Node{
        int item;link l,r;
};
link NODE(int item,link l,link r){
        link t=malloc(sizeof *t);
        t->item=item;t->l=l;t->r=r;
        return t;
}
link Construct() {
        link node4 = NODE(7, NULL, NODE(3,NULL,NULL));
        link node3 = NODE(4,NULL,NULL);
        link node2 = NODE(12,NULL,NULL);
        link node1 = NODE(5, node3, node4);
        link root  = NODE(10, node1, node2);
        return root;
}
int PrintByLevel(link root, int level) {
        if(root == NULL)
                return 0;
        if(level == 1) {
                printf("%d ",root->item);
                return 1;
        }
        return PrintByLevel(root->l, level - 1) + PrintByLevel(root->r, level - 1);
}
int GetTreeHeight(link root) {
        if(root == NULL)
                return 0;
        return max(GetTreeHeight(root->l) + 1, GetTreeHeight(root->r) + 1);
}
int main() {
        link root = Construct();
        int height = GetTreeHeight(root);
        int i=0;
        for( i = 1; i <= height; i++) {
                PrintByLevel(root, i);
                printf("\n");
        }
        return 0;
}

http://www.cppblog.com/ngaut/archive/2012/09/06/2351.html


打印树
：

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <curses.h>
#include <time.h>
#define N 10
typedef struct node *link;
struct node{
        int item;link l,r;
};
static void recur_print( struct node * node, int line, int col ){
        if( node == NULL ){
                move( line, col ) ;
                addstr("*");//此处为加*号的代码，用来占位，可去掉。
                return ;
        }
        int t = COLS/pow( 2, line+2 );
        char buf[9];
        sprintf(buf,"%-d", node->item ) ;
        move( line , col ) ;
        addstr( buf ) ;
        if( node->l != NULL || node->r != NULL ){
                move(line+1, col-t-1 ) ;
                addstr("[");
                move(line+1, col+t+3) ;
                addstr("]");
        }
        recur_print( node->l, line+1, col-t ) ;
        recur_print( node->r, line+1, col+t ) ;
}
void print_tree(struct node * root){
        initscr() ;
        clear();
        recur_print(root, 0, COLS/2);
        move(LINES-1, COLS-1) ;
        refresh() ;
        getchar() ;
        endwin() ;
}
link NODE(int item,link l,link r){
        link t=malloc(sizeof *t);
        t->item=item;t->l=l;t->r=r;
        return t;
}
link insert_node(link t,int item){
        if(t==NULL) return  NODE(item,NULL,NULL);
        if(item<t->item)
                t->l=insert_node(t->l,item);
        else
                t->r=insert_node(t->r,item);
        return t;
}
void pprint(link t){
        printf("(");
        if(t!=NULL){
                printf("%d",t->item);
                pprint(t->l);
                pprint(t->r);
        }
        printf(")");
}
int bst_search(link t,int item){
        if(t==NULL) return 0;
        if(item<t->item)return bst_search(t->l,item);
        else if(item>t->item) return bst_search(t->r,item);
        else return 1;
}
int main(){
        printf("aaa");
srand(time(NULL));
        int i ;link root=NULL;
        for(i=0;i<N;i++) root =insert_node(root,rand()%100);
        printf("\n");
        printf("\t\\tree");pprint(root);
        print_tree(root);
        return 0;
}

编译的时候需要 gcc  -lm -lcurses ctree.c
需要安装ncurses

参考了
http://biancheng.dnbcw.info/linux/248916.html