#include <stdio.h> #include <malloc.h> #define QUEUE_SIZE 5 /** * Binary tree node. */ typedef struct BTNode{
char element; BTNode* left; BTNode* right; }BTNode, *BTNodePtr; /** * A queue with a number of pointers. */ typedef struct BTNodePtrQueue{
BTNodePtr* nodePtrs; int front; int rear; }BTNodePtrQueue, *QueuePtr; /** * Initialize the queue. */ QueuePtr initQueue(){
QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue)); resultQueuePtr->nodePtrs = (BTNodePtr*)malloc(QUEUE_SIZE * sizeof(BTNodePtr)); resultQueuePtr->front = 0; resultQueuePtr->rear = 1; return resultQueuePtr; }//Of initQueue /** * Is the queue empty? */ bool isQueueEmpty(QueuePtr paraQueuePtr){
if ((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear) {
return true; }//Of if return false; }//Of isQueueEmpty /** * Add a pointer to the queue. */ void enqueue(QueuePtr paraQueuePtr, BTNodePtr paraBTNodePtr){
printf("front = %d, rear = %d.\r\n", paraQueuePtr->front, paraQueuePtr->rear); if ((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE) {
printf("Error, trying to enqueue %c. queue full.\r\n", paraBTNodePtr->element); return; }//Of if paraQueuePtr->nodePtrs[paraQueuePtr->rear] = paraBTNodePtr; paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE; printf("enqueue %c ends.\r\n", paraBTNodePtr->element); }//Of enqueue /** * Remove an element from the queue and return. */ BTNodePtr dequeue(QueuePtr paraQueuePtr){
if (isQueueEmpty(paraQueuePtr)) {
printf("Error, empty queue\r\n"); return NULL; }//Of if paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE; //BTNodePtr tempPtr = paraQueuePtr->nodePtrs[paraQueuePtr->front + 1]; printf("dequeue %c ends.\r\n", paraQueuePtr->nodePtrs[paraQueuePtr->front]->element); return paraQueuePtr->nodePtrs[paraQueuePtr->front]; }//Of dequeue /** * Construct a BTNode using the given char. */ BTNodePtr constructBTNode(char paraChar){
BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(BTNode)); resultPtr->element = paraChar; resultPtr->left = NULL; resultPtr->right = NULL; return resultPtr; }//Of constructBTNode /** * Construct a binary tree using the given string. */ BTNodePtr stringToBTree(char* paraString){
int i; char ch; //Use a queue to manage the pointers QueuePtr tempQueuePtr = initQueue(); BTNodePtr resultHeader; BTNodePtr tempParent, tempLeftChild, tempRightChild; i = 0; ch = paraString[i]; resultHeader = constructBTNode(ch); enqueue(tempQueuePtr, resultHeader); while(!isQueueEmpty(tempQueuePtr)) {
tempParent = dequeue(tempQueuePtr); //The left child i ++; ch = paraString[i]; if (ch == '#') {
tempParent->left = NULL; } else {
tempLeftChild = constructBTNode(ch); enqueue(tempQueuePtr, tempLeftChild); tempParent->left = tempLeftChild; }//Of if //The right child i ++; ch = paraString[i]; if (ch == '#') {
tempParent->right = NULL; } else {
tempRightChild = constructBTNode(ch); enqueue(tempQueuePtr, tempRightChild); tempParent->right = tempRightChild; }//Of if }//Of while return resultHeader; }//Of stringToBTree /** * Levelwise. */ void levelwise(BTNodePtr paraTreePtr){
//Use a queue to manage the pointers char tempString[100]; int i = 0; QueuePtr tempQueuePtr = initQueue(); BTNodePtr tempNodePtr; enqueue(tempQueuePtr, paraTreePtr); while(!isQueueEmpty(tempQueuePtr)) {
tempNodePtr = dequeue(tempQueuePtr); //For output. tempString[i] = tempNodePtr->element; i ++; if (tempNodePtr->left != NULL){
enqueue(tempQueuePtr, tempNodePtr->left); }//Of if if (tempNodePtr->right != NULL){
enqueue(tempQueuePtr, tempNodePtr->right); }//Of if }//Of while tempString[i] = '\0'; printf("Levelwise: %s\r\n", tempString); }//Of levelwise /** * Preorder. */ void preorder(BTNodePtr tempPtr){
if (tempPtr == NULL){
return; }//Of if printf("%c", tempPtr->element); preorder(tempPtr->left); preorder(tempPtr->right); }//Of preorder /** * Inorder. */ void inorder(BTNodePtr tempPtr){
if (tempPtr == NULL) {
return; }//Of if inorder(tempPtr->left); printf("%c", tempPtr->element); inorder(tempPtr->right); }//Of inorder /** * Post order. */ void postorder(BTNodePtr tempPtr){
if (tempPtr == NULL) {
return; }//Of if postorder(tempPtr->left); postorder(tempPtr->right); printf("%c", tempPtr->element); }//Of postorder /** * The entrance. */ int main(){
BTNodePtr tempHeader; tempHeader = constructBTNode('c'); printf("There is only one node. Preorder visit: "); preorder(tempHeader); printf("\r\n"); char* tempString = "acde#bf######"; tempHeader = stringToBTree(tempString); printf("Preorder: "); preorder(tempHeader); printf("\r\n"); printf("Inorder: "); inorder(tempHeader); printf("\r\n"); printf("Postorder: "); postorder(tempHeader); printf("\r\n"); printf("Levelwise: "); levelwise(tempHeader); printf("\r\n"); return 1; }//Of main dequeue e ends.
dequeue b ends.
dequeue f ends.
Preorder: acedbf
Inorder: ecabdf
Postorder: ecbfda
Levelwise: front = 0, rear = 1.
enqueue a ends.
dequeue a ends.
front = 1, rear = 2.
enqueue c ends.
front = 1, rear = 3.
enqueue d ends.
dequeue c ends.
front = 2, rear = 4.
enqueue e ends.
dequeue d ends.
front = 3, rear = 0.
enqueue b ends.
front = 3, rear = 1.
enqueue f ends.
dequeue e ends.
dequeue b ends.
dequeue f ends.
Levelwise: acdebf.
dequeue e ends.
dequeue b ends.
dequeue f ends.
Preorder: acedbf
Inorder: ecabdf
Postorder: ecbfda
Levelwise: front = 0, rear = 1.
enqueue a ends.
dequeue a ends.
front = 1, rear = 2.
enqueue c ends.
front = 1, rear = 3.
enqueue d ends.
dequeue c ends.
front = 2, rear = 4.
enqueue e ends.
dequeue d ends.
front = 3, rear = 0.
enqueue b ends.
front = 3, rear = 1.
enqueue f ends.
dequeue e ends.
dequeue b ends.
dequeue f ends.
Levelwise: acdebf