自学教程：C++ tree_insert函数代码示例

tree* tree_insert(tree* T, elem x, bst B){  REQUIRES(is_tree(T, B));  REQUIRES(x != NULL);  if (T == NULL) {    T = xmalloc(sizeof(tree));    T->height = 1;    T->data = x;    T->left = NULL;    T->right = NULL;  } else {    int r = B->elem_compare(x, T->data);    if (r == 0) {      T->data = x;    } else if (r < 0) {      T->left = tree_insert(T->left, x, B);      T = rebalance_left(T, B);    } else {      T->right = tree_insert(T->right, x, B);      T = rebalance_right(T, B);    }  }  ENSURES(is_tree(T, B));  return T;}

/* program execution begins here * */int main(int argc, char* argv[]) {    if( argc != 2 ) {        fprintf(stderr, "ERROR: useage is ./ticker FILENAME/n");        return -1;    }    struct tree* tree, *tempC = NULL, *tempT = malloc(sizeof(struct tree));    if (!tempT) {        fprintf(stderr, "ERROR: could not allocate space./n");        return -1;    }    memset(tempT, 0, sizeof(struct tree));    tree = read_file(argv[1]);    if (!tree) { // allocation or read failed somehow        return -1;    }    user_input(tree);    while( (tempC = pop_tree(tree)) && tempC != tree) {        tree_insert(tempT, tempC->data, check_value);        free(tempC);    }    tree_insert(tempT, tree->data, check_value);    print_tree(tempT);    free(tree);    tree_destroy(tempT);}

void c_test_ins_tree_equal(void) {  int sizeOfElement = sizeof(struct complexThing);  Tree tree = new_tree(sizeOfElement, navigateComplex, copyComplex, destroyComplex, eq_handler);    Complex *c = malloc(sizeof(struct complexThing));  c->int_regular = 10;  c->int_pointer = malloc(sizeof(int));  *c->int_pointer = 15;  tree_insert(&tree, c, NULL);  *c->int_pointer = 25;  tree_insert(&tree, c, NULL);    void *upd = tree_search(&tree, cb, c, NULL);    CU_ASSERT_EQUAL(*c->int_pointer, *(((Complex*)upd)->int_pointer));    if (tree != NULL) {    destroy_tree(&tree);   }  if (c != NULL) {    if (c->int_pointer != NULL) {      free(c->int_pointer);    }    free(c);  } }

static inline uint8_t tree_insert(treap_node **node,hash_key_t key,void *val) {	treap_node *n = (*node);	if (n==NULL) {		n = malloc(sizeof(treap_node));		passert(n);		n->left = NULL;		n->right = NULL;		n->key = key;		n->val = val;		n->pri = rndu32();		*node = n;		return 1;	} else {		if (key < n->key) {			if (tree_insert(&(n->left),key,val)) {				if (n->left->pri < n->pri) {					tree_rotate_with_left_child(node);				}				return 1;			}		} else if (key > n->key) {			if (tree_insert(&(n->right),key,val)) {				if (n->right->pri < n->pri) {					tree_rotate_with_right_child(node);				}				return 1;			}		}	}	return 0;}

/*inserts a searchKey value into searchTree T*/SearchTree tree_insert( searchKey value, SearchTree T ){   if (T == NULL) // current node is a leaf  {       T = (NodePtr) malloc ( sizeof (struct TreeNode));      if (T == NULL)      {          printf("ERROR no more memory/n");      }      else      {          T -> data = value;          T -> left = NULL;          T -> right = NULL;          }  }  else  {      if (value <= T -> data) //insert to left node (recursion)      {                 T -> left = tree_insert( value, (T -> left) );      }      else  // insert to the right node (recursion)      {           T -> right = tree_insert( value, (T -> right) );      }  }  return T;}

END_TESTSTART_TEST(test_tree_basics){    int seven = 7, one = 1, three = 3;    ck_assert_int_eq(tree_size(tree), 0);    ck_assert_int_eq(*(int *)tree_insert(tree, &seven, &seven), seven);    ck_assert_int_eq(tree_size(tree), 1);    ck_assert_int_eq(*(int *)tree_insert(tree, &one, &one), one);    ck_assert_int_eq(tree_size(tree), 2);    ck_assert_int_eq(*(int *)tree_insert(tree, &three, &three), three);    ck_assert_int_eq(tree_size(tree), 3);    ck_assert_int_eq(*(int *)tree_find(tree, &seven), seven);    ck_assert_int_eq(*(int *)tree_find(tree, &one), one);    ck_assert_int_eq(*(int *)tree_find(tree, &three), three);    ck_assert_int_eq(*(int *)tree_delete(tree, &seven), seven);    ck_assert_int_eq(tree_size(tree), 2);    ck_assert_int_eq(*(int *)tree_delete(tree, &one), one);    ck_assert_int_eq(tree_size(tree), 1);    ck_assert_int_eq(*(int *)tree_delete(tree, &three), three);    ck_assert_int_eq(tree_size(tree), 0);}

static injectable_t * injectable_create(injfile_t * injfile, const char * filename) {    injectable_t * injectable = adbi_malloc(sizeof(injectable_t));        if (!filename) {        /* built-in, loaded from memory */        injectable->filename = adbi_malloc(strlen(injfile->name) + 16);        sprintf((char *) injectable->filename, "<built-in %s>", injfile->name);        injectable->builtin = true;    } else {        /* loaded from disk */        injectable->filename = strdup(filename);        injectable->builtin = false;    }        injectable->references = 0;    injectable->id = next_iid++;    injectable->injfile = injfile;        tree_insert(&injectables, injectable->id, injectable);    if (injectable_is_library(injectable)) {        tree_insert(&libraries, injectable->id, injectable);    } else {        tree_insert(&bindings, injectable->id, injectable);    }        info("Loaded injectable %s.", str_injectable(injectable));    return injectable;}

int main(int argc, char* argv[]){    node_t *root = NULL;        root = tree_insert(NULL, 20);    root = tree_insert(root, 10);    root = tree_insert(root, 100);    root = tree_insert(root, 30);    //printf("%d/n", !tree_lookup(root, 1));    //printf("%d/n", !tree_lookup(root, 2));    //printf("%d/n", !tree_lookup(root, 3));    //printf("%d/n", !tree_lookup(root, 4));    printf("%d/n", tree_min_val(root));    printf("%d/n", tree_max_val(root));    printf("%d/n", tree_size(root));    printTree(root);#if 0    printf("1 %d/n", !check("a(b)"));    printf("1 %d/n", !check("[{}]"));    printf("0 %d/n", !check("["));    printf("0 %d/n", !check("}{"));    printf("1 %d/n", !check("z([{}-()]{a})"));#endif    return 1;}

void tree_insert(struct tree *root, const char *path, int length,		 long offset, long size){	char *pos;	struct tree *node;	if (!path || !*path)		return;	if ((pos = memchr(path, '/', length))) {		// Path contains directory.		*pos = '/0';		node = root->sub;		// Check if this directory was already inserted by earlier calls.		while (node) {			if (!strcmp(node->name, path)) {				tree_insert(node, pos + 1,					    length - (pos + 1 - path),					    offset, size);				return;			}			node = node->next;		}		// Create new directory.		node = (struct tree *)malloc(sizeof(struct tree));		node->name = strdup(path);		node->is_dir = 1;		node->offset = 0;		node->size = 0;		node->nsubdirs = 0;		node->sub = NULL;		node->next = root->sub;		// Connect new directory under current directory.		root->sub = node;		root->nsubdirs++;		// Insert remaining parts of path in new directory.		tree_insert(node, pos + 1, length - (pos + 1 - path),			    offset, size);	} else {		// No more directories in path. Just create new file		// under current directory.		node = (struct tree *)malloc(sizeof(struct tree));		node->name = strndup(path, length);		node->is_dir = 0;		node->offset = offset;		node->size = size;		node->nsubdirs = 0;		node->sub = NULL;		node->next = root->sub;		root->sub = node;	}}

BusinessNode * tree_insert(BusinessNode * node, BusinessNode * root){  if (root == NULL || node == NULL) return node;  if (strcmp(node -> name, root -> name) <= 0)//node < root, should be placed in the left branch    {      root -> left = tree_insert(node, root -> left);      return root;    }  root -> right = tree_insert(node, root -> right);  return root;}

voiduserlist_update_mode (session * sess, char *name, char mode, char sign){    int access;    int offset = 0;    int level;    int pos;    char prefix;    struct User *user;    user = userlist_find (sess, name);    if (!user)        return;    /* remove from binary trees, before we loose track of it */    tree_remove (sess->usertree, user, &pos);    tree_remove (sess->usertree_alpha, user, &pos);    /* which bit number is affected? */    access = mode_access (sess->server, mode, &prefix);    if (sign == '+')    {        level = TRUE;        if (!(user->access & (1 << access)))        {            offset = 1;            user->access |= (1 << access);        }    }    else    {        level = FALSE;        if (user->access & (1 << access))        {            offset = -1;            user->access &= ~(1 << access);        }    }    /* now what is this users highest prefix? e.g. @ for ops */    user->prefix[0] = get_nick_prefix (sess->server, user->access);    /* update the various counts using the CHANGED prefix only */    update_counts (sess, user, prefix, level, offset);    /* insert it back into its new place */    tree_insert (sess->usertree_alpha, user);    pos = tree_insert (sess->usertree, user);    /* let GTK move it too */    fe_userlist_move (sess, user, pos);    fe_userlist_numbers (sess);}

static intuserlist_insertname (session *sess, struct User *newuser){	if (!sess->usertree)	{		sess->usertree = tree_new ((tree_cmp_func *)nick_cmp, sess->server);		sess->usertree_alpha = tree_new ((tree_cmp_func *)nick_cmp_alpha, sess->server);	}	tree_insert (sess->usertree_alpha, newuser);	return tree_insert (sess->usertree, newuser);}

static node_t *tree_insert(node_t *root, char data){    if (!root)        return tree_new(data);    if (data < root->data)        root->left = tree_insert(root->left, data);    else        root->right = tree_insert(root->right, data);        return root;}

void compute(struct In *input, struct Out *output){  tree_t tree;  BOOL success = FALSE;  tree_init(&tree);  success = tree_insert(&tree, 9, 112);  success = tree_insert(&tree, 27, 8);  success = tree_insert(&tree, 63, 789);  tree_find_gt(&tree, 26, FALSE, &(output->result_set1));  tree_find_range(&tree, 8, TRUE, 63, FALSE, &(output->result_set2));}

tree *tree_insert(tree *btree, int data){    if(!btree){        btree = calloc(1, sizeof(tree));        btree->data = data;        return btree;    }    if(btree->data > data)       btree->left = tree_insert(btree->left, data);    else       btree->right = tree_insert(btree->right, data);    return btree;}

BusinessNode * tree_insert(BusinessNode * node, BusinessNode * root){    if(root == NULL)	return node;    if(strcmp(root -> name, node -> name) >= 0) {	root -> left = tree_insert(node, root -> left);	return root;    }    root -> right = tree_insert(node, root -> right);    return root;}

MNCL_RAW *mncl_acquire_raw(const char *resource){    MNCL_RAW *result = NULL;    struct resmap_node seek, *found = NULL;    struct provider *i = providers;    char *duped_name;    seek.resname = resource;    found = (struct resmap_node *)tree_find(&locked_resources, (TREE_NODE *)&seek, rescmp);    if (found) {        ++found->refcount;        return found->resource;    }    while (i && !result) {        switch (i->tag) {        case PROVIDER_DIRECTORY:            result = filesystem_get_resource(i->path, resource);            break;        case PROVIDER_ZIPFILE:            result = zipfile_get_resource(i->path, resource);            break;        default:            /* ? */            break;        }        i = i->next;    }    if (!result) {        /* Don't pollute our resource map */        return NULL;    }    /* Update the resource map */    found = malloc(sizeof(struct resmap_node));    duped_name = (char *)malloc(strlen(resource)+1);    strcpy(duped_name, resource);    found->resname = duped_name;    found->resource = result;    found->refcount = 1;    tree_insert(&locked_resources, (TREE_NODE *)found, rescmp);    /* Build another copy for the reverse map */    found = malloc(sizeof(struct resmap_node));    duped_name = (char *)malloc(strlen(resource)+1);    strcpy(duped_name, resource);    found->resname = duped_name;    found->resource = result;    found->refcount = 0;    tree_insert(&reverse_map, (TREE_NODE *)found, ptrcmp);        return result;}

struct tree_node *tree_insert(struct tree_node *p, char *word){	if (p == NULL) {		p = (struct tree_node *)malloc(sizeof(struct tree_node));		p->word = word;		p->lchild = NULL;		p->rchild = NULL;	} else if (strcmp(p->word, word) < 0) {		p->rchild = tree_insert(p->rchild, word);	} else if (strcmp(p->word, word) > 0) {		p->lchild = tree_insert(p->lchild, word);	}	return p;}

void tree_insert(tree_node_t **root, int key){    if (tree_node_empty(*root))    {        *root = mk_tree_node(key, mk_empty_tree(), mk_empty_tree());    }    else if (key < (*root)->key)    {        tree_insert(&(*root)->left, key);    }    else if (key > (*root)->key)    {        tree_insert(&(*root)->right, key);    }}

/* * this allocates a new root in the lookup tree. * * root_id should be the object id of the root * * ref_tree is the objectid of the referring root. * * dir_id is the directory in ref_tree where this root_id can be found. * * name is the name of root_id in that directory * * name_len is the length of name */static int add_root(struct root_lookup *root_lookup,		    u64 root_id, u64 ref_tree, u64 dir_id, char *name,		    int name_len){	struct root_info *ri;	struct rb_node *ret;	ri = malloc(sizeof(*ri) + name_len + 1);	if (!ri) {		printf("memory allocation failed/n");		exit(1);	}	memset(ri, 0, sizeof(*ri) + name_len + 1);	ri->path = NULL;	ri->dir_id = dir_id;	ri->root_id = root_id;	ri->ref_tree = ref_tree;	strncpy(ri->name, name, name_len);	ret = tree_insert(&root_lookup->root, root_id, ref_tree, &ri->rb_node);	if (ret) {		printf("failed to insert tree %llu/n", (unsigned long long)root_id);		exit(1);	}	return 0;}

int main(){	BinTree *tree = tree_new();	/*tree_insert(tree, 5);	tree_insert(tree, 7);	tree_insert(tree, 3);	tree_insert(tree, 8);	tree_insert(tree, 1);	tree_insert(tree, 0);	tree_insert(tree, 2);	tree_insert(tree, 6);	tree_insert(tree, 4);	//tree_remove(tree, 6);	printf("%d/n", tree_height(tree));	printf("%d/n", tree_find(tree, 5));	tree_print(tree);	*/	int i;	for (i = 0; i < TAM; i++)		tree_insert(tree, i+1);	//demora aprox 22 segundos a pesquisar todos os elementos da lista 	for (i = 0; i < TAM; i++)		tree_find(tree, i);		tree_destroy(tree);		return 0;}

void c_test_tree_delete(void) {    int items = 2;  int sizeOfElement = sizeof(struct complexThing);  Tree tree = new_tree(sizeOfElement, navigateComplex, copyComplex, destroyComplex, NULL);    for (int i = 1; i < items; i++) {    Complex *c = malloc(sizeof(struct complexThing));    c->int_regular = i;    c->int_pointer = malloc(sizeof(int));    *c->int_pointer = i+i;    tree_insert(&tree, c, NULL);         if (c != NULL) {      if (c->int_pointer != NULL) {	free(c->int_pointer);      }      free(c);    }  }   for (int d = items - 1; d >= 0; d--) {    tree_delete(&tree, &d, navigateSearchComplex);  }  CU_ASSERT_EQUAL(get_tree_height(tree), 0);  if (tree != NULL) {    destroy_tree(&tree);   }}

void command_add (command_fn_t callback,                  const char *input,                  const char *readable){    if (!commands) {        commands = tree_alloc(TREE_KEY_STRING, "TREE ROOT: commands");    }    command_t *command = (typeof(command))                    myzalloc(sizeof(*command), "TREE NODE: command");    command->tree.key = dupstr(input, "TREE KEY: command");    command->callback = callback;    /*     * Convert the command into tokens for matching.     */    tokens_tostring(input, &command->tokens);    tokens_tostring(input, &command->input_tokens);    tokens_tostring(readable, &command->readable_tokens);    if (!tree_insert(commands, &command->tree.node)) {        ERR("insert of command %s fail", input);    }}

/* Reads fromt he specified file and creates a tree based on the data inside * returns a MALLOC'd tree structure. */struct tree* read_file(char* filename) {    FILE* file;    if ( ! (file = fopen(filename, "r"))) {        fprintf(stderr, "ERROR: could not open file. Check filename and permissions./n");        return NULL;    }    struct tree* farce = malloc(sizeof(struct tree));    if (! farce) {        fprintf(stderr, "ERROR: could not allocate space./n");        return NULL;    }    memset( farce, 0, sizeof(struct tree));    char temp[82];    struct company *pmet;    while( fgets(temp, sizeof(temp), file) != NULL) {        temp[81] = '/0';        pmet = make_company(temp);        if ( pmet) {            tree_insert(farce, pmet, check_symbol);        }        pmet = NULL;    }    fclose(file);    return farce;}

intmain(void){       tree_node_t *bs_treep;   /* binary search tree 	*/      int          data_key;   /* input - keys for tree  	*/      int          status;     /* status of input operation	*/       bs_treep = NULL;   /* Initially, tree is empty */       /* As long as valid data remains, scan and insert keys,          displaying tree after each insertion. */      for  (status = scanf("%d", &data_key);            status == 1;            status = scanf("%d", &data_key)) {          bs_treep = tree_insert(bs_treep, data_key);          printf("Tree after insertion of %d:/n", data_key);          tree_inorder(bs_treep);      }          if (status == 0) {            printf("Invalid data >>%c/n", getchar());      } else {            printf("Final binary search tree:/n");            tree_inorder(bs_treep);      }       return (0);}

int main(int argc, char *argv[]){    char numbers[] = { 4, 2, 6, 1, 3, 5, 7 };    tree_node_t *root = mk_empty_tree();    assert(tree_node_empty(root));    int i;    for (i = 0; i < sizeof(numbers); ++i)    {        tree_insert(&root, numbers[i]);    }    assert(!tree_node_empty(root));    assert(root->key == 4);    assert(tree_search(root, 7));    printf("=== pre ===/n");    preorder(root);    printf("=== in ===/n");    inorder(root);    printf("=== post ===/n");    postorder(root);    return 0;}

/* Insert a node into a BST. Primarily used in load_tree_from_file(). Return a * pointer to the root of the BST. */BusinessNode *tree_insert(BusinessNode * node, BusinessNode * root){	if(root == NULL){		return node;	}	int comp = strcmp(node -> name, root -> name);	if(comp <= 0){		root -> left = tree_insert(node,root->left);	}	else	{		root -> right = tree_insert(node,root->right);		}	return root;}

/* Parse a .tsv file line by line, create a BusinessNode for each entry, and * enter that node into a new BST. Return a pointer to the root of the BST. * * The explode(...) function from PA03 may be useful for breaking up a lines  * into seperate fields.  */BusinessNode *load_tree_from_file(char * filename){	FILE * fptr = NULL;    fptr = fopen(filename, "r");    if(fptr == NULL)    {        return NULL;    }    BusinessNode * root = NULL;    char ** strexplode = NULL;    char * str = malloc(sizeof(char)*2000);    int arrLen = 0;    while(fgets(str, 2000, fptr) != NULL)	{		strexplode = explode(str, "/t", &arrLen);    	if(arrLen == 3)    	{        	BusinessNode * node = create_node(strexplode[0], strexplode[1], strexplode[2]);        	root = tree_insert(node, root);    	}    	free(strexplode);	}	free(str);	fclose(fptr);	return(root);}

int main(){	int i;	char **words = (char **)malloc(sizeof(char *) * 100000);	if (words == NULL) {		printf("error!/n");		exit(1);	}	for (i = 0; i < 100000; i++) {		words[i] = (char *)malloc(sizeof(char) * 20);		if (words[i] == NULL) {			printf("error!/n");			exit(1);		}	}	for (i = 0; i < 79339; i++)		scanf("%s", words[i]);	struct tree_node *root;	root = NULL;	for (i = 0; i < 79339; i++)		tree_insert(root, words[i]);	if (root == NULL)		printf ("root is NULL/n");	/* for (i = 0; i < 79339; i++) */	/* 	printf("%d/n", bin_tree_search(root, words[i])); */	return 0;}

void ReadHostFile (const char *fname){  if (!fname || !*fname)     return;  hostFname = strdup (fname);  if (!hostFname)     return;  sethostent (1);  if (!hostFile)     return;  while (1)  {    struct _hostent h;    if (!_gethostent(&h))       break;    if (!tree_insert(&host_root, (void*)&h, sizeof(h), (CmpFunc)host_cmp_name))    {      outsnl (_LANG("Hostfile too big!/7"));      break;    }  }  atexit (endhostent);}