1 // content of "BST.h" 2 #include<stdio.h> 3 #include<stdlib.h> 4  5 // definition of the Tree. 6  7 struct Node { 8     int key; 9     struct Node *LeftChild;10     struct Node *RightChild;11 };12 13 typedef struct Node *Position;14 typedef struct Node *SearchTree;15 16 int GetHeight(SearchTree T);17 SearchTree Insert(SearchTree T, int data);18 Position Find(SearchTree T, int data);19 SearchTree Delete(SearchTree T, int data);20 Position FindMin(SearchTree T);21 22 void Error1(char *s);23 24 // Definition of the Queue of Nodes.25 26 typedef Position ElementType;27 28 struct Q_Item {29     ElementType data;30     struct Q_Item *next;31 };32 33 typedef struct Q_Item *PtrToItem;34 35 struct Qrec {36     PtrToItem front, end;37 };38 39 typedef struct Qrec *Queue;40 41 Queue CreateQ(void);42 void InQ(Queue Q, ElementType data);43 ElementType OutQ(Queue Q);44 void Clear(Queue Q);45 int IsEmpty(Queue Q);46 int Power(int x, int n);47 48 // Definition of the Queue of the info needed in PrintDepth.49 50 struct infoNode {51     int pos;52     int space;53     int level;54     int newline;55     struct infoNode *next;56 };57 58 typedef struct infoNode *infoItem;59 60 struct infoQrec {61     infoItem front, end;62 };63 64 typedef struct infoQrec *infoQ;65 66 infoItem MakeItem(int pos, int space, int level, int newline);67 infoQ CreateInfoQ(void);68 void Pushback(infoQ Q, infoItem item);69 infoItem PopFront(infoQ Q);70 int InfoQEmpty(infoQ Q);71 72 // the final function is here73 75 void PrintDepth_2(SearchTree T);

  1 #include"BST.h"  2 #define TRUE 1  3 #define FALSE 0  4   5 // the Queue of TreeNodes.  6   7 Queue CreateQ(void)  8 {  9     Queue Q = (Queue)malloc(sizeof(struct Qrec)); 10     if(!Q) 11         Error1("out of space for Queue for TreeNode"); 12  13     Q->front = Q->end = NULL; 14  15     return Q; 16 } 17  18 void InQ(Queue Q, ElementType data) 19 { 20     PtrToItem newNode = (PtrToItem)malloc(sizeof(ElementType)); 21     if(!newNode) 22     { 23         printf("no space for newNode\n"); 24         exit(1); 25     } 26  27     newNode->data =http://www.mamicode.com/ data; 28     newNode->next = NULL; 29  30     if(!Q->end) 31         Q->front = Q->end = newNode; 32     else 33     { 34         Q->end->next = newNode; 35         Q->end = newNode; 36     } 37 } 38  39 ElementType OutQ(Queue Q) 40 { 41     ElementType data; 42     PtrToItem temp; 43  44     if(!Q->front) 45     { 46         printf("the Queue is empty\n"); 47         exit(1); 48     } 49  50     temp = Q->front; 51     data = http://www.mamicode.com/temp->data; 52  53     if(temp->next == NULL) 54         Q->front = Q->end = NULL; 55     else 56         Q->front = temp->next; 57  58     free(temp); 59  60     return data; 61 } 62  63 void Clear(Queue Q) 64 { 65     PtrToItem curr, temp; 66  67     curr = Q->front; 68  69     while(curr) 70     { 71         temp = curr; 72         curr = curr->next; 73         free(temp); 74     } 75  76     free(Q); 77  78 } 79  80 int IsEmpty(Queue Q) 81 { 82     return Q->front == NULL; 83 } 84  85 int Power(int x, int n) 86 { 87     if(n == 0) 88         return 1; 89     else if( n % 2 ) 90         return Power(x*x, n/2) * x; 91     else 92         return Power(x*x, n/2); 93 } 94  95 // the Queue for printing information. 96  97 infoItem MakeItem(int pos, int space, int level, int newline) 98 { 99     infoItem newItem = (infoItem)malloc(sizeof(struct infoNode));100     if(!newItem)101         Error1("out of space for infoNode");102 103     newItem->pos = pos;104     newItem->space = space;105     newItem->level = level;106     newItem->newline = newline;107     newItem->next = NULL;108 109     return newItem;110 }111 112 infoQ CreateInfoQ(void)113 {114     infoQ Q = (infoQ)malloc(sizeof(struct infoQrec));115     if(!Q)116         Error1("out of space for infoQ");117 118     Q->front = Q->end = NULL;119 120     return Q;121 }122 123 void Pushback(infoQ Q, infoItem item)124 {125     infoItem newItem = item;126 127     if(!Q->end)128         Q->front = Q->end = newItem;129     else130     {131         Q->end->next = newItem;132         Q->end = newItem;133     }134 }135 136 infoItem PopFront(infoQ Q)137 {138     infoItem item;139 140     if(!Q->front)141         Error1("the Queue is empty");142 143     item = Q->front;144 145     if(item->next == NULL)146         Q->front = Q->end = NULL;147     else148         Q->front = item->next;149 150     return item;151 }152 153 void ClearInfoQ(infoQ Q)154 {155     infoItem curr, temp;156 157     curr = Q->front;158 159     while(curr)160     {161         temp = curr;162         curr = curr->next;163         free(temp);164     }165 166     free(Q);167 168 }169 170 int InfoQEmpty(infoQ Q)171 {172     return Q->front == NULL;173 }174 175 176 177 // this function also print the NULL nodes,178 // so the tree will look better and prettier,179 // but also acquire a larger screen because180 // this function divides the screen into181 // many blocks, so the space here is consuming.182 //183 // |  |  |  |44|  |  |  |184 // |  |29|  |  |  |66|  |185 // |11|  |33|  |54|  |77|186 //187 // the key idea of this program is:188 // while the node is not at the bottom,189 // no matter if there is a node in the tree,190 // we create a infoItem with the printing information,191 // and push a NULL into the Queue.192 // when we pop the elements out of the Queue,193 // if the Node it contains is a NULL, we print some194 // blank block, otherwise we print the key in the Node.195 196 197 void PrintDepth(SearchTree T)198 {199     Position currNode;200     Queue Q = CreateQ();201     infoQ IQ = CreateInfoQ();202     infoItem newInfo, currInfo, preInfo;203     int height = GetHeight(T);204     int ScreenWidth = Power(2, height+1);205     int pos, level, space, newline;206     int dataWidth = 1;　　　　// dataWidth is the width of the block.207     int i;208 209     InQ(Q, T);210     level = 1;211     pos = ScreenWidth >> level;212     space = pos;213     newline = TRUE;214 215     newInfo = MakeItem(pos, space, level, newline);216     Pushback(IQ, newInfo);217 218     preInfo = newInfo;219 220     while(!IsEmpty(Q))221     {222         currNode = OutQ(Q);223         currInfo = PopFront(IQ);224 225         if(currInfo->newline)226             printf("\n");227 228         for(i=0; i<currInfo->space; i++)229             printf(" ");            230 231         if(currNode)232             printf("%d",currNode->key);233         else234             printf(" ");235 236         if(currInfo->level < height+1)　　 // if the node is not at the bottom,237         {　　　　　　　　　　　　　　　　　　  //  always create 2 child nodes.238             level = currInfo->level + 1;239             pos = currInfo->pos - (ScreenWidth >> level);  // the left child.240             if(level > preInfo->level)241             {242                 newline = TRUE;243                 space = pos;244             }245             else246             {247                 newline = FALSE;248                 space = pos - preInfo->pos;249             }250 251             space--;       // set aside space for the data to be printed.252             newInfo = MakeItem(pos, space, level, newline);253 254             Pushback(IQ, newInfo);255 256             preInfo = newInfo;257 258             if(currNode)　　// if there is a node in a tree, create the left child.259             {260                 if(currNode->LeftChild)261                     InQ(Q, currNode->LeftChild);262                 else263                     InQ(Q, NULL);264             }265             else　　　　　　// if there is a NULL, create the "left child" for NULL.266                 InQ(Q, NULL);267 268             pos = currInfo->pos + (ScreenWidth >> level); // the right child.269             newline = FALSE;270             space = pos - preInfo->pos;271             space--;272 273             newInfo = MakeItem(pos, space, level, newline);274 275             Pushback(IQ, newInfo);276 277             if(currNode)278             {279                 if(currNode->RightChild)280                     InQ(Q, currNode->RightChild);281                 else282                     InQ(Q, NULL);283             }284             else285                 InQ(Q, NULL);286 287             preInfo = newInfo;288 289         }290 291     }292 293     printf("\n\n");294 }