Can anyone help me to implement binary search tree with addition ?
- 3 Contributors
- forum2 Replies
- 4 Views
- 8 Years Discussion Span
- comment Latest Post by verruckt24
BestJewSinceJC 700
Try to do it yourself, ask specific questions if you have any.
verruckt24 438
Yes, the information on this URL describes the BST in detail. To add further lets explain what the BST is actually. The BST or a Tree in general in the context of Data Structures, is a collection of Nodes. Where a Node has the following properties:
- Each Node has a data element (sometimes also called as the key)
- Each Node has a left Node which can also be called as a left child or the left sub tree.
- Each Node has a right Node aka right child or the right sub tree.
From this information, following the OO design principles you can create a Node class as follows:
class Node{
int data;
Node leftNode; // left sub tree is itself a Node very much like this.
Node rightNode; // right sub tree is also a Node very much like this.
}
Addition in a BST is the process of finding the right place for an element/key. According to the definition of a BST - all keys in the left sub tree of a node should be smaller than that at the current node and all keys in the right sub tree should be larger than (or equal) to the key in the current node. When you are about to add an element in the tree, you make comparisons that help you decide the correct position of the key in the tree. This process should be carried out something like this:
- Starting with the root of the tree, compare the key to be added, lets say K, to the key in each node, we call the node that we currently are in as the current node.
- If K < key at the current node, move to left else move to right.
- Repeat the above step as long as you keep encountering nodes, when there are no more nodes, say for e.g. that you are about to move to the left but you find that there is no left sub-tree for the current node, you know you have reached the correct position for the key K.
I guess this much is fine for you to get started.
Edited
by verruckt24: n/a