Algorithm for a removing a node of a binary tree that is unsorted.... How would

Question

Algorithm for a removing a node of a binary tree that is unsorted.... How would I remove a node of a binary tree that is unsorted, meaning it is not a search tree and not balanced (no ordering of nodes by value). It has a structure like so... struct node{ node left; node right; int value; } I believe I am going to have to do some checking and move pointers but I am unsure as to how to go about it. I don't believe there is a need to compare each node value like they do in a Binary SEARCH tree. I know about pointers and " "node.left" and "node.right" but how can I delete a node and still make sure the nodes that come after have not been disconnected from the tree. Algorithm would be great... I will gave rating promptly....

Explanation / Answer

Since the binary tree is unsorted and we are searching for an element x in tree . so x could be any element in the tree ,since the tree is not ordered it could be any where in the tree , it may be the root element, it may be in left subtree, it may be in right subtree too. // this function will remove all occurences o f x in tree ,if x occurs more than once. to delete only one instance of x add a global variable found initialized to false.make it true before or after line 4. execute line 6 if found is false . execute line 7 if found is false. ( do not execute line 6 and 7 in same if statement ,execute line 6 and 7 in its own if statement ,because each execution can change the value of found). Delete ( r,x){ 1) if ( r == null ) 2) return; 3) if ( r.value == x ) 4) DeleteNode(r); 5) else{ 6) Delete(r.left,x); 7) Delete(r.right,x); 8) } } DeleteNode(r) { if r's parent is null ( r is root node. ){ if r is zero children ( r is only node of tree ) simply remove r. if r has one children or two children { find any leaf node in the tree and swap its content with r's value. Now delete that leaf node. ( since tree is unordered it won't make any diff.) } } else { if r hase zero children ( it is leaf ) simply remove r. else r has one child connect r's child to r's parent and remove r. if r has two children { find any leaf node in the tree and swap its content with r's value. Now delete that leaf node. ( since tree is unordered it won't make any diff.) } } }

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.