Pеализация двоичного дерева на Си /* binary search tree */ #include <stdio.h> #include <stdlib.h> typedef int T; /* type of item to be stored */ #define compLT(a,b) (a < b) #define compEQ(a,b) (a == b) typedef struct Node_ { struct Node_ *left; /* left child */ struct Node_ *right; /* right child */ struct Node_ *parent; /* parent */ T data; /* data stored in node */ } Node; Node *root = NULL; /* root of binary tree */ Node *insertNode(T data) { Node *x, *current, *parent; /*********************************************** * allocate node for data and insert in tree * ***********************************************/ /* find x's parent */ current = root; parent = 0; while (current) { if (compEQ(data, current->data)) return (current); parent = current; current = compLT(data, current->data) ? current->left : current->right; } /* setup new node */ if ((x = malloc (sizeof(*x))) == 0) { fprintf (stderr, "insufficient memory (insertNode)\n"); exit(1); } x->data = data; x->parent = parent; x->left = NULL; x->right = NULL; /* insert x in tree */ if(parent) if(compLT(x->data, parent->data)) parent->left = x; else parent->right = x; else root = x; return(x); } void deleteNode(Node *z) { Node *x, *y; /***************************** * delete node z from tree * *****************************/ /* y will be removed from the parent chain */ if (!z || z == NULL) return; /* find tree successor */ if (z->left == NULL || z->right == NULL) y = z; else { y = z->right; while (y->left != NULL) y = y->left; } /* x is y's only child */ if (y->left != NULL) x = y->left; else x = y->right; /* remove y from the parent chain */ if (x) x->parent = y->parent; if (y->parent) if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; else root = x; /* y is the node we're removing */ /* z is the data we're removing */ /* if z and y are not the same, replace z with y. */ if (y != z) { y->left = z->left; if (y->left) y->left->parent = y; y->right = z->right; if (y->right) y->right->parent = y; y->parent = z->parent; if (z->parent) if (z == z->parent->left) z->parent->left = y; else z->parent->right = y; else root = y; free (z); } else { free (y); } } Node *findNode(T data) { /******************************* * find node containing data * *******************************/ Node *current = root; while(current != NULL) if(compEQ(data, current->data)) return (current); else current = compLT(data, current->data) ? current->left : current->right; return(0); } int main(int argc, char **argv) { int i, *a, maxnum, random; /* command-line: * * bin maxnum random * * bin 5000 // 5000 sequential * bin 2000 r // 2000 random * */ maxnum = atoi(argv[1]); random = argc > 2; if ((a = malloc(maxnum * sizeof(*a))) == 0) { fprintf (stderr, "insufficient memory (a)\n"); exit(1); } if (random) { /* random */ /* fill "a" with unique random numbers */ for (i = 0; i < maxnum; i++) a[i] = rand(); printf ("ran bt, %d items\n", maxnum); } else { for (i=0; i printf ("seq bt, %d items\n", maxnum); } for (i = 0; i < maxnum; i++) { insertNode(a[i]); } for (i = maxnum-1; i >= 0; i--) { findNode(a[i]); } for (i = maxnum-1; i >= 0; i--) { deleteNode(findNode(a[i])); } return 0; } <<<  Назад  1  2  3  4   8  Комментарии к статье  8 8  Обсудить в чате