/***************************************************************************** * * * Beispielprogramm zum Testen des binären Baumes * * ============================================== * * * *****************************************************************************/ #include #include /********************************************************************************* * --------------------- Aufbau des binären Baumes ----------------------- * * * * Eingefuegt wird nach folgendem Schema: * * * * Alle Knoten mit kleineren Schluesselwerten befinden sich im linken Unterbaum,* * und im rechten Unterbaum befinden sich alle Knoten mit gleichen oder * * groesseren Schluesselwerten. Bezug wird auf den Wurzelknotenwert genommen. * * * * Entsprechend kann die Suche dann aufgebaut werden. * * * **********************************************************************************/ /***************************************************************************** * * * Definition der Struktur der Binaerbaumknoten * * * *****************************************************************************/ typedef struct BiTreeNode_Struct { int count; struct BiTreeNode_Struct *left; struct BiTreeNode_Struct *right; } BiTreeNode; /***************************************************************************** * * * Definition der Struktur eines Binaerbaumes * * * *****************************************************************************/ typedef struct BiTree_Struct { int size; BiTreeNode *root; } BiTree; /******************************************************************************** * * * ------------------- Verwendete & nützliche Makros: --------------------- * * * *********************************************************************************/ #define bitree_size(tree) ((tree)->size) #define bitree_root(tree) ((tree)->root) #define bitree_is_eob(node) ((node) == NULL) #define bitree_is_leaf(node) ((node)->left == NULL && (node)->right == NULL) #define bitree_data(node) ((node)->count) #define bitree_left(node) ((node)->left) #define bitree_right(node) ((node)->right) /***************************************************************************** * * * --------------------------- Schnittstellen --------------------------- * * * *****************************************************************************/ void bitree_init(BiTree *tree); void bitree_destroy(BiTree *tree); int bitree_insert_left(BiTree *tree, BiTreeNode *node, int count); int bitree_insert_right(BiTree *tree, BiTreeNode *node, int count); void bitree_remove_left(BiTree *tree, BiTreeNode *node); void bitree_remove_right(BiTree *tree, BiTreeNode *node); int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, int count); int preorder(const BiTreeNode *node); int inorder(const BiTreeNode *node); int postorder(const BiTreeNode *node); /***************************************************************************** * * * ------------------------------ bitree_init ----------------------------- * * * *****************************************************************************/ void bitree_init(BiTree *tree) { /* Initialisierung des Binärbaumes */ tree->size = 0; tree->root = NULL; } /***************************************************************************** * * * ---------------------------- bitree_destroy ---------------------------- * * * *****************************************************************************/ void bitree_destroy(BiTree *tree) { /* alle Knoten loeschen*/ bitree_remove_left(tree, NULL); } /***************************************************************************** * * * ---------------------------- bitree_insert_left ------------------------ * * * *****************************************************************************/ int bitree_insert_left(BiTree *tree, BiTreeNode *node, int count) { BiTreeNode *new_node, **position; /*Bestimmen wo eingefuegt werden muss*/ if (node == NULL) { /*An der Wurzel ist nur bei einem leeren Baum das Einfuegen erlaubt*/ if (bitree_size(tree) > 0) return -1; position = &tree->root; } else { /*Nur am Ende eines Zweiges ist das Einfuegen erlaubt*/ if (bitree_left(node) != NULL) return -1; position = &node->left; } /* Speicherreservierung für den Knoten*/ if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL) return -1; /*Einfuegen des Knotens*/ new_node->count = count; new_node->left = NULL; new_node->right = NULL; *position = new_node; /* Baumgroesse anpassen*/ tree->size++; return 0; } /***************************************************************************** * * * --------------------------- bitree_insert_right ------------------------ * * * *****************************************************************************/ int bitree_insert_right(BiTree *tree, BiTreeNode *node, int count) { BiTreeNode *new_node, **position; /*Bestimmen wo eingefuegt werden muss*/ if (node == NULL) { /*An der Wurzel ist nur bei einem leeren Baum das Einfuegen erlaubt*/ if (bitree_size(tree) > 0) return -1; position = &tree->root; } else { /*Nur am Ende eines Zweiges ist das Einfuegen erlaubt*/ if (bitree_right(node) != NULL) return -1; position = &node->right; } /* Speicherreservierung für den Knoten*/ if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL) return -1; /*Einfuegen des Knotens*/ new_node->count = count; new_node->left = NULL; new_node->right = NULL; *position = new_node; /* Baumgroesse anpassen*/ tree->size++; return 0; } /***************************************************************************** * * * ---------------------------- bitree_remove_left ------------------------ * * * *****************************************************************************/ void bitree_remove_left(BiTree *tree, BiTreeNode *node) { BiTreeNode **position; /* Vorsicht bei einem leeren Baum */ if (bitree_size(tree) == 0) return; /*Bestimmen wo geloescht werden muss*/ if (node == NULL) position = &tree->root; else position = &node->left; /* Den Knoten loeschen*/ if (*position != NULL) { /*Die linken und rechten Nachfolger auch loeschen*/ bitree_remove_left(tree, *position); bitree_remove_right(tree, *position); free(*position); *position = NULL; /* Baumgroesse anpassen*/ tree->size--; } return; } /***************************************************************************** * * * --------------------------- bitree_remove_right ------------------------ * * * *****************************************************************************/ void bitree_remove_right(BiTree *tree, BiTreeNode *node) { BiTreeNode **position; /* Vorsicht bei einem leeren Baum */ if (bitree_size(tree) == 0) return; /*Bestimmen wo geloescht werden muss*/ if (node == NULL) position = &tree->root; else position = &node->right; /* Den Knoten loeschen*/ if (*position != NULL) { /*Die linken und rechten Nachfolger auch loeschen*/ bitree_remove_left(tree, *position); bitree_remove_right(tree, *position); free(*position); *position = NULL; /* Baumgroesse anpassen*/ tree->size--; } return; } /***************************************************************************** * * * ----------------------------- bitree_merge ----------------------------- * * * *****************************************************************************/ int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, int count) { /*Initialisierung des neuen Baumes*/ bitree_init(merge); /*Wuzelknoten des neuen Baumes einfuegen*/ if (bitree_insert_left(merge, NULL, count) != 0) { bitree_destroy(merge); return -1; } /*Die beiden Baeume zu einen neuen Baum vereinigen*/ bitree_root(merge)->left = bitree_root(left); bitree_root(merge)->right = bitree_root(right); /* Baumgroesse anpassen*/ merge->size = merge->size + bitree_size(left) + bitree_size(right); /*Die beiden Orginalbaeume duerfen nicht auf die vereinigten Knoten zeigen*/ left->root = NULL; left->size = 0; right->root = NULL; right->size = 0; return 0; } /***************************************************************************** * * * ------------------------------- preorder ------------------------------- * * * *****************************************************************************/ int preorder(const BiTreeNode *node) { if (!bitree_is_eob(node)) { printf("%d\n", node->count); if (!bitree_is_eob(bitree_left(node))) if (preorder(bitree_left(node)) != 0) return -1; if (!bitree_is_eob(bitree_right(node))) if (preorder(bitree_right(node)) != 0) return -1; } return 0; } /***************************************************************************** * * * -------------------------------- inorder ------------------------------- * * * *****************************************************************************/ int inorder(const BiTreeNode *node) { if (!bitree_is_eob(node)) { if (!bitree_is_eob(bitree_left(node))) if (inorder(bitree_left(node)) != 0) return -1; printf("%d\n", node->count); if (!bitree_is_eob(bitree_right(node))) if (inorder(bitree_right(node)) != 0) return -1; } return 0; } /***************************************************************************** * * * ------------------------------- postorder ------------------------------ * * * *****************************************************************************/ int postorder(const BiTreeNode *node) { if (!bitree_is_eob(node)) { if (!bitree_is_eob(bitree_left(node))) if (postorder(bitree_left(node)) != 0) return -1; if (!bitree_is_eob(bitree_right(node))) if (postorder(bitree_right(node)) != 0) return -1; printf("%d\n", node->count); } return 0; } /******************************************************************************** * * * --------------------------- int-Werte einfuegen ------------------------ * * * *********************************************************************************/ int insert_int(BiTree *tree, int i) { BiTreeNode *node, *prev; int direction; /*an der Wurzel beginnen*/ node = tree->root; direction = 0; /*Bis zu den Blättern, also bis node == NULL*/ //while (node) { while (!bitree_is_eob(node)) { /*Vorgaenger merken*/ prev = node; /*Wert schon enthalten -> Fehler*/ if (i == bitree_data(node)) { return -1; } /*einzufuegender Wert ist kleiner als Wert des aktuellen Knotens */ /*dann linken Knoten merken und Richtung=1, also links davon einfuegen */ else if (i < bitree_data(node)) { node = bitree_left(node); direction = 1; } /*einzufuegender Wert ist gleich oder groesser als Wert des aktuellen Knotens */ /*dann rechten Knoten merken und Richtung=2, also rechts davon einfuegen */ else { node = bitree_right(node); direction = 2; } } /*Je nach zuvor bestimmter Richtung wird jetzt der neue Knoten eingefuegt*/ if (direction == 0) return bitree_insert_left(tree, NULL, i); if (direction == 1) return bitree_insert_left(tree, prev, i); if (direction == 2) return bitree_insert_right(tree, prev, i); return -1; } /***************************************************************************** * * * ---------------------------- int-Werte suchen---------------------------- * * * *****************************************************************************/ BiTreeNode *search_int(BiTree *tree, int i) { BiTreeNode *node; /*An der Wurzel beginnen*/ node = bitree_root(tree); /*Bis zu den Blättern, also bis node == NULL*/ //while (node) { while (!bitree_is_eob(node)) { /*gesuchten Wert gefunden*/ if (i == bitree_data(node)) { return node; } /*gesuchter Wert ist kleiner als Wert des aktuellen Knotens*/ /*dann gehts links weiter */ else if (i < bitree_data(node)) { node = bitree_left(node); } /*gesuchter Wert ist gleich oder größer als Wert des aktuellen Knotens*/ /*dann gehts rechts weiter */ else { node = bitree_right(node); } } return NULL; } /***************************************************************************** * * * --------------------------------- main --------------------------------- * * * *****************************************************************************/ int main(void) { BiTree tree; BiTreeNode *node; int i; /***************************************************************************** * * * Initialisierung des binären Baumes * * * *****************************************************************************/ printf("Tree initialisieren ...\n"); bitree_init(&tree); printf("Einige Knoten einfuegen\n"); if (insert_int(&tree, 20) != 0) return 1; if (insert_int(&tree, 10) != 0) return 1; if (insert_int(&tree, 30) != 0) return 1; if (insert_int(&tree, 15) != 0) return 1; if (insert_int(&tree, 25) != 0) return 1; if (insert_int(&tree, 70) != 0) return 1; if (insert_int(&tree, 80) != 0) return 1; if (insert_int(&tree, 23) != 0) return 1; if (insert_int(&tree, 26) != 0) return 1; if (insert_int(&tree, 5) != 0) return 1; printf("Baumgroesse: %d\n", bitree_size(&tree)); i = 30; if ((node = search_int(&tree, i)) == NULL) { printf("%03d kann nicht gefunden werden.\n", i); } else { printf("%03d gefunden ... der linke Zweig unterhalb wird geloescht\n", i); bitree_remove_left(&tree, node); printf("Baumgroesse: %d\n", bitree_size(&tree)); } i = 99; if ((node = search_int(&tree, i)) == NULL) { printf("%03d kann nicht gefunden werden.\n", i); } else { printf("%03d gefunden ... der rechte Zweig unterhalb wird geloescht\n", i); bitree_remove_right(&tree, node); printf("Baumgroesse: %d\n", bitree_size(&tree)); } i = 20; if ((node = search_int(&tree, i)) == NULL) { printf("%03d kann nicht gefunden werden.\n", i); } else { printf("%03d gefunden ... der rechte Zweig unterhalb wird geloescht\n", i); bitree_remove_right(&tree, node); printf("Baumgroesse: %d\n", bitree_size(&tree)); } printf("Weitere Knoten einfuegen\n"); if (insert_int(&tree, 55) != 0) return 1; if (insert_int(&tree, 44) != 0) return 1; if (insert_int(&tree, 77) != 0) return 1; if (insert_int(&tree, 11) != 0) return 1; printf("Baumgroesse: %d\n", bitree_size(&tree)); printf("Preorder-Traversierung\n"); preorder(bitree_root(&tree)); printf("Inorder-Traversierung\n"); inorder(bitree_root(&tree)); printf("Postorder-Traversierung\n"); postorder(bitree_root(&tree)); printf("Loeschen des Baumes\n"); bitree_destroy(&tree); return 0; }