 Introduction Home Essays Resources Contact Info Basic CS General AI Chess AI Go AI   Source CodeAI Tips and Tricks Books Links     Binary Search Trees (Up to Basic Computer Science : Data Trees) Binary search trees (also known as just binary trees) are ordered trees in which all nodes have no more than two children. The parent node is always greater than all of the data in the left sub-tree that extends from the left child node, and the parent node is less than all of the data in the right sub-tree that extends from the right child node. Here is the basic framwork for the binary search tree: ```class binTree { public: binTree(void); // Constructor ~binTree(void); // Destructor void add(int item); // Add function void remove(int item); // Remove function bool search(int item); // Search function void print(void); // Print function private: binTreeNode *root; // Root pointer // ... // The extra functions needed for implementation are put here }; class binTreeNode { public: int data; // Actual data binTreeNode *left_child; // Left child pointer binTreeNode *right_child; // Right child pointer }; ``` This code is very similar to the code of the linked list, but the node here is differs from the node to the linked list in that this binTreeNode points to two other nodes instead of just one. Since the left child is always less than the parent and the right child is greater than the parent, the tree can easily print an ordered list of all of the elements with the following algorithm, also known as in-order traversal: ```void printTree(binTreeNode *node) { printTree(node->left_child); // Left child first cout << node->data << endl; // Then this node printTree(node->right_child); // Then right child }``` To print the tree, you would call the function with the value of root. Each time, the function would keep calling itself (recursion!) until it reaches the leftmost node, which is the least value in the entire tree. Then, it would cycle through the entire tree, and then the right children, until it reaches the rightmost, or greatest, value in the tree. Other traversals of trees are pre-order and post-order traversals. In pre-order, the root is processed first, then the left children, and then the right children. In post-order, the left children and right children are processed before the root. Try writing the code for the binary tree as an exercise. It's a little tricky this time, especially with the remove() function. (HINT: Most of the functions require helper, or auxiliary, functions. Some, but definitely not all, of the functions may be recursive.)