Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- private CampTreeNode deleteHelp(CampTreeNode current, Camper key) {
- CampTreeNode root = current; // assign original root to variable root
- CampTreeNode parent = null;
- while (current != null) {
- if (current.getData().equals(key)) { // if node found
- if (current.getLeftNode() == null && current.getRightNode() == null) {
- // if current node is leaf
- if (parent == null) { // if no parent, current is root
- current = null;
- root = null;
- }
- else if (parent.getLeftNode().equals(current)) { // if current is a left child
- parent.setLeftNode(null); // remove left child
- current = null;
- }
- else { // if current is a right child
- parent.setRightNode(null); // remove right child
- current = null;
- }
- }
- else if (current.getLeftNode() != null && current.getRightNode() == null) {
- // if current node only has a left child
- if (parent == null) { // if current is root
- root = current.getLeftNode(); // root assigned to current's only child
- current = null;
- }
- else if (parent.getLeftNode().equals(current)) { // if current is a left child
- // remove current node and assign parent's left child to current's left child
- parent.setLeftNode(current.getLeftNode());
- current = null;
- }
- else { // if current is a right child
- // remove current node and assign parent's right child to current's left child
- parent.setRightNode(current.getLeftNode());
- current = null;
- }
- }
- else if (current.getLeftNode() == null && current.getRightNode() != null) {
- // if current node only has a right child
- if (parent == null) { // if current is root
- root = current.getRightNode(); // root assigned to current's only child
- current = null;
- }
- else if (parent.getLeftNode().equals(current)) { // if current is a left child
- // remove current node and assign parent's left child to current's right child
- parent.setLeftNode(current.getRightNode());
- current = null;
- }
- else { // if current is a right child
- // remove current node and assign parent's right child to current's right child
- parent.setRightNode(current.getRightNode());
- current = null;
- }
- }
- else { // if current has two children
- // Find successor (leftmost child of right tree
- CampTreeNode suc = current.getRightNode();
- while (suc.getLeftNode() != null) { // sets suc to leftmost child of right tree of current
- suc = suc.getLeftNode();
- }
- Camper sucData = suc.getData(); // backup of successor's data
- deleteHelp(root, sucData); // remove successor
- current.setData(sucData); // assign current's data with successor's data
- current = null;
- }
- }
- else if (current.getData().compareTo(key) < 0) { // if current < key
- parent = current;
- current = current.getRightNode(); // search right
- }
- else { // if current > key
- parent = current;
- current = current.getLeftNode(); // search left
- }
- }
- return root;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement