binary tree (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 | #ifndef _BINARY_TREE_ #define _BINARY_TREE_ struct Binary_Tree_Node_Type { char data; 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 | #ifndef _BINARY_TREE_TRAVERSAL_RECURSIVE_ #define _BINARY_TREE_TRAVERSAL_RECURSIVE_ #include "binarytree.h" void Preorder_Traversal_Recursive_Binary_Tree(Binary_Tree* Pointer_Binary_Tree); void Preorder_Traversal_Recursive_Binary_Tree_Node(Binary_Tree_Node* Pointer_Root_Node); void Inorder_Traversal_Recursive_Binary_Tree(Binary_Tree* Pointer_Binary_Tree); void Inorder_Traversal_Recursive_Binary_Tree_Node(Binary_Tree_Node* Pointer_Root_Node); void Postorder_Traversal_Recursive_Binary_Tree(Binary_Tree* Pointer_Binary_Tree); void Postorder_Traversal_Recursive_Binary_Tree_Node(Binary_Tree_Node* Pointer_Root_Node); #endif // !_BINARY_TREE_TRAVERSAL_RECURSIVE_ | 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 | #include <stdio.h> #include <stdlib.h> #include "binarytree.h" Binary_Tree* Make_Binary_Tree(Binary_Tree_Node Root_Node) { Binary_Tree* Pointer_Return = NULL; (Binary_Tree*)Pointer_Return = (Binary_Tree*)malloc(1 * sizeof(Binary_Tree)); if ((Binary_Tree*)Pointer_Return == NULL) { printf("Error! Dynamic memory allocation. 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. 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) 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()\n"); 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) return NULL; else if ((struct Binary_Tree_Node_Type*)Pointer_Parent_Node->Pointer_Right_Child != NULL) { printf("Error! The node alreary 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*)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((struct Binary_Tree_Node_Type*) 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; Delete_Binary_Tree_Node((struct Binary_Tree_Ndoe_Type*)Pointer_Node->Pointer_Left_Child); Delete_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Node->Pointer_Right_Child); free((Binary_Tree_Node*)Pointer_Node); } | 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 | #include <stdio.h> #include <stdlib.h> #include "binarytree.h" #include "binarytreetraversalrec.h" void Preorder_Traversal_Recursive_Binary_Tree(Binary_Tree* Pointer_Binary_Tree) { if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return; Preorder_Traversal_Recursive_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Binary_Tree->Pointer_Root_Node); return; } void Preorder_Traversal_Recursive_Binary_Tree_Node(Binary_Tree_Node* Pointer_Root_Node) { if ((Binary_Tree*)Pointer_Root_Node == NULL) return; printf("%c ", Pointer_Root_Node->data); Preorder_Traversal_Recursive_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Root_Node->Pointer_Left_Child); Preorder_Traversal_Recursive_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Root_Node->Pointer_Right_Child); return; } void Inorder_Traversal_Recursive_Binary_Tree(Binary_Tree* Pointer_Binary_Tree) { if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return; Inorder_Traversal_Recursive_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Binary_Tree->Pointer_Root_Node); return; } void Inorder_Traversal_Recursive_Binary_Tree_Node(Binary_Tree_Node* Pointer_Root_Node) { if ((Binary_Tree_Node*)Pointer_Root_Node == NULL) return; Inorder_Traversal_Recursive_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Root_Node->Pointer_Left_Child); printf("%c ", Pointer_Root_Node->data); Inorder_Traversal_Recursive_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Root_Node->Pointer_Right_Child); return; } void Postorder_Traversal_Recursive_Binary_Tree(Binary_Tree* Pointer_Binary_Tree) { if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return; Postorder_Traversal_Recursive_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Binary_Tree->Pointer_Root_Node); return; } void Postorder_Traversal_Recursive_Binary_Tree_Node(Binary_Tree_Node* Pointer_Root_Node) { if ((Binary_Tree_Node*)Pointer_Root_Node == NULL) return; Postorder_Traversal_Recursive_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Root_Node->Pointer_Left_Child); Postorder_Traversal_Recursive_Binary_Tree_Node((struct Binary_Tree_Node_Type*)Pointer_Root_Node->Pointer_Right_Child); printf("%c ", Pointer_Root_Node->data); 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 | #include <stdio.h> #include <stdlib.h> #include "binarytree.h" #include "binarytreetraversalrec.h" Binary_Tree* Create_Example_Binary_Tree(void); int main(int argc, char** argv) { Binary_Tree* Pointer_Binary_Tree = (Binary_Tree*)Create_Example_Binary_Tree(); if ((Binary_Tree*)Pointer_Binary_Tree == NULL) return -1; printf("Predrder Recursive Traversal\n"); Preorder_Traversal_Recursive_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); printf("\nInorder Recursive Traversal\n"); Inorder_Traversal_Recursive_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); printf("\nPostorder Recursive Traversal\n"); Postorder_Traversal_Recursive_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); printf("\n"); Delete_Binary_Tree((Binary_Tree*)Pointer_Binary_Tree); return 0; } Binary_Tree* Create_Example_Binary_Tree(void) { Binary_Tree_Node* Pointer_Node_A = NULL, *Pointer_Node_B = NULL, *Pointer_Node_C = NULL, *Pointer_Node_D = NULL, *Pointer_Node_E = NULL, *Pointer_Node_F = NULL, *Pointer_Node_G = NULL, *Pointer_Node_H = NULL, *Pointer_Node_I = NULL, *Pointer_Node_J = NULL, *Pointer_Node_K = NULL, *Pointer_Node_L = NULL, *Pointer_Node_M = NULL; Binary_Tree_Node node = { 0, }; node.data = 'A'; Binary_Tree* Pointer_Return = 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); 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_B != 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); 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_C != 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); 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_D != 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); 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_E != 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_F != NULL) { node.data = 'K'; (Binary_Tree_Node*)Pointer_Node_K = (Binary_Tree_Node*)Insert_Left_Child_Node_Binary_Tree((Binary_Tree_Node*)Pointer_Node_F, node); } if ((Binary_Tree_Node*)Pointer_Node_G != 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); 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); } return (Binary_Tree*)Pointer_Return; } | cs |
0 개의 댓글:
댓글 쓰기