From b70153e861af2b1c51d07926b7829ba0a3264a6b Mon Sep 17 00:00:00 2001 From: Steve Lee Date: Sun, 10 Dec 2017 09:07:59 +0800 Subject: chap4 for data structure --- .../chapter_4/.binary_search_tree.c.swp | Bin 0 -> 12288 bytes Computer_Science/data_structures/chapter_4/a.out | Bin 0 -> 12928 bytes .../data_structures/chapter_4/binary_search_tree.c | 138 ++++++++++ .../data_structures/chapter_4/binary_search_tree.h | 17 ++ .../data_structures/chapter_4/print_ascii_tree.c | 282 +++++++++++++++++++++ .../data_structures/chapter_4/print_ascii_tree.h | 22 ++ 6 files changed, 459 insertions(+) create mode 100644 Computer_Science/data_structures/chapter_4/.binary_search_tree.c.swp create mode 100755 Computer_Science/data_structures/chapter_4/a.out create mode 100644 Computer_Science/data_structures/chapter_4/binary_search_tree.c create mode 100644 Computer_Science/data_structures/chapter_4/binary_search_tree.h create mode 100644 Computer_Science/data_structures/chapter_4/print_ascii_tree.c create mode 100644 Computer_Science/data_structures/chapter_4/print_ascii_tree.h (limited to 'Computer_Science/data_structures/chapter_4') diff --git a/Computer_Science/data_structures/chapter_4/.binary_search_tree.c.swp b/Computer_Science/data_structures/chapter_4/.binary_search_tree.c.swp new file mode 100644 index 0000000..b1514aa Binary files /dev/null and b/Computer_Science/data_structures/chapter_4/.binary_search_tree.c.swp differ diff --git a/Computer_Science/data_structures/chapter_4/a.out b/Computer_Science/data_structures/chapter_4/a.out new file mode 100755 index 0000000..b1815f0 Binary files /dev/null and b/Computer_Science/data_structures/chapter_4/a.out differ diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree.c b/Computer_Science/data_structures/chapter_4/binary_search_tree.c new file mode 100644 index 0000000..fb61e7b --- /dev/null +++ b/Computer_Science/data_structures/chapter_4/binary_search_tree.c @@ -0,0 +1,138 @@ +#include +#include +#include + +#include "binary_search_tree.h" +#include "print_ascii_tree.h" + +struct TreeNode +{ + elem_t elem; + SearchTree left; + SearchTree right; +}; + +SearchTree make_empty(SearchTree t) +{ + if(t != NULL) { + make_empty(t->left); + make_empty(t->right); + free(t); + } + + return NULL; +} + +/** + * find x or return NULL. + */ +Position find(elem_t x, SearchTree t) +{ + if(t != NULL) { + if(t->elem == x) return t; + else if(t->elem > x) return find(x, t->right); + else return find(x, t->left); + } + + return NULL; +} + +Position find_min(SearchTree t) +{ + if(t == NULL) + return NULL; + else if(t->left == NULL) + return t; + else + return find_min(t->left); +} + +Position find_max(SearchTree t) +{ + if(t == NULL) + return NULL; + else if(t->right == NULL) + return t; + else + return find_max(t->right); +} + +SearchTree insert(elem_t x, SearchTree t) +{ + if(t == NULL) { + t = malloc(sizeof(struct TreeNode)); + t->elem = x; + t->left = NULL; + t->right = NULL; + } else if(x > t->elem) + t->right = insert(x, t->right); + else if(x < t->elem) + t->left = insert(x, t->left); + /* The t->elem = x need do nothing, already inserted */ + + return t; +} + +SearchTree delete(elem_t x, SearchTree t) +{ + Position p, tmp; + + p = find(x, t); + + if(p == NULL) { + /* elem x not found */ + printf("x not found!(do nothing)\n"); + } else if(p->left == NULL && p->right == NULL) { + free(p); + } else if(p->left == NULL) { + tmp = p; + p = p->right; + free(tmp); + } else if(p->right == NULL) { + tmp = p; + p = p->left; + free(tmp); + } else { + /* replace and delete */ + tmp = find_min(p->right); + p->elem = tmp->elem; + t->right = delete(p->elem, t->right); + } + + return t; +} + +elem_t retrieve(Position p) +{ + +} + +void print_tree_pre_order(SearchTree t) +{ + if(t == NULL) + return; + print_tree_pre_order(t->left); + printf("%d ", t->elem); + print_tree_pre_order(t->right); +} + +void test() +{ + SearchTree t = NULL; + t = make_empty(t); + t = insert(1, t); + insert(4, t); + insert(3, t); + insert(2, t); + insert(10, t); + + print_tree_pre_order(t); + printf("\n"); + print_ascii_tree(t); +} + +int main() +{ + test(); + return 0; +} diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree.h b/Computer_Science/data_structures/chapter_4/binary_search_tree.h new file mode 100644 index 0000000..da128f8 --- /dev/null +++ b/Computer_Science/data_structures/chapter_4/binary_search_tree.h @@ -0,0 +1,17 @@ +#ifndef _BINARY_SEARCH_TREE_H +#define _BINARY_SEARCH_TREE_H + +struct TreeNode; +typedef struct TreeNode *Position; +typedef struct TreeNode *SearchTree; +typedef int elem_t; + +SearchTree make_empty(SearchTree t); +Position find(elem_t x, SearchTree t); +Position find_min(SearchTree t); +Position find_max(SearchTree t); +SearchTree insert(elem_t x, SearchTree t); +SearchTree delete(elem_t x, SearchTree t); +elem_t retrieve(Position p); + +#endif /* _BINARY_SEARCH_TREE_H */ diff --git a/Computer_Science/data_structures/chapter_4/print_ascii_tree.c b/Computer_Science/data_structures/chapter_4/print_ascii_tree.c new file mode 100644 index 0000000..f2e9839 --- /dev/null +++ b/Computer_Science/data_structures/chapter_4/print_ascii_tree.c @@ -0,0 +1,282 @@ +#include +#include +#include + +#include "binary_search_tree.h" +#include "print_ascii_tree.h" + +struct asciinode_struct +{ + asciinode * left, * right; + + //length of the edge from this node to its children + int edge_length; + + int height; + + int lablen; + + //-1=I am left, 0=I am root, 1=right + int parent_dir; + + //max supported unit32 in dec, 10 digits max + char label[11]; +}; + +int lprofile[MAX_HEIGHT]; +int rprofile[MAX_HEIGHT]; + +//adjust gap between left and right nodes +int gap = 3; + +//used for printing next node in the same level, +//this is the x coordinate of the next char printed +int print_next; + +int MIN (int X, int Y) +{ + return ((X) < (Y)) ? (X) : (Y); +} + +int MAX (int X, int Y) +{ + return ((X) > (Y)) ? (X) : (Y); +} + +asciinode *build_ascii_tree_recursive(Tree t) +{ + asciinode *node; + + if (t == NULL) return NULL; + + node = malloc(sizeof(asciinode)); + node->left = build_ascii_tree_recursive(t->left); + node->right = build_ascii_tree_recursive(t->right); + + if (node->left != NULL) + { + node->left->parent_dir = -1; + } + + if (node->right != NULL) + { + node->right->parent_dir = 1; + } + + sprintf(node->label, "%d", t->elem); + node->lablen = strlen(node->label); + + return node; +} + + +//Copy the tree into the ascii node structre +asciinode *build_ascii_tree(Tree t) +{ + asciinode *node; + if (t == NULL) return NULL; + node = build_ascii_tree_recursive(t); + node->parent_dir = 0; + return node; +} + +//Free all the nodes of the given tree +void free_ascii_tree(asciinode *node) +{ + if (node == NULL) return; + free_ascii_tree(node->left); + free_ascii_tree(node->right); + free(node); +} + +//The following function fills in the lprofile array for the given tree. +//It assumes that the center of the label of the root of this tree +//is located at a position (x,y). It assumes that the edge_length +//fields have been computed for this tree. +void compute_lprofile(asciinode *node, int x, int y) +{ + int i, isleft; + if (node == NULL) return; + isleft = (node->parent_dir == -1); + lprofile[y] = MIN(lprofile[y], x-((node->lablen-isleft)/2)); + if (node->left != NULL) + { + for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++) + { + lprofile[y+i] = MIN(lprofile[y+i], x-i); + } + } + compute_lprofile(node->left, x-node->edge_length-1, y+node->edge_length+1); + compute_lprofile(node->right, x+node->edge_length+1, y+node->edge_length+1); +} + +void compute_rprofile(asciinode *node, int x, int y) +{ + int i, notleft; + if (node == NULL) return; + notleft = (node->parent_dir != -1); + rprofile[y] = MAX(rprofile[y], x+((node->lablen-notleft)/2)); + if (node->right != NULL) + { + for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++) + { + rprofile[y+i] = MAX(rprofile[y+i], x+i); + } + } + compute_rprofile(node->left, x-node->edge_length-1, y+node->edge_length+1); + compute_rprofile(node->right, x+node->edge_length+1, y+node->edge_length+1); +} + +//This function fills in the edge_length and +//height fields of the specified tree +void compute_edge_lengths(asciinode *node) +{ + int h, hmin, i, delta; + if (node == NULL) return; + compute_edge_lengths(node->left); + compute_edge_lengths(node->right); + + /* first fill in the edge_length of node */ + if (node->right == NULL && node->left == NULL) + { + node->edge_length = 0; + } + else + { + if (node->left != NULL) + { + for (i=0; ileft->height && i < MAX_HEIGHT; i++) + { + rprofile[i] = -INFINITY; + } + compute_rprofile(node->left, 0, 0); + hmin = node->left->height; + } + else + { + hmin = 0; + } + if (node->right != NULL) + { + for (i=0; iright->height && i < MAX_HEIGHT; i++) + { + lprofile[i] = INFINITY; + } + compute_lprofile(node->right, 0, 0); + hmin = MIN(node->right->height, hmin); + } + else + { + hmin = 0; + } + delta = 4; + for (i=0; ileft != NULL && node->left->height == 1) || + (node->right != NULL && node->right->height == 1))&&delta>4) + { + delta--; + } + + node->edge_length = ((delta+1)/2) - 1; + } + + //now fill in the height of node + h = 1; + if (node->left != NULL) + { + h = MAX(node->left->height + node->edge_length + 1, h); + } + if (node->right != NULL) + { + h = MAX(node->right->height + node->edge_length + 1, h); + } + node->height = h; +} + +//This function prints the given level of the given tree, assuming +//that the node has the given x cordinate. +void print_level(asciinode *node, int x, int level) +{ + int i, isleft; + if (node == NULL) return; + isleft = (node->parent_dir == -1); + if (level == 0) + { + for (i=0; i<(x-print_next-((node->lablen-isleft)/2)); i++) + { + printf(" "); + } + print_next += i; + printf("%s", node->label); + print_next += node->lablen; + } + else if (node->edge_length >= level) + { + if (node->left != NULL) + { + for (i=0; i<(x-print_next-(level)); i++) + { + printf(" "); + } + print_next += i; + printf("/"); + print_next++; + } + if (node->right != NULL) + { + for (i=0; i<(x-print_next+(level)); i++) + { + printf(" "); + } + print_next += i; + printf("\\"); + print_next++; + } + } + else + { + print_level(node->left, + x-node->edge_length-1, + level-node->edge_length-1); + print_level(node->right, + x+node->edge_length+1, + level-node->edge_length-1); + } +} + +//prints ascii tree for given Tree structure +void print_ascii_tree(Tree t) +{ + asciinode *proot; + int xmin, i; + if (t == NULL) return; + proot = build_ascii_tree(t); + compute_edge_lengths(proot); + for (i=0; iheight && i < MAX_HEIGHT; i++) + { + lprofile[i] = INFINITY; + } + compute_lprofile(proot, 0, 0); + xmin = 0; + for (i = 0; i < proot->height && i < MAX_HEIGHT; i++) + { + xmin = MIN(xmin, lprofile[i]); + } + for (i = 0; i < proot->height; i++) + { + print_next = 0; + print_level(proot, -xmin, i); + printf("\n"); + } + if (proot->height >= MAX_HEIGHT) + { + printf("(This tree is taller than %d, and may be drawn incorrectly.)\n", MAX_HEIGHT); + } + free_ascii_tree(proot); +} diff --git a/Computer_Science/data_structures/chapter_4/print_ascii_tree.h b/Computer_Science/data_structures/chapter_4/print_ascii_tree.h new file mode 100644 index 0000000..12eed6a --- /dev/null +++ b/Computer_Science/data_structures/chapter_4/print_ascii_tree.h @@ -0,0 +1,22 @@ +#ifndef _PRINT_ASCII_TREE_H +#define _PRINT_ASCII_TREE_H + +struct asciinode_struct; +typedef struct asciinode_struct asciinode; +typedef SearchTree Tree; + +#define MAX_HEIGHT 1000 +#define INFINITY (1 << 20) + +int MIN (int X, int Y); +int MAX (int X, int Y); +asciinode *build_ascii_tree_recursive(Tree t); +asciinode *build_ascii_tree(Tree t); +void free_ascii_tree(asciinode *node); +void compute_lprofile(asciinode *node, int x, int y); +void compute_rprofile(asciinode *node, int x, int y); +void compute_edge_lengths(asciinode *node); +void print_level(asciinode *node, int x, int level); +void print_ascii_tree(Tree t); + +#endif -- cgit v1.2.3