C语言实现二叉树源代码

#include "2xtree.h" //#include <memory.h> //#include <malloc.h> #include <stdio.h> #include <stdlib.h> #include <sys/types.h> //#include <asm/types.h> /*前缀位操作*/ #define CHECK_BIT(P,L) \ ((((u_char *)(P))[(L)/8]>>(7-(L)%8))&1) /*计算两个前缀的共同前缀，结果为common_p*/ void prefix_common(struct prefix *p1, struct prefix *p2, struct prefix *common_p) { u_int32_t shift; u_int32_t p1_p=*((u_int32_t *)(&p1->prefix_4)); u_int32_t p2_p=*((u_int32_t *)(&p2->prefix_4)); u_int32_t tmp_common=(~(p1_p & p2_p))& p1_p; memcpy(&common_p->prefix_4, &tmp_common, sizeof(u_int32_t)); shift=0; while(!(tmp_common&0x1)) { tmp_common>>1; shift++; } common_p->prefix_len=32-shift; } /*比较两个前缀是否有共同的前缀*/ int prefix_match(struct prefix *p1, struct prefix *p2) { struct prefix *common_p; common_p=(struct prefix *)malloc(sizeof(struct prefix)); memset(common_p, 0, sizeof(struct prefix)); prefix_common(p1, p2, common_p); if(common_p) return TRUE; else return FAULSE; } /*ASR 接入网络前缀表的初始化和删除*/ struct route_mr_table *route_mr_table_init() { struct route_mr_table *mrt; mrt=(struct route_mr_table *)malloc(sizeof(struct route_mr_table)); memset(mrt,0,sizeof(struct route_mr_table)); return mrt; } void route_mr_table_free(struct route_mr_table *mrt) { if(mrt->top==NULL) return; struct route_mr_node *node, *tmp_node; node=mrt->top; while(node) { if(node->l_son) { node=node->l_son; continue; } if(node->r_son) { node=node->r_son; continue; } tmp_node=node; node=node->parent; if(node!=NULL) { if(tmp_node==node->l_son) node->l_son=NULL; else node->r_son=NULL; }else { mrt->top=NULL; } route_mr_node_free(tmp_node); } } /*接入网络前缀条目的查找，创建，删除*/ struct route_mr_node *route_mr_node_close_match(struct route_mr_table *mrt, struct prefix *p) { struct route_mr_node *node; struct route_mr_node *close_match_node; close_match_node=NULL; node= mrt->top; while (node&&node->p.prefix_len<=p->prefix_len&&prefix_match(&node->p, p)) { if(node->info) close_match_node=node; node=node->son[CHECK_BIT(&p->prefix_4, node->p.prefix_len)]; } if(close_match_node) return route_mr_node_lock(node); return NULL; } struct route_mr_node *route_mr_node_lookup(struct route_mr_table *mrt, struct prefix *p) { struct route_mr_node *node; node= mrt->top; while (node&&node->p.prefix_len<=p->prefix_len&&prefix_match(&node->p, p)) { if(node->p.prefix_len==p->prefix_len&&node->info) return route_mr_node_lock(node); node=node->son[CHECK_BIT(&p->prefix_4, node->p.prefix_len)]; } return NULL; } struct route_mr_node *route_mr_node_create() { struct route_mr_node *mn; mn=(struct route_mr_node *)malloc(sizeof(struct route_mr_node)); memset(mn,0,sizeof(struct route_mr_node)); return mn; } struct route_mr_node *route_mr_node_get(struct route_mr_table *mrt, struct prefix *p) { struct route_mr_node *node; node=mrt->top; if(node==NULL) { mrt->top=route_mr_node_set(mrt, p); return mrt->top; } node= route_mr_node_lookup(mrt, p); if(node) { return node; }else { node= route_mr_node_close_match(mrt, p); if(node) { struct route_mr_node *new_node, *tmp_node; new_node=route_mr_node_set(mrt, p); tmp_node=node->son[CHECK_BIT(p,node->p.prefix_len)]; new_node->parent=node; new_node->son[CHECK_BIT(p,node->p.prefix_len)]=tmp_node; tmp_node->parent=new_node; }else { node=mrt->top; struct prefix new_p; struct route_mr_node *new_top, *new_node; prefix_common(&node->p, p, &new_p); new_node=route_mr_node_set(mrt, p); new_top=route_mr_node_set(mrt, &new_p); new_top->son[CHECK_BIT(&mrt->top->p.prefix_4, new_top->p.prefix_len)]=mrt->top; new_top->son[CHECK_BIT(&new_node->p.prefix_4, new_top->p.prefix_len)]=new_node; new_node->parent=new_top; mrt->top->parent=new_top; mrt->top=new_top; return new_node; } } } struct route_mr_node *route_mr_node_set(struct route_mr_table *mrt,struct prefix *p) { struct route_mr_node *new_node; new_node=route_mr_node_create(); memcpy(&new_node->p, p, sizeof(struct prefix)); new_node->asr_mr_table=mrt; return new_node; } void route_mr_node_free(struct route_mr_node *mn) { free(mn); } void route_mr_node_delete(struct route_mr_node *node) { struct route_mr_node *parent; struct route_mr_node *child; if(node->l_son&&node->r_son) return; if(node->l_son) child=node->l_son; if(node->r_son) child=node->r_son; parent=node->parent; if(child) child->parent=node->parent; if(parent) { //if(node->l_son==child)为什么错？因为有可能node是最低端，无子 if(parent->l_son==node) parent->l_son=child; else parent->r_son=child; }else { node->asr_mr_table->top=NULL; } route_mr_node_free(node); } /*为接入网络前缀条目加锁*/ struct route_mr_node *route_mr_node_lock(struct route_mr_node *node) { node->lock++; return node; } struct route_mr_node *route_mr_node_unlock(struct route_mr_node *node) { node->lock--; return node; } int main(int argc, char **argv) { return 0; }