Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define LINELEN 80 /* maximum length of any input line */
- #define RIGHT 1 /* right traversal of tree */
- #define LEFT 0 /* left traversal of tree */
- #define INSERT 'i' /* command to add a string */
- #define PRINT1 'p' /* command to do plain print */
- #define PRINT2 's' /* command to do snazzy print */
- #define ROTATE 'r' /* command to do a tree edge rotation */
- #define TABULA 't' /* command to tabulate statistics */
- #define FREEIT 'f' /* command to free all space */
- #define ALLOPS "irpstf" /* list of all valid operators */
- #define FILINP 1 /* indicates input coming from a file */
- #define PROMPT "> "
- /****************************************************************/
- /* print out a tree, snazzy formatting */
- void
- do_print_s(tree_t *root) {
- /* Creates history array of max depth of tree */
- int maxdepth = do_t_maxdepth(root,0);
- int *history = (int*)malloc(maxdepth*sizeof(root->key));
- /* Snazzy print function part 2 */
- do_print_s_2(root, 0, history, -1);
- }
- /****************************************************************/
- /* Finds each word in reverse-alphabetic order,
- printing spaces according to it's level */
- void
- do_print_s_2(tree_t *root, int level, int *history, int lr) {
- int p_space = 0;
- /* Adds left or right traversal to history array */
- if (lr == RIGHT) history[level] = RIGHT;
- else history[level] = LEFT;
- /* Double recursive loop traversing down right
- leaves first - reverse alphabetic order */
- if (root != NULL){
- do_print_s_2(root->right, level + 1, history, RIGHT);
- /* Print space according to current level
- Five spaces for the rest of the str and prints
- '|' if needed */
- while(p_space<5*(level)-3){
- /* Checks if '|' is needed */
- if (do_print_s_3(history,p_space,level)){
- printf("|");
- p_space++;
- }
- printf(" ");
- p_space++;
- }
- /* Print string with +-- */
- if (level>0) printf("+--%s\n",root->key);
- else printf("%s\n",root->key);
- do_print_s_2(root->left,level + 1,history, LEFT);
- }
- else{
- /* Print NULL (empty) leaf with +-- */
- if (level>0){
- while(p_space<5*(level)-3){
- if (do_print_s_3(history,p_space,level)){
- printf("|");
- p_space++;
- }
- printf(" ");
- p_space++;
- }
- printf("+--\n");
- }
- }
- }
- /****************************************************************/
- /* Checks if | needs to be printed */
- int
- do_print_s_3(int *history,int p_space, int level){
- /* If tree traverses in alternating directions (i.e right then left
- or right then left) '|' is printed at corresponding level */
- if (level>0 && ((p_space+3) % 5*(level) == 0)
- && history[(p_space-2)/5+1] != history[(p_space-2)/5+2]){
- return 1;
- }
- return 0;
- }
- /* Find the maximum depth of tree */
- int
- do_t_maxdepth(tree_t *root,int level) {
- int lnum = 0, rnum = 0;
- /* Recursive loop adds one at end of tree */
- if (root != NULL) {
- lnum = do_t_maxdepth(root->right, level + 1);
- rnum = do_t_maxdepth(root->left, level + 1);
- }
- /* Returns max level, first root node is 0, however NULL
- nodes also add to total */
- if (lnum > rnum) {
- if (lnum > level) return lnum;
- }
- if (rnum > level) return rnum;
- return level;
- }
- /****************************************************************/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement