binary tree 2 (traversal)
"binarytree.h"
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #ifndef _BINARY_TREE_ #define _BINARY_TREE_ struct Binary_Tree_Node_Type { char data; int visited; struct Binary_Tree_Node_Type* Pointer_Left_Child; struct Binary_Tree_Node_Type* Pointer_Right_Child; }; struct Binary_Tree_Type { struct Binary_Tree_Node_Type* Pointer_Root_Node; }; typedef struct Binary_Tree_Node_Type Binary_Tree_Node; typedef struct Binary_Tree_Type Binary_Tree; Binary_Tree* Make_Binary_Tree(Binary_Tree_Node Root_Node); Binary_Tree_Node* Get_Root_Node_Binary_Tree(Binary_Tree* Pointer_Binary_Tree); Binary_Tree_Node* Insert_Left_Child_Node_Binary_Tree(Binary_Tree_Node* Pointer_Parent_Node, Binary_Tree_Node element); Binary_Tree_Node* Insert_Right_Child_Node_Binary_Tree(Binary_Tree_Node* Pointer_Parent_Node, Binary_Tree_Node element); Binary_Tree_Node* Get_Left_Child_Node_Binary_Tree(Binary_Tree_Node* Pointer_Node); Binary_Tree_Node* Get_Right_Child_Node_Binary_Tree(Binary_Tree_Node* Pointer_Node); void Delete_Binary_Tree(Binary_Tree* Pointer_Binary_Tree); void Delete_Binary_Tree_Node(Binary_Tree_Node* Pointer_Node); #endif // !_BINARY_TREE_ #ifndef _COMMON_TREE_DEFAULT_ #define _COMMON_TREE_DEFAULT_ #define TRUE 1 #define FALSE 0 #endif // !_COMMON_TREE_DEFAULT_ | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #ifndef _LINKED_QUEUE_ #define _LINKED_QUEUE_ #include "binarytree.h" struct Queue_Node_Type { Binary_Tree_Node* data; struct Queue_Node_Type* Pointer_Next; }; struct Linked_Queue_Type { int Current_Element_Count; struct Queue_Node_Type* Pointer_Front_Node; struct Queue_Node_Type* Pointer_Rear_Node; }; typedef struct Queue_Node_Type Queue_Node; typedef struct Linked_Queue_Type Linked_Queue; Linked_Queue* Create_Linked_Queue(void); int Enqueue_Linked_Queue(Linked_Queue* Pointer_Queue, Queue_Node element); Queue_Node* Dequeue_Linked_Queue(Linked_Queue* Pointer_Queue); Queue_Node* Peek_Linked_Queue(Linked_Queue* Pointer_Queue); void Delete_Linked_Queue(Linked_Queue* Pointer_Queue); int Is_Linked_Queue_Full(Linked_Queue* Pointer_Queue); int Is_Linked_Queue_Empty(Linked_Queue* Pointer_Queue); #endif // !_LINKED_QUEUE_ #ifndef _COMMON_QUEUE_DEFAULT_ #define _COMMON_QUEUE_DEFAULT_ #define TRUE 1 #define FALSE 0 #endif // !_COMMON_QUEUE_DEFAULT_ | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #ifndef _LINKED_STACK_ #define _LINKED_STACK_ #include "binarytree.h" struct Stack_Node_Type { Binary_Tree_Node* data; struct Stack_Node_Type* Pointer_Next; }; struct Linked_Stack_Type { int Current_Element_Count; struct Stack_Node_Type* Pointer_Top_Element; }; typedef struct Stack_Node_Type Stack_Node; typedef struct Linked_Stack_Type Linked_Stack; Linked_Stack* Create_Linked_Stack(void); int Push_Linked_Stack(Linked_Stack* Pointer_Stack, Stack_Node element); Stack_Node* Pop_Linked_Stack(Linked_Stack* Pointer_Stack); Stack_Node* Peek_Linked_Stack(Linked_Stack* Pointer_Stack); void Delete_Linked_Stack(Linked_Stack* Pointer_Stack); int Is_Linked_Stack_Full(Linked_Stack* Pointer_Stack); int Is_Linked_Stack_Empty(Linked_Stack* Pointer_Stack); #endif // !_LINKED_STACK_ #ifndef _COMMON_STACK_DEFALUT_ #define _COMMON_STACK_DEFAULT_ #define TRUE 1 #define FALSE 0 #endif // !_COMMON_STACK_DEFALUT_ | cs |
1 2 3 4 5 6 7 8 9 10 11 12 | #ifndef _BINARY_TREE_TRAVERSAL_ #define _BINARY_TREE_TRAVERSAL_ #include "binarytree.h" void Preorder_Traversal_Binary_Tree(Binary_Tree* Pointer_Binary_Tree); void Inorder_Traversal_Binary_Tree(Binary_Tree* Pointer_Binary_Tree); void Postorder_Traversal_Binary_Tree(Binary_Tree* Pointer_Binary_Tree); void Level_Order_Traversal_Binary_Tree(Binary_Tree* Pointer_Binary_Tree); #endif // !_BINARY_TREE_TRAVERSAL_ | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <stdio.h> #include <stdlib.h> #include "binarytree.h" Binary_Tree* Make_Binary_Tree(Binary_Tree_Node Root_Node) { Binary_Tree* Pointer_Return = NULL; Pointer_Return = (Binary_Tree*)malloc(1 * sizeof(Binary_Tree)); if ((Binary_Tree*)Pointer_Return == NULL) { printf("Error! Dynamic memory allocation(1). Make_Binary_Tree()\n"); return NULL; } (struct Binary_Tree_Node_Type*)Pointer_Return->Pointer_Root_Node = (struct Binary_Tree_Node_Type*)malloc(1 * sizeof(struct Binary_Tree_Node_Type)); if ((struct Binary_Tree_Node_Type*)Pointer_Return->Pointer_Root_Node == NULL) { printf("Error! Dynamic memory allocation(2). Make_Binary_Tree()\n"); free((Binary_Tree*)Pointer_Return); return NULL; } *(struct Binary_Tree_Node_Type*) (Pointer_Return->Pointer_Root_Node) = *(struct Binary_Tree_Node_Type*)&Root_Node; (struct Binary_Tree_Node_Type*)Pointer_Return->Pointer_Root_Node->Pointer_Left_Child = NULL; (struct Binary_Tree_Node_Type*)Pointer_Return->Pointer_Root_Node->Pointer_Right_Child = NULL; return (Binary_Tree*)Pointer_Return; } Binary_Tree_Node* Insert_Left_Child_Node_Binary_Tree(Binary_Tree_Node* Pointer_Parent_Node, Binary_Tree_Node element) { if ((Binary_Tree_Node*)Pointer_Parent_Node == NULL) { printf("Error! Binary tree node is null. Insert_Left_Child_Node_Binary_Tree()\n"); return NULL; } else if ((struct Binary_Tree_Node_Type*)Pointer_Parent_Node->Pointer_Left_Child != NULL) { printf("Error! The node already exists. Insert_Left_Child_Node_Binary_Tree()\n"); return NULL; } (struct Binary_Tree_Node_Type*)Pointer_Parent_Node->Pointer_Left_Child = (struct Binary_Tree_Node_Type*)malloc(1 * sizeof(struct Binary_Tree_Node_Type)); if ((struct Binary_Tree_Node_Type*)Pointer_Parent_Node->Pointer_Left_Child == NULL) { printf("Error! Dynamic memory allocation. Insert_Left_Child_Node_Binary_Tree()\m"); return NULL; } *(struct Binary_Tree_Node_Type*)(Pointer_Parent_Node->Pointer_Left_Child) = *(struct Binary_Tree_Node_Type*)&element; (struct Binary_Tree_Node_Type*) Pointer_Parent_Node->Pointer_Left_Child->Pointer_Left_Child = NULL; (struct Binary_Tree_Node_Type*) Pointer_Parent_Node->Pointer_Left_Child->Pointer_Right_Child = NULL; return (Binary_Tree_Node*)Pointer_Parent_Node->Pointer_Left_Child; } Binary_Tree_Node* Insert_Right_Child_Node_Binary_Tree(Binary_Tree_Node* Pointer_Parent_Node, Binary_Tree_Node element) { if ((Binary_Tree_Node*)Pointer_Parent_Node == NULL) { printf("Error! Binary tree node is null. Insert_Right_Child_Node_Binary_Tree()\n"); return NULL; } else if ((struct Binary_Tree_Node_Type*) Pointer_Parent_Node->Pointer_Right_Child != NULL) { printf("Error! The node already exists. Insert_Right_Child_Node_Binary_Tree()\n"); return NULL; } (struct Binary_Tree_Node_Type*)Pointer_Parent_Node->Pointer_Right_Child = (struct Binary_Tree_Node_Type*)malloc(1 * sizeof(struct Binary_Tree_Node_Type)); if ((struct Binary_Tree_Node_Type*)Pointer_Parent_Node->Pointer_Right_Child == NULL) { printf("Error! Dynamic memory allocation. Insert_Right_Child_Node_Binary_Tree()\n"); return NULL; } *(struct Binary_Tree_Node_Type*)Pointer_Parent_Node->Pointer_Right_Child = *(struct Binary_Tree_Node_Type*)&element; (struct Binary_Tree_Node_Type*)Pointer_Parent_Node->Pointer_Right_Child->Pointer_Left_Child = NULL; (struct Binary_Tree_Node_Type*)Pointer_Parent_Node->Pointer_Right_Child->Pointer_Right_Child = NULL; return (Binary_Tree_Node*)Pointer_Parent_Node->Pointer_Right_Child; } Binary_Tree_Node* Get_Root_Node_Binary_Tree(Binary_Tree* Pointer_Binary_Tree) { if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return NULL; return (Binary_Tree_Node*)Pointer_Binary_Tree->Pointer_Root_Node; } Binary_Tree_Node* Get_Left_Child_Node_Binary_Tree(Binary_Tree_Node* Pointer_Node) { if ((Binary_Tree_Node*)Pointer_Node == NULL) return NULL; return (Binary_Tree_Node*)Pointer_Node->Pointer_Left_Child; } Binary_Tree_Node* Get_Right_Child_Node_Binary_Tree(Binary_Tree_Node* Pointer_Node) { if ((Binary_Tree_Node*)Pointer_Node == NULL) return NULL; return (Binary_Tree_Node*) Pointer_Node->Pointer_Right_Child; } void Delete_Binary_Tree(Binary_Tree* Pointer_Binary_Tree) { if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return NULL; Delete_Binary_Tree_Node((Binary_Tree_Node*) Pointer_Binary_Tree->Pointer_Root_Node); free((Binary_Tree*)Pointer_Binary_Tree); return; } void Delete_Binary_Tree_Node(Binary_Tree_Node* Pointer_Node) { if ((Binary_Tree_Node*)Pointer_Node == NULL) return NULL; Delete_Binary_Tree_Node((Binary_Tree_Node*)Pointer_Node->Pointer_Left_Child); Delete_Binary_Tree_Node((Binary_Tree_Node*)Pointer_Node->Pointer_Right_Child); free((Binary_Tree_Node*)Pointer_Node); return; } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include <stdio.h> #include <stdlib.h> #include <string.h> #include "binarytree.h" #include "binarytreelinkedqueue.h" Linked_Queue* Create_Linked_Queue(void) { Linked_Queue* Pointer_Return = (Linked_Queue*)malloc(1 * sizeof(Linked_Queue)); if ((Linked_Queue*)Pointer_Return == NULL) { printf("Error! Dynamic memory allocation. Create_Linked_Queue()\n"); return NULL; } (void*)memset((Linked_Queue*)Pointer_Return, 0, 1 * sizeof(Linked_Queue)); return (Linked_Queue*)Pointer_Return; } int Enqueue_Linked_Queue(Linked_Queue* Pointer_Queue, Queue_Node element) { if ((Linked_Queue*)Pointer_Queue == NULL) { printf("Error! The linked queue is null. Enqueue_Linked_Queue()\n"); return FALSE; } Queue_Node* Pointer_Node = (Queue_Node*)malloc(1 * sizeof(Queue_Node)); if ((Queue_Node*)Pointer_Node == NULL) { printf("Error! Dynamic memory allocation. Enqueue_Linked_Queue()\n"); return FALSE; } *(Queue_Node*)Pointer_Node = *(Queue_Node*)&element; (struct Queue_Node_Type*)Pointer_Node->Pointer_Next = NULL; if (Is_Linked_Queue_Empty((Linked_Queue*)Pointer_Queue) == TRUE) { (struct Queue_Node_Type*)Pointer_Queue->Pointer_Front_Node = (struct Queue_Node_Type*)Pointer_Node; (struct Queue_Node_Type*)Pointer_Queue->Pointer_Rear_Node = (struct Queue_Node_Type*)Pointer_Node; } else { (struct Queue_Node_Type*)Pointer_Queue->Pointer_Rear_Node->Pointer_Next = (struct Queue_Node_Type*)Pointer_Node; (struct Queue_Node_Type*)Pointer_Queue->Pointer_Rear_Node = (struct Queue_Node_Type*)Pointer_Node; } Pointer_Queue->Current_Element_Count++; return TRUE; } Queue_Node* Dequeue_Linked_Queue(Linked_Queue* Pointer_Queue) { if ((Linked_Queue*)Pointer_Queue == NULL) { printf("The linked queue is null. Dequeue_Linked_Queue()\n"); return NULL; } else if (Is_Linked_Queue_Empty((Linked_Queue*)Pointer_Queue) == TRUE) return NULL; Queue_Node* Pointer_Return = (Queue_Node*)Pointer_Queue->Pointer_Front_Node; (struct Queue_Node_Type*)Pointer_Queue->Pointer_Front_Node = (struct Queue_Node_Type*)Pointer_Queue->Pointer_Front_Node->Pointer_Next; (struct Queue_Node_Type*)Pointer_Return->Pointer_Next = NULL; Pointer_Queue->Current_Element_Count--; if (Is_Linked_Queue_Empty((Linked_Queue*)Pointer_Queue) == TRUE) (struct Queue_Node_Type*)Pointer_Queue->Pointer_Rear_Node = NULL; return (Queue_Node*)Pointer_Return; } Queue_Node* Peek_Linked_Queue(Linked_Queue* Pointer_Queue) { if ((Linked_Queue*)Pointer_Queue == NULL) { printf("Error! The linked queue is null. Peek_Linked_Queue()\n"); return NULL; } else if (Is_Linked_Queue_Empty((Linked_Queue*)Pointer_Queue) == TRUE) return NULL; return (Queue_Node*)Pointer_Queue->Pointer_Front_Node; } void Delete_Linked_Queue(Linked_Queue* Pointer_Queue) { if ((Linked_Queue*)Pointer_Queue == NULL) return; Queue_Node* Pointer_Node = (Queue_Node*)Pointer_Queue->Pointer_Front_Node; while ((Queue_Node*)Pointer_Node != NULL) { Queue_Node* Pointer_Delete_Node = (Queue_Node*)Pointer_Node; (Queue_Node*)Pointer_Node = (Queue_Node*)Pointer_Node->Pointer_Next; free((Queue_Node*)Pointer_Delete_Node); } free((Linked_Queue*)Pointer_Queue); return; } int Is_Linked_Queue_Full(Linked_Queue* Pointer_Queue) { return FALSE; } int Is_Linked_Queue_Empty(Linked_Queue* Pointer_Queue) { if ((Linked_Queue*)Pointer_Queue == NULL) return FALSE; else if (Pointer_Queue->Current_Element_Count == 0) return TRUE; return FALSE; } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <stdio.h> #include <stdlib.h> #include <string.h> #include "binarytree.h" #include "binarytreelinkedstack.h" Linked_Stack* Create_Linked_Stack(void) { Linked_Stack* Pointer_Return = (Linked_Stack*)malloc(1 * sizeof(Linked_Stack)); if ((Linked_Stack*)Pointer_Return == NULL) { printf("Error! dynamic memory allocation. Create_Linked_Stack()\n"); return NULL; } (void*)memset((Linked_Stack*)Pointer_Return, 0, 1 * sizeof(Linked_Stack)); return (Linked_Stack*)Pointer_Return; } int Push_Linked_Stack(Linked_Stack* Pointer_Stack, Stack_Node element) { if ((Linked_Stack*)Pointer_Stack == NULL) { printf("Error! The linked stack is null(1). Push_Linked_Stack()\n"); return FALSE; } Stack_Node* Pointer_Node = (Stack_Node*)malloc(1 * sizeof(Stack_Node)); if ((Stack_Node*)Pointer_Node == NULL) { printf("Error! The linked stack is null(2). Push_Linked_Stack()\n"); return FALSE; } (void*)memset((Stack_Node*)Pointer_Node, 0, 1 * sizeof(Stack_Node)); *(Stack_Node*)Pointer_Node = *(Stack_Node*)&element; (struct Stack_Node_Type*)Pointer_Node->Pointer_Next = (struct Stack_Node_Type*)Pointer_Stack->Pointer_Top_Element; (struct Stack_Node_Type*)Pointer_Stack->Pointer_Top_Element = (struct Stack_Node_Type*)Pointer_Node; Pointer_Stack->Current_Element_Count++; return TRUE; } Stack_Node* Pop_Linked_Stack(Linked_Stack* Pointer_Stack) { if ((Linked_Stack*)Pointer_Stack == NULL) { printf("Error! The linked stack is null. Pop_Linked_Stack()\n"); return NULL; } else if (Is_Linked_Stack_Empty((Linked_Stack*)Pointer_Stack) == TRUE) return NULL; Stack_Node* Pointer_Return = (Stack_Node*)Pointer_Stack->Pointer_Top_Element; (struct Stack_Node_Type*) Pointer_Stack->Pointer_Top_Element = (struct Stack_Node_Type*)Pointer_Return->Pointer_Next; (struct Stack_Node_Type*)Pointer_Return->Pointer_Next = NULL; Pointer_Stack->Current_Element_Count--; return (Stack_Node*)Pointer_Return; } Stack_Node* Peek_Linked_Stack(Linked_Stack* Pointer_Stack) { if ((Linked_Stack*)Pointer_Stack == NULL) { printf("Error! The linked stack is null. Peek_Linked_Stack()\n"); return NULL; } else if (Is_Linked_Stack_Empty((Linked_Stack*)Pointer_Stack) == TRUE) return NULL; return (Stack_Node*)Pointer_Stack->Pointer_Top_Element; } void Delete_Linked_Stack(Linked_Stack* Pointer_Stack) { if ((Linked_Stack*)Pointer_Stack == NULL) return; Stack_Node* Pointer_Node = Pointer_Stack->Pointer_Top_Element; while ((Stack_Node*)Pointer_Node != NULL) { Stack_Node* Pointer_Delete_Node = (Stack_Node*)Pointer_Node; (Stack_Node*)Pointer_Node = (struct Stack_Node_Type*)Pointer_Node->Pointer_Next; free((Stack_Node*)Pointer_Delete_Node); } free((Linked_Stack*)Pointer_Stack); return; } int Is_Linked_Stack_Full(Linked_Stack* Pointer_Stack) { return FALSE; } int Is_Linked_Stack_Empty(Linked_Stack* Pointer_Stack) { if ((Linked_Stack*)Pointer_Stack == NULL) return FALSE; else if (Pointer_Stack->Current_Element_Count == 0) return TRUE; return FALSE; } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | #include <stdio.h> #include <stdlib.h> #include "binarytree.h" #include "binarytreelinkedstack.h" #include "binarytreelinkedqueue.h" #include "binarytreetraversal.h" int Push_Linked_Stack_Binary_Tree_Node(Linked_Stack* Pointer_Stack, Binary_Tree_Node* Pointer_Node) { Stack_Node node = { 0, }; (Binary_Tree_Node*)node.data = (Binary_Tree_Node*)Pointer_Node; return Push_Linked_Stack((Linked_Stack*)Pointer_Stack, node); } int Enqueue_Linked_Queue_Binary_Tree_Node(Linked_Queue* Pointer_Queue, Binary_Tree_Node* Pointer_Node) { Queue_Node node = { 0, }; (Binary_Tree_Node*)node.data = (Binary_Tree_Node*)Pointer_Node; return Enqueue_Linked_Queue((Linked_Queue*)Pointer_Queue, node); } void Preorder_Traversal_Binary_Tree(Binary_Tree* Pointer_Binary_Tree) { if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return NULL; Binary_Tree_Node* Pointer_Root_Node = (Binary_Tree_Node*)Get_Root_Node_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); if ((Binary_Tree_Node*)Pointer_Root_Node == NULL) return NULL; Linked_Stack* Pointer_Stack = Create_Linked_Stack(); if ((Linked_Stack*)Pointer_Stack == NULL) return NULL; Push_Linked_Stack_Binary_Tree_Node((Linked_Stack*)Pointer_Stack, (Binary_Tree_Node*)Pointer_Root_Node); while (1) { if (Is_Linked_Stack_Empty((Linked_Stack*)Pointer_Stack) == TRUE) return; Stack_Node* Pointer_Stack_Node = (Stack_Node*)Pop_Linked_Stack((Linked_Stack*)Pointer_Stack); if ((Stack_Node*)Pointer_Stack_Node == NULL) continue; (Binary_Tree_Node*)Pointer_Root_Node = (Binary_Tree_Node*)Pointer_Stack_Node->data; printf("%c ", Pointer_Root_Node->data); Binary_Tree_Node* Pointer_Left_Child_Node = (Binary_Tree_Node*)Get_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Root_Node); if (Pointer_Left_Child_Node != NULL) Push_Linked_Stack_Binary_Tree_Node((Linked_Stack*)Pointer_Stack, (Binary_Tree_Node*)Pointer_Left_Child_Node); Binary_Tree_Node* Pointer_Right_Child_Node = (Binary_Tree_Node*)Get_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Root_Node); if (Pointer_Right_Child_Node != NULL) Push_Linked_Stack_Binary_Tree_Node((Linked_Stack*)Pointer_Stack, (Binary_Tree_Node*)Pointer_Right_Child_Node); free((Stack_Node*)Pointer_Stack_Node); } // end-of-while Delete_Linked_Stack((Linked_Stack*)Pointer_Stack); return; } void Inorder_Traversal_Binary_Tree(Binary_Tree* Pointer_Binary_Tree) { if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return; Binary_Tree_Node* Pointer_Root_Node = (Binary_Tree_Node*)Get_Root_Node_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); if ((Binary_Tree_Node*)Pointer_Root_Node == NULL) return; Linked_Stack* Pointer_Stack = (Linked_Stack*)Create_Linked_Stack(); if ((Linked_Stack*)Pointer_Stack == NULL) return; Binary_Tree_Node* Pointer_Node = (Binary_Tree_Node*)Pointer_Root_Node; while (1) { for (1; (Binary_Tree_Node*)Pointer_Node != NULL; (Binary_Tree_Node*)Pointer_Node = (Binary_Tree_Node*)Get_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node)) { Push_Linked_Stack_Binary_Tree_Node((Linked_Stack*)Pointer_Stack, (Binary_Tree_Node*)Pointer_Node); } if (Is_Linked_Queue_Empty((Linked_Stack*)Pointer_Stack) == TRUE) break; Stack_Node* Pointer_Stack_Node = (Stack_Node*)Pop_Linked_Stack((Linked_Stack*)Pointer_Stack); if ((Stack_Node*)Pointer_Stack_Node == NULL) continue; (Binary_Tree_Node*)Pointer_Node = (Binary_Tree_Node*)Pointer_Stack_Node->data; printf("%c ", Pointer_Node->data); (Binary_Tree_Node*)Pointer_Node = (Binary_Tree_Node*)Get_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node); free((Stack_Node*)Pointer_Stack_Node); } // end-of-while Delete_Linked_Stack((Linked_Stack*)Pointer_Stack); return; } void Postorder_Traversal_Binary_Tree(Binary_Tree* Pointer_Binary_Tree) { if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return; Binary_Tree_Node* Pointer_Root_Node = (Binary_Tree_Node*)Get_Root_Node_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); if ((Binary_Tree_Node*)Pointer_Root_Node == NULL) return; Linked_Stack* Pointer_Stack = (Linked_Stack*)Create_Linked_Stack(); if ((Linked_Stack*)Pointer_Stack == NULL) return; Push_Linked_Stack_Binary_Tree_Node((Linked_Stack*)Pointer_Stack, (Binary_Tree_Node*)Pointer_Root_Node); while (Is_Linked_Stack_Empty((Linked_Stack*)Pointer_Stack) == FALSE) { Stack_Node* Pointer_Stack_Node = (Stack_Node*)Peek_Linked_Stack((Linked_Stack*)Pointer_Stack); if ((Stack_Node*)Pointer_Stack_Node == NULL) continue; (Binary_Tree_Node*)Pointer_Root_Node = (Binary_Tree_Node*)Pointer_Stack_Node->data; Binary_Tree_Node* Pointer_Left_Child_Node = (Binary_Tree_Node*)Get_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Root_Node); if ((Binary_Tree_Node*)Pointer_Left_Child_Node != NULL && Pointer_Left_Child_Node->visited == FALSE) { Push_Linked_Stack_Binary_Tree_Node((Linked_Stack*)Pointer_Stack, (Binary_Tree_Node*)Pointer_Left_Child_Node); continue; } Binary_Tree_Node* Pointer_Right_Child_Node = (Binary_Tree_Node*)Get_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Root_Node); if (Pointer_Right_Child_Node != NULL && Pointer_Right_Child_Node->visited == FALSE) { Push_Linked_Stack_Binary_Tree_Node((Linked_Stack*)Pointer_Stack, (Binary_Tree_Node*)Pointer_Right_Child_Node); continue; } Pointer_Root_Node->visited = TRUE; printf("%c ", Pointer_Root_Node->data); free((Stack_Node*)Pop_Linked_Stack((Linked_Stack*)Pointer_Stack)); } // end-of-while Delete_Linked_Stack((Linked_Stack*)Pointer_Stack); return; } void Level_Order_Traversal_Binary_Tree(Binary_Tree* Pointer_Binary_Tree) { if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return; Binary_Tree_Node* Pointer_Root_Node = (Binary_Tree_Node*)Get_Root_Node_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); if ((Binary_Tree_Node*)Pointer_Root_Node == NULL) return; Linked_Queue* Pointer_Queue = (Linked_Queue*)Create_Linked_Queue(); if ((Linked_Queue*)Pointer_Queue == NULL) return; Enqueue_Linked_Queue_Binary_Tree_Node((Linked_Queue*)Pointer_Queue, (Binary_Tree_Node*)Pointer_Root_Node); while (Is_Linked_Queue_Empty((Linked_Queue*)Pointer_Queue) == FALSE) { Queue_Node* Pointer_Queue_Node = (Queue_Node*)Dequeue_Linked_Queue((Linked_Queue*)Pointer_Queue); if ((Queue_Node*)Pointer_Queue_Node == NULL) continue; (Binary_Tree_Node*)Pointer_Root_Node = (Binary_Tree_Node*)Pointer_Queue_Node->data; if ((Binary_Tree_Node*)Pointer_Root_Node != NULL) printf("%c ", Pointer_Root_Node->data); Binary_Tree_Node* Pointer_Left_Child_Node = (Binary_Tree_Node*)Get_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Root_Node); if ((Binary_Tree_Node*)Pointer_Left_Child_Node != NULL) { Enqueue_Linked_Queue_Binary_Tree_Node((Linked_Queue*)Pointer_Queue, (Binary_Tree_Node*)Pointer_Left_Child_Node); } Binary_Tree_Node* Pointer_Right_Child_Node = (Binary_Tree_Node*)Get_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Root_Node); if ((Binary_Tree_Node*)Pointer_Right_Child_Node != NULL) { Enqueue_Linked_Queue_Binary_Tree_Node((Linked_Queue*)Pointer_Queue, (Binary_Tree_Node*)Pointer_Right_Child_Node); } free((Queue_Node*)Pointer_Queue_Node); } // end-of-while printf("\n"); Delete_Linked_Queue((Linked_Queue*)Pointer_Queue); return; } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <stdio.h> #include <stdlib.h> #include "binarytree.h" #include "binarytreetraversal.h" Binary_Tree* Create_Example_Binary_Tree(void); int main(int argc, char** argv) { Binary_Tree* Pointer_Binary_Tree = NULL; (Binary_Tree*)Pointer_Binary_Tree = (Binary_Tree*)Create_Example_Binary_Tree(); if (Pointer_Binary_Tree == NULL) return -1; printf("Preorder iterative traversal\n"); Preorder_Traversal_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); printf("\nInorder iterative traversal\n"); Inorder_Traversal_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); printf("\nPostorder iterative traversal\n"); Postorder_Traversal_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); printf("\nLevel iterative Traversal\n"); Level_Order_Traversal_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); Delete_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); (Binary_Tree*)Pointer_Binary_Tree = NULL; return 0; } Binary_Tree* Create_Example_Binary_Tree(void) { Binary_Tree_Node node = { 0, }; node.data = 'A'; Binary_Tree* Pointer_Return = (Binary_Tree*)Make_Binary_Tree(node); if ((Binary_Tree*)Pointer_Return == NULL) return NULL; Binary_Tree_Node* Pointer_Node_A = (Binary_Tree_Node*)Get_Root_Node_Binary_Tree((Binary_Tree*)Pointer_Return); node.data = 'B'; Binary_Tree_Node* Pointer_Node_B = (Binary_Tree_Node*)Insert_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_A, node); if ((Binary_Tree_Node*)Pointer_Node_B == NULL) return NULL; node.data = 'C'; Binary_Tree_Node* Pointer_Node_C = (Binary_Tree_Node*)Insert_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_A, node); if ((Binary_Tree_Node*)Pointer_Node_C == NULL) return NULL; node.data = 'D'; Binary_Tree_Node* Pointer_Node_D = (Binary_Tree_Node*)Insert_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_B, node); if ((Binary_Tree_Node*)Pointer_Node_D == NULL) return NULL; node.data = 'E'; Binary_Tree_Node* Pointer_Node_E = (Binary_Tree_Node*)Insert_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_B, node); if ((Binary_Tree_Node*)Pointer_Node_E == NULL) return NULL; node.data = 'F'; Binary_Tree_Node* Pointer_Node_F = (Binary_Tree_Node*)Insert_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_C, node); if ((Binary_Tree_Node*)Pointer_Node_F == NULL) return NULL; node.data = 'G'; Binary_Tree_Node* Pointer_Node_G = (Binary_Tree_Node*)Insert_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_C, node); if ((Binary_Tree_Node*)Pointer_Node_G == NULL) return NULL; node.data = 'H'; Binary_Tree_Node* Pointer_Node_H = (Binary_Tree_Node*)Insert_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_D, node); if ((Binary_Tree_Node*)Pointer_Node_H == NULL) return NULL; node.data = 'I'; Binary_Tree_Node* Pointer_Node_I = (Binary_Tree_Node*)Insert_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_D, node); if ((Binary_Tree_Node*)Pointer_Node_I == NULL) return NULL; node.data = 'J'; Binary_Tree_Node* Pointer_Node_J = (Binary_Tree_Node*)Insert_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_E, node); if ((Binary_Tree_Node*)Pointer_Node_J == NULL) return NULL; node.data = 'K'; Binary_Tree_Node* Pointer_Node_K = (Binary_Tree_Node*)Insert_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_F, node); if ((Binary_Tree_Node*)Pointer_Node_K == NULL) return NULL; node.data = 'L'; Binary_Tree_Node* Pointer_Node_L = (Binary_Tree_Node*)Insert_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_G, node); if ((Binary_Tree_Node*)Pointer_Node_L == NULL) return NULL; node.data = 'M'; Binary_Tree_Node* Pointer_Node_M = (Binary_Tree_Node*)Insert_Right_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_G, node); if ((Binary_Tree_Node*)Pointer_Node_M == NULL) return NULL; return (Binary_Tree*)Pointer_Return; } | cs |
0 개의 댓글:
댓글 쓰기