C语言二叉树实例 C语言队列实例 C语言二分查找树实例 C语言二叉树实例 头文件 /* tree.h -- binary search tree */ /* no duplicate items are allowed in this tree */ #ifndef _TREE_H_ #define _TREE_H_ #include <stdbool.h> /* redefine Item as appropriate */ #define SLEN 20 typedef struct item { char petname[SLEN]; char petkind[SLEN]; } Item; #define MAXITEMS 10 typedef struct trnode { Item item; struct trnode * left; /* pointer to right branch */ struct trnode * right; /* pointer to left branch */ } Trnode; typedef struct tree { Trnode * root; /* pointer to root of tree */ int size; /* number of items in tree */ } Tree; /* function prototypes */ /* operation: initialize a tree to empty */ /* preconditions: ptree points to a tree */ /* postconditions: the tree is initialized to empty */ void InitializeTree(Tree * ptree); /* operation: determine if tree is empty */ /* preconditions: ptree points to a tree */ /* postconditions: function returns true if tree is */ /* empty and returns false otherwise */ bool TreeIsEmpty(const Tree * ptree); /* operation: determine if tree is full */ /* preconditions: ptree points to a tree */ /* postconditions: function returns true if tree is */ /* full and returns false otherwise */ bool TreeIsFull(const Tree * ptree); /* operation: determine number of items in tree */ /* preconditions: ptree points to a tree */ /* postconditions: function returns number of items in */ /* tree */ int TreeItemCount(const Tree * ptree); /* operation: add an item to a tree */ /* preconditions: pi is address of item to be added */ /* ptree points to an initialized tree */ /* postconditions: if possible, function adds item to */ /* tree and returns true; otherwise, */ /* the function returns false */ bool AddItem(const Item * pi, Tree * ptree); /* operation: find an item in a tree */ /* preconditions: pi points to an item */ /* ptree points to an initialized tree */ /* postconditions: function returns true if item is in */ /* tree and returns false otherwise */ bool InTree(const Item * pi, const Tree * ptree); /* operation: delete an item from a tree */ /* preconditions: pi is address of item to be deleted */ /* ptree points to an initialized tree */ /* postconditions: if possible, function deletes item */ /* from tree and returns true; */ /* otherwise the function returns false*/ bool DeleteItem(const Item * pi, Tree * ptree); /* operation: apply a function to each item in */ /* the tree */ /* preconditions: ptree points to a tree */ /* pfun points to a function that takes*/ /* an Item argument and has no return */ /* value */ /* postcondition: the function pointed to by pfun is */ /* executed once for each item in tree */ void Traverse (const Tree * ptree, void (* pfun)(Item item)); /* operation: delete everything from a tree */ /* preconditions: ptree points to an initialized tree */ /* postconditions: tree is empty */ void DeleteAll(Tree * ptree); #endif 实现文件 /* tree.c -- tree support functions */ #include <string.h> #include <stdio.h> #include <stdlib.h> #include "tree.h" /* local data type */ typedef struct pair { Trnode * parent; Trnode * child; } Pair; /* protototypes for local functions */ static Trnode * MakeNode(const Item * pi); static bool ToLeft(const Item * i1, const Item * i2); static bool ToRight(const Item * i1, const Item * i2); static void AddNode (Trnode * new_node, Trnode * root); static void InOrder(const Trnode * root, void (* pfun)(Item item)); static Pair SeekItem(const Item * pi, const Tree * ptree); static void DeleteNode(Trnode **ptr); static void DeleteAllNodes(Trnode * ptr); /* function definitions */ void InitializeTree(Tree * ptree) { ptree->root = NULL; ptree->size = 0; } bool TreeIsEmpty(const Tree * ptree) { if (ptree->root == NULL) return true; else return false; } bool TreeIsFull(const Tree * ptree) { if (ptree->size == MAXITEMS) return true; else return false; } int TreeItemCount(const Tree * ptree) { return ptree->size; } bool AddItem(const Item * pi, Tree * ptree) { Trnode * new_node; if (TreeIsFull(ptree)) { fprintf(stderr,"Tree is full\n"); return false; /* early return */ } if (SeekItem(pi, ptree).child != NULL) { fprintf(stderr, "Attempted to add duplicate item\n"); return false; /* early return */ } new_node = MakeNode(pi); /* points to new node */ if (new_node == NULL) { fprintf(stderr, "Couldn't create node\n"); return false; /* early return */ } /* succeeded in creating a new node */ ptree->size++; if (ptree->root == NULL) /* case 1: tree is empty */ ptree->root = new_node; /* new node is tree root */ else /* case 2: not empty */ AddNode(new_node,ptree->root); /* add node to tree */ return true; /* successful return */ } bool InTree(const Item * pi, const Tree * ptree) { return (SeekItem(pi, ptree).child == NULL) ? false : true; } bool DeleteItem(const Item * pi, Tree * ptree) { Pair look; look = SeekItem(pi, ptree); if (look.child == NULL) return false; if (look.parent == NULL) /* delete root item */ DeleteNode(&ptree->root); else if (look.parent->left == look.child) DeleteNode(&look.parent->left); else DeleteNode(&look.parent->right); ptree->size--; return true; } void Traverse (const Tree * ptree, void (* pfun)(Item item)) { if (ptree != NULL) InOrder(ptree->root, pfun); } void DeleteAll(Tree * ptree) { if (ptree != NULL) DeleteAllNodes(ptree->root); ptree->root = NULL; ptree->size = 0; } /* local functions */ static void InOrder(const Trnode * root, void (* pfun)(Item item)) { if (root != NULL) { InOrder(root->left, pfun); (*pfun)(root->item); InOrder(root->right, pfun); } } static void DeleteAllNodes(Trnode * root) { Trnode * pright; if (root != NULL) { pright = root->right; DeleteAllNodes(root->left); free(root); DeleteAllNodes(pright); } } static void AddNode (Trnode * new_node, Trnode * root) { if (ToLeft(&new_node->item, &root->item)) { if (root->left == NULL) /* empty subtree */ root->left = new_node; /* so add node here */ else AddNode(new_node, root->left);/* else process subtree*/ } else if (ToRight(&new_node->item, &root->item)) { if (root->right == NULL) root->right = new_node; else AddNode(new_node, root->right); } else /* should be no duplicates */ { fprintf(stderr,"location error in AddNode()\n"); exit(1); } } static bool ToLeft(const Item * i1, const Item * i2) { int comp1; if ((comp1 = strcmp(i1->petname, i2->petname)) < 0) return true; else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0 ) return true; else return false; } static bool ToRight(const Item * i1, const Item * i2) { int comp1; if ((comp1 = strcmp(i1->petname, i2->petname)) > 0) return true; else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0 ) return true; else return false; } static Trnode * MakeNode(const Item * pi) { Trnode * new_node; new_node = (Trnode *) malloc(sizeof(Trnode)); if (new_node != NULL) { new_node->item = *pi; new_node->left = NULL; new_node->right = NULL; } return new_node; } static Pair SeekItem(const Item * pi, const Tree * ptree) { Pair look; look.parent = NULL; look.child = ptree->root; if (look.child == NULL) return look; /* early return */ while (look.child != NULL) { if (ToLeft(pi, &(look.child->item))) { look.parent = look.child; look.child = look.child->left; } else if (ToRight(pi, &(look.child->item))) { look.parent = look.child; look.child = look.child->right; } else /* must be same if not to left or right */ break; /* look.child is address of node with item */ } return look; /* successful return */ } static void DeleteNode(Trnode **ptr) /* ptr is address of parent member pointing to target node */ { Trnode * temp; if ( (*ptr)->left == NULL) { temp = *ptr; *ptr = (*ptr)->right; free(temp); } else if ( (*ptr)->right == NULL) { temp = *ptr; *ptr = (*ptr)->left; free(temp); } else /* deleted node has two children */ { /* find where to reattach right subtree */ for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right) continue; temp->right = (*ptr)->right; temp = *ptr; *ptr =(*ptr)->left; free(temp); } } C语言队列实例 C语言二分查找树实例