One reason to use trees might be because you want to store information that naturally forms a hierarchy. Finally, elements with no children are called leaves. For example, ‘a’ is a child of ‘f’, and ‘f’ is the parent of ‘a’. The element directly above something is called its parent. The elements that are directly under an element are called its children. Tree Vocabulary: The topmost node is called root of the tree. Trees: Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees are hierarchical data structures. ISRO CS Syllabus for Scientist/Engineer Exam.ISRO CS Original Papers and Official Keys.GATE CS Original Papers and Official Keys.You can see the implementation of a BST in Java in the post – Binary Search Tree in Java. So, this post was all about the coding implementation of the binary search tree in C. If two children – Find the minimum element of the right subtree – find_minimum(root->right_child). Replace the data of the node to be deleted with the data of this node – root->data = temp->data. Delete node found by the minimum function – delete(root->right_child, temp->data). We have to delete this node but we also have to point its parent to its child, so we are storing its child into a temporary variable – temp = root->right_child and then deleting the node – free(root). – if(root->left_child=NULL) – Only right child exists. If only one child ( (root->left_child=NULL || root->right_child=NULL))– Make the parent of the node to be deleted point to the child. If the tree has no children ( if(root->left_child=NULL & root->right_child=NULL)) – Just delete the node – free(root). Root->right_child = delete(root->right_child, temp->data) Struct node *temp = find_minimum(root->right_child) If(root->left_child=NULL & root->right_child=NULL)Įlse if(root->left_child=NULL || root->right_child=NULL) Root->left_child = delete(root->left_child, x) Root->right_child = delete(root->right_child, x) Struct node* delete(struct node *root, int x) DeleteĪs discussed in Binary Search Tree, the code for the deletion is: The insert function will either return a new node (in case of a null node) or the modified subtree itself ( return root). If the data at the current node is smaller than the data to be inserted, then we will change the right child of the current node with the right subtree obtained with the insert function. Thus, the entire insert function can be summed up as – If the current node is null then just return a new node. So, we will first create a new node which is returned by insert(root->right_child, x) and then make the right child of ‘X’ equal to that node – root->right_child = insert(root->right_child, x). So after searching, if we reach to a null node, then we just insert a new node there – if(root=NULL) → return new_node(x). If the element to be inserted is greater than the data at the node, then we insert it in the right subtree – root->right_child = insert(root->right_child, x). Suppose, we have to insert a new node to the right child of a node ‘X’. We first search for the element and if it is not found at the required place (where it should be) then we just insert a new node at that position. Inserting a new node is similar to searching for an element in a tree. Root->left_child = insert(root->left_child,x) Root->right_child = insert(root->right_child, x) Struct node* insert(struct node *root, int x) If(root=NULL || root->data=x) → If the null value is reached then the element is not in the tree and if the data at the root is equal to x then the element is found.Įlse if(x>root->data) → The element is greater than the data at the root, so we will search in the right subtree – search(root->right_child, x). Otherwise, on the left subtree – search(root->left_child,x). We repeat this process until the element is found or a null value is reached (the element is not in the tree). To search an element we first visit the root and if the element is not found there, then we compare the element with the data of the root and if the element is greater, then it must lie on the right subtree (property of a BST – All elements greater than the data at the node are on the right subtree), otherwise on the left subtree. Search is a function to find any element in the tree. Struct node* search(struct node *root, int x) Also, the concepts behind a binary search tree are explained in the post Binary Search Tree. Here, we will focus on the parts related to the binary search tree like inserting a node, deleting a node, searching, etc. The making of a node and traversals are explained in the post Binary Trees in C: Linked Representation & Traversals. #include #include struct node Explanation
0 kommentar(er)
