Skip to content

BinaryTree find(int key) fix #113

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Oct 2, 2017
Merged

BinaryTree find(int key) fix #113

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
e538158
Changed find(int key) method to return null when node is not found, a…
mpokryva Sep 29, 2017
edc51cb
Merge branch 'master' of https://github.com/TheAlgorithms/Java into n…
mpokryva Sep 29, 2017
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
278 changes: 138 additions & 140 deletions data_structures/Trees/BinaryTree.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,20 +1,20 @@
/**
* This entire class is used to build a Binary Tree data structure.
* There is the Node Class and the Tree Class, both explained below.
*
* @author Unknown
*
*/
* This entire class is used to build a Binary Tree data structure.
* There is the Node Class and the Tree Class, both explained below.
*
* @author Unknown
*
*/


/**
* This class implements the nodes that will go on the Binary Tree.
* They consist of the data in them, the node to the left, the node
* to the right, and the parent from which they came from.
*
* @author Unknown
*
*/
* This class implements the nodes that will go on the Binary Tree.
* They consist of the data in them, the node to the left, the node
* to the right, and the parent from which they came from.
*
* @author Unknown
*
*/
class Node{
/** Data for the node */
public int data;
Expand All @@ -26,10 +26,10 @@ class Node{
public Node parent;

/**
* Constructor of Node
*
* @param value Value to put in the node
*/
* Constructor of Node
*
* @param value Value to put in the node
*/
public Node(int value){
data = value;
left = null;
Expand All @@ -40,56 +40,54 @@ public Node(int value){


/**
* A binary tree is a data structure in which an element
* has two successors(children). The left child is usually
* smaller than the parent, and the right child is usually
* bigger.
*
* @author Unknown
*
*/
* A binary tree is a data structure in which an element
* has two successors(children). The left child is usually
* smaller than the parent, and the right child is usually
* bigger.
*
* @author Unknown
*
*/
class Tree{
/** The root of the Binary Tree */
private Node root;

/**
* Constructor
*/
* Constructor
*/
public Tree(){
root = null;
}

/**
* Method to find a Node with a certain value
*
* @param key Value being looked for
* @return The node if it finds it, otherwise returns the parent
*/
public Node find(int key){
* Method to find a Node with a certain value
*
* @param key Value being looked for
* @return The node if it finds it, otherwise returns the parent
*/
public Node find(int key) {
Node current = root;
Node last = root;
while(current != null){
last = current;
if(key < current.data)
while (current != null) {
if(key < current.data) {
current = current.left;
else if(key > current.data)
} else if(key > current.data) {
current = current.right;
//If you find the value return it
else
} else { // If you find the value return it
return current;
}
}
return last;
return null;
}

/**
* Inserts certain value into the Binary Tree
*
* @param value Value to be inserted
*/
* Inserts certain value into the Binary Tree
*
* @param value Value to be inserted
*/
public void put(int value){
Node newNode = new Node(value);
if(root == null)
root = newNode;
root = newNode;
else{
//This will return the soon to be parent of the value you're inserting
Node parent = find(value);
Expand All @@ -109,29 +107,29 @@ public void put(int value){
}

/**
* Deletes a given value from the Binary Tree
*
* @param value Value to be deleted
* @return If the value was deleted
*/
* Deletes a given value from the Binary Tree
*
* @param value Value to be deleted
* @return If the value was deleted
*/
public boolean remove(int value){
//temp is the node to be deleted
Node temp = find(value);

//If the value doesn't exist
if(temp.data != value)
return false;
return false;

//No children
if(temp.right == null && temp.left == null){
if(temp == root)
root = null;
root = null;

//This if/else assigns the new node to be either the left or right child of the parent
else if(temp.parent.data < temp.data)
temp.parent.right = null;
temp.parent.right = null;
else
temp.parent.left = null;
temp.parent.left = null;
return true;
}

Expand Down Expand Up @@ -162,9 +160,9 @@ else if(temp.left != null && temp.right != null){

//This if/else assigns the new node to be either the left or right child of the parent
if(temp.parent.data < temp.data)
temp.parent.right = successor;
temp.parent.right = successor;
else
temp.parent.left = successor;
temp.parent.left = successor;
return true;
}
}
Expand All @@ -175,96 +173,96 @@ else if(temp.left != null && temp.right != null){
if(temp == root){
root = temp.right; return true;}

temp.right.parent = temp.parent;
temp.right.parent = temp.parent;

//Assigns temp to left or right child
if(temp.data < temp.parent.data)
//Assigns temp to left or right child
if(temp.data < temp.parent.data)
temp.parent.left = temp.right;
else
else
temp.parent.right = temp.right;
return true;
return true;
}
//If it has a left child
else{
if(temp == root){
root = temp.left; return true;}

temp.left.parent = temp.parent;

//Assigns temp to left or right side
if(temp.data < temp.parent.data)
temp.parent.left = temp.left;
else
temp.parent.right = temp.left;
return true;
}
}
}
//If it has a left child
else{
if(temp == root){
root = temp.left; return true;}

temp.left.parent = temp.parent;
/**
* This method finds the Successor to the Node given.
* Move right once and go left down the tree as far as you can
*
* @param n Node that you want to find the Successor of
* @return The Successor of the node
*/
public Node findSuccessor(Node n){
if(n.right == null)
return n;
Node current = n.right;
Node parent = n.right;
while(current != null){
parent = current;
current = current.left;
}
return parent;
}

//Assigns temp to left or right side
if(temp.data < temp.parent.data)
temp.parent.left = temp.left;
else
temp.parent.right = temp.left;
return true;
/**
* Returns the root of the Binary Tree
*
* @return the root of the Binary Tree
*/
public Node getRoot(){
return root;
}
}
}

/**
* This method finds the Successor to the Node given.
* Move right once and go left down the tree as far as you can
*
* @param n Node that you want to find the Successor of
* @return The Successor of the node
*/
public Node findSuccessor(Node n){
if(n.right == null)
return n;
Node current = n.right;
Node parent = n.right;
while(current != null){
parent = current;
current = current.left;
}
return parent;
}
/**
* Prints leftChild - root - rightChild
*
* @param localRoot The local root of the binary tree
*/
public void inOrder(Node localRoot){
if(localRoot != null){
inOrder(localRoot.left);
System.out.print(localRoot.data + " ");
inOrder(localRoot.right);
}
}

/**
* Returns the root of the Binary Tree
*
* @return the root of the Binary Tree
*/
public Node getRoot(){
return root;
}
/**
* Prints root - leftChild - rightChild
*
* @param localRoot The local root of the binary tree
*/
public void preOrder(Node localRoot){
if(localRoot != null){
System.out.print(localRoot.data + " ");
preOrder(localRoot.left);
preOrder(localRoot.right);
}
}

/**
* Prints leftChild - root - rightChild
*
* @param localRoot The local root of the binary tree
*/
public void inOrder(Node localRoot){
if(localRoot != null){
inOrder(localRoot.left);
System.out.print(localRoot.data + " ");
inOrder(localRoot.right);
}
}

/**
* Prints root - leftChild - rightChild
*
* @param localRoot The local root of the binary tree
*/
public void preOrder(Node localRoot){
if(localRoot != null){
System.out.print(localRoot.data + " ");
preOrder(localRoot.left);
preOrder(localRoot.right);
}
}

/**
* Prints rightChild - leftChild - root
*
* @param localRoot The local root of the binary tree
*/
public void postOrder(Node localRoot){
if(localRoot != null){
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data + " ");
/**
* Prints rightChild - leftChild - root
*
* @param localRoot The local root of the binary tree
*/
public void postOrder(Node localRoot){
if(localRoot != null){
postOrder(localRoot.left);
postOrder(localRoot.right);
System.out.print(localRoot.data + " ");
}
}
}
}
}