0
What is the algorithm to delete a child node in binary tree?
Harithaveni
as far as i know u have 4 cases for the node u wanna delete
1.It's a leaf (has no children)
2.It has only left child
3.it has only right child
4.it has both children ,left and right
now, let's work on it :>
set a pointer node to the root
while the element to be deleted doesnt equal the pointer
if it's smaller, move the pointer to the left subtree
if it's large , move the pointer to the right subtree
if pointer reached the end of the tree , null, break the loop (unluckly that means u didnt find the element that should be removed)
end while //(now u must have found the target, the while condition is breaked normally)
// this is case 4
if both children don't equal null
get the most left node in the subtree of the pointer node
assign its value to the pointer node.
remove it (set that most left thing to equal null)
//...case 2
if pointer node.right only equals null
pointer node = pointer node.left
//...case3
if pointer node.left only equals null
pointer node = pointer node.right
//... case 1
if pointer node.left and .right equals null
pointer node.data = null
maybe it doesnt look like any algorithm style ,sorry for that, that's as far as i knw, i doubt case 4 anyways..
Wiki User
∙ 12y ago
Wiki User
∙ 12y agopublic boolean delete (String targetKey)
{
boolean found;
TreeNodeWrapper p = new TreeNodeWrapper();
TreeNodeWrapper c = new TreeNodeWrapper();
TreeNode largest;
TreeNode nextLargest;
found = findNode(targetKey, p, c);
if(found c.get())
p.get().lc = nextLargest;
else
p.get().rc = nextLargest;
}
}
return true;
}
}
Wiki User
∙ 13y agoReplace it with the biggest element of the left sub-tree. Or the smallest element of the right sub-tree.
Add your answer:
Earn +20 pts
Algoritm for deleting the last element from a list?
Given a list and a node to delete, use the following algorithm: // Are we deleting the head node? if (node == list.head) { // Yes -- assign its next node as the new head list.head = node.next } else // The node is not the head node { // Point to the head node prev = list.head // Traverse the list to locate the node that comes immediately before the one we want to delete while (prev.next != node) { prev = prev.next; } end while // Assign the node's next node to the previous node's next node prev.next = node.next; } end if // Before deleting the node, reset its next node node.next = null; // Now delete the node. delete node;
How do you delete a node with two children in binary tree using c?
Use a recursive function. void delete_node (node* n) { /* ensure the given pointer is valid */ if (n==NULL) return; /* recursively delete the left child */ delete_node (n->left); n->left = NULL; /* recursively delete the right child */ delete_node (n->right); n->right = NULL; /* delete the data (assuming the data is a pointer)*/ free (n->data); n->data = NULL; /* finally, delete the node itself */ free (n); n=NULL; }
What is the algorithm to find largest node in a binary search tree?
Since a binary search tree is ordered to start with, to find the largest node simply traverse the tree from the root, choosing only the right node (assuming right is greater and left is less) until you reach a node with no right node. You will then be at the largest node.for (node=root; node!= NULL&&node->right != NULL; node=node->right);This loop will do this. There is no body because all the work is done in the control expressions.
What is parent node?
In programming, a parent node is any node that holds some reference to a child node. The child node may itself be a parent node. A classic example of parent/child node usage is the binary tree, where every node in the tree may hold a reference to up to 2 children. Nodes that have no children are known as leaf nodes.
What is the difference between extended binary tree and a binary search tree?
A strictly binary tree is one where every node other than the leaves has exactly 2 child nodes. Such trees are also known as 2-trees or full binary trees. An extended binary tree is a tree that has been transformed into a full binary tree. This transformation is achieved by inserting special "external" nodes such that every "internal" node has exactly two children.
explain the process of converting tree to binary tree with example?
A binary tree is a type of tree data structure in which each node has at most two children. To convert a tree to a binary tree, we can follow these steps: Choose a root node for the binary tree. This will be the node at the top of the tree, and all other nodes will be connected to it. For each child node of the root node, add it as a left or right child of the root node, depending on its position relative to the root node. For each child node of the root node, repeat step 2 for its child nodes, adding them as left or right children of the appropriate parent node.
Algoritm for deleting the last element from a list?
Given a list and a node to delete, use the following algorithm: // Are we deleting the head node? if (node == list.head) { // Yes -- assign its next node as the new head list.head = node.next } else // The node is not the head node { // Point to the head node prev = list.head // Traverse the list to locate the node that comes immediately before the one we want to delete while (prev.next != node) { prev = prev.next; } end while // Assign the node's next node to the previous node's next node prev.next = node.next; } end if // Before deleting the node, reset its next node node.next = null; // Now delete the node. delete node;
How do you delete a node with two children in binary tree using c?
Use a recursive function. void delete_node (node* n) { /* ensure the given pointer is valid */ if (n==NULL) return; /* recursively delete the left child */ delete_node (n->left); n->left = NULL; /* recursively delete the right child */ delete_node (n->right); n->right = NULL; /* delete the data (assuming the data is a pointer)*/ free (n->data); n->data = NULL; /* finally, delete the node itself */ free (n); n=NULL; }
Algorithm in creating delete method in linked list?
To delete an node in a linked list...If the head node is empty, stop, and return failed.Interate thorugh each member of the list.Remember at each iteration, the address of the privious node.If the current node is the head node or not the desired node, continue to the next iteration.Move the current node's pointer value to the previous node's pointer.Delete the current node, and return success.Return failed..
What is the algorithm to find largest node in a binary search tree?
Since a binary search tree is ordered to start with, to find the largest node simply traverse the tree from the root, choosing only the right node (assuming right is greater and left is less) until you reach a node with no right node. You will then be at the largest node.for (node=root; node!= NULL&&node->right != NULL; node=node->right);This loop will do this. There is no body because all the work is done in the control expressions.
What is parent node?
In programming, a parent node is any node that holds some reference to a child node. The child node may itself be a parent node. A classic example of parent/child node usage is the binary tree, where every node in the tree may hold a reference to up to 2 children. Nodes that have no children are known as leaf nodes.
How can a binary tree be represented in a computer memory?
A binary tree is a tree that has at most two child node. It contain a data field, a pointer to the left and a pointer to the right child.
What is the difference between extended binary tree and a binary search tree?
A strictly binary tree is one where every node other than the leaves has exactly 2 child nodes. Such trees are also known as 2-trees or full binary trees. An extended binary tree is a tree that has been transformed into a full binary tree. This transformation is achieved by inserting special "external" nodes such that every "internal" node has exactly two children.
What is an almost complete binary tree?
An almost complete binary tree is a tree in which each node that has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child.The number of nodes in a binary tree can be found using this formula: n = 2^h Where n is the amount of nodes in the tree, and h is the height of the tree.
Steps of algorithum for delete node in linklist?
To delete a node (this) in a linked list, first you need to find the address of the parent node (parent).Iterate through the list, checking to find if the head pointer (head) or a child node (parent) points to (this).Store the next pointer of (this) in (parent) or (head), as determined by step 2.Delete (this).
General tree to binary tree conversion?
The process of converting the general tree to a binary tree is as follows: * use the root of the general tree as the root of the binary tree * determine the first child of the root. This is the leftmost node in the general tree at the next level * insert this node. The child reference of the parent node refers to this node * continue finding the first child of each parent node and insert it below the parent node with the child reference of the parent to this node. * when no more first children exist in the path just used, move back to the parent of the last node entered and repeat the above process. In other words, determine the first sibling of the last node entered. * complete the tree for all nodes. In order to locate where the node fits you must search for the first child at that level and then follow the sibling references to a nil where the next sibling can be inserted. The children of any sibling node can be inserted by locating the parent and then inserting the first child. Then the above process is repeated.
Is null node equal to leaf node?
No. A leaf node is a node that has no child nodes. A null node is a node pointer that points to the null address (address zero). Since a leaf node has no children, its child nodes are null nodes.
