Generic Binary Search Tree Implementation in Java
up vote
0
down vote
favorite
There is an implementation of Binary Search Tree. This is kind of based on Set Theory that duplicates are not allowed but an attempt to adding the same node twice will replace the older node.
BSTNode Class:
package nodes.treeNodes.binaryTreesNode.bstNode;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class BSTNode<T>
{
private BSTNode<T> parent;
private BSTNode<T> leftChild;
private BSTNode<T> rightChild;
private T data;
public BSTNode(T data)
{
this(null, null, null, data);
}
public BSTNode(BSTNode<T> parent, BSTNode<T> leftChild, BSTNode<T> rightChild, T data)
{
this.parent = parent;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.data = data;
}
public BSTNode <T> getParent()
{
return parent;
}
public void setParent(BSTNode <T> parent)
{
this.parent = parent;
}
public BSTNode <T> getLeftChild()
{
return leftChild;
}
public void setLeftChild(BSTNode <T> leftChild)
{
this.leftChild = leftChild;
}
public BSTNode <T> getRightChild()
{
return rightChild;
}
public void setRightChild(BSTNode <T> rightChild)
{
this.rightChild = rightChild;
}
public T getData()
{
return data;
}
public void setData(T data)
{
this.data = data;
}
public void removeChild(BSTNode<T> child)
{
if(child == null) return;
if(this.getRightChild() == child)
{
this.setRightChild(null);
return;
}
if(this.getLeftChild() == child)
this.setLeftChild(null);
}
public Iterator<BSTNode> children()
{
List<BSTNode> childList = new LinkedList<>();
if(this.leftChild != null) childList.add(leftChild);
if(this.rightChild != null) childList.add(rightChild);
return childList.iterator();
}
}
BST Class:
package trees.binaryTrees.bst;
import nodes.treeNodes.binaryTreesNode.bstNode.BSTNode;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
public class BST<T extends Comparable<T>>
{
private BSTNode<T> root;
private int size;
public BST() {}
private BSTNode<T> root()
{
return root;
}
private void addRoot(T data) throws Exception
{
if(root != null) throw new Exception("Root exists is the tree.");
root = new BSTNode <>(data);
size++;
}
public void add(T data) throws Exception
{
BSTNode<T> node = find(data);
if (node == null)
addRoot(data);
else if (node.getData().compareTo(data) > 0)
addLeft(node, data);
else if (node.getData().compareTo(data) < 0)
addRight(node, data);
else node.setData(data);
}
private void addLeft(BSTNode<T> parent, T data)
{
BSTNode<T> left = new BSTNode <>(data);
parent.setLeftChild(left);
left.setParent(parent);
size++;
}
private void addRight(BSTNode<T> parent, T data)
{
BSTNode<T> right = new BSTNode <>(data);
parent.setRightChild(right);
right.setParent(parent);
size++;
}
public void remove(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return;
remove(node);
}
private BSTNode<T> remove(BSTNode<T> node)
{
if (isLeaf(node))
{
BSTNode<T> parent = node.getParent();
if (parent == null) root = null;
else parent.removeChild(node);
size--;
return parent;
}
BSTNode<T> descendant = descendant(node);
promoteDescendant(node, descendant);
return remove(descendant);
}
private void promoteDescendant(BSTNode<T> parent, BSTNode<T> descendant)
{
parent.setData(descendant.getData());
}
private BSTNode<T> descendant(BSTNode<T> parent)
{
BSTNode<T> child = parent.getLeftChild();
if (child != null)
{
while (child.getRightChild() != null) child = child.getRightChild();
return child;
}
child = parent.getRightChild();
if (child != null)
{
while (child.getLeftChild() != null) child = child.getLeftChild();
return child;
}
return child;
}
public T get(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return null;
return node.getData();
}
public boolean contains(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return false;
return true;
}
private BSTNode<T> find(T data)
{
if(root() == null) return null;
return findRecursively(root(), data);
}
private BSTNode<T> findRecursively(BSTNode<T> parent, T data)
{
int comparison = data.compareTo(parent.getData());
if(comparison == 0) return parent;
else if(comparison < 0 && parent.getLeftChild() != null) return findRecursively(parent.getLeftChild(), data);
else if(comparison > 0 && parent.getRightChild() != null) return findRecursively(parent.getRightChild(), data);
return parent;
}
public boolean isEmpty()
{
return size() == 0;
}
public int size()
{
return size;
}
private BSTNode<T> parent(BSTNode<T> child)
{
return child.getParent();
}
private boolean isInternal(BSTNode<T> node)
{
return node.children().hasNext();
}
private boolean isLeaf(BSTNode<T> node)
{
return !isInternal(node);
}
private int depth(BSTNode<T> node)
{
if(isLeaf(node)) return 0;
return depth(node.getParent()) + 1;
}
private int height(BSTNode<T> node)
{
if(isLeaf(node)) return 0;
int maxHeight = 0;
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
int height = height(children.next());
if(height > maxHeight) maxHeight = height;
}
return maxHeight + 1;
}
public int height()
{
if(root == null) return -1;
return height(root);
}
public List<T> preOrder()
{
List<T> list = new LinkedList<>();
preOrder(root, list);
return list;
}
private void preOrder(BSTNode<T> node, List<T> list)
{
if(node == null) return;
list.add(node.getData());
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
preOrder(children.next(), list);
}
}
public List<T> postOrder()
{
List<T> list = new LinkedList <>();
postOrder(root(), list);
return list;
}
private void postOrder(BSTNode<T> node, List<T> list)
{
if(node == null) return;
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
postOrder(children.next(), list);
}
list.add(node.getData());
}
public List<T> levelOrder()
{
List<T> nodeList = new LinkedList <>();
if(root() == null) return nodeList;
Queue<BSTNode> nodeQueue = new ConcurrentLinkedQueue <>();
try
{
nodeList.add(root().getData());
nodeQueue.add(root());
while (!nodeQueue.isEmpty())
{
BSTNode<T> node = nodeQueue.poll();
Iterator<BSTNode> nodeItr = node.children();
while (nodeItr.hasNext())
{
BSTNode<T> treeNode = nodeItr.next();
nodeQueue.add(treeNode);
nodeList.add(treeNode.getData());
}
}
}
catch (Exception ex)
{
System.out.println(ex.getMessage());
}
return nodeList;
}
public List<T> inOrder()
{
List<T> answer = new LinkedList <>();
inOrder(root(), answer);
return answer;
}
private void inOrder(BSTNode<T> node, List<T> list)
{
if (node == null) return;
inOrder(node.getLeftChild(), list);
list.add(node.getData());
inOrder(node.getRightChild(), list);
}
@Override
public String toString()
{
return inOrder().toString();
}
}
java object-oriented tree generics search
asked 9 mins ago
Hamidur Rahman
486
add a comment |
up vote
0
down vote
favorite
There is an implementation of Binary Search Tree. This is kind of based on Set Theory that duplicates are not allowed but an attempt to adding the same node twice will replace the older node.
BSTNode Class:
package nodes.treeNodes.binaryTreesNode.bstNode;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class BSTNode<T>
{
private BSTNode<T> parent;
private BSTNode<T> leftChild;
private BSTNode<T> rightChild;
private T data;
public BSTNode(T data)
{
this(null, null, null, data);
}
public BSTNode(BSTNode<T> parent, BSTNode<T> leftChild, BSTNode<T> rightChild, T data)
{
this.parent = parent;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.data = data;
}
public BSTNode <T> getParent()
{
return parent;
}
public void setParent(BSTNode <T> parent)
{
this.parent = parent;
}
public BSTNode <T> getLeftChild()
{
return leftChild;
}
public void setLeftChild(BSTNode <T> leftChild)
{
this.leftChild = leftChild;
}
public BSTNode <T> getRightChild()
{
return rightChild;
}
public void setRightChild(BSTNode <T> rightChild)
{
this.rightChild = rightChild;
}
public T getData()
{
return data;
}
public void setData(T data)
{
this.data = data;
}
public void removeChild(BSTNode<T> child)
{
if(child == null) return;
if(this.getRightChild() == child)
{
this.setRightChild(null);
return;
}
if(this.getLeftChild() == child)
this.setLeftChild(null);
}
public Iterator<BSTNode> children()
{
List<BSTNode> childList = new LinkedList<>();
if(this.leftChild != null) childList.add(leftChild);
if(this.rightChild != null) childList.add(rightChild);
return childList.iterator();
}
}
BST Class:
package trees.binaryTrees.bst;
import nodes.treeNodes.binaryTreesNode.bstNode.BSTNode;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
public class BST<T extends Comparable<T>>
{
private BSTNode<T> root;
private int size;
public BST() {}
private BSTNode<T> root()
{
return root;
}
private void addRoot(T data) throws Exception
{
if(root != null) throw new Exception("Root exists is the tree.");
root = new BSTNode <>(data);
size++;
}
public void add(T data) throws Exception
{
BSTNode<T> node = find(data);
if (node == null)
addRoot(data);
else if (node.getData().compareTo(data) > 0)
addLeft(node, data);
else if (node.getData().compareTo(data) < 0)
addRight(node, data);
else node.setData(data);
}
private void addLeft(BSTNode<T> parent, T data)
{
BSTNode<T> left = new BSTNode <>(data);
parent.setLeftChild(left);
left.setParent(parent);
size++;
}
private void addRight(BSTNode<T> parent, T data)
{
BSTNode<T> right = new BSTNode <>(data);
parent.setRightChild(right);
right.setParent(parent);
size++;
}
public void remove(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return;
remove(node);
}
private BSTNode<T> remove(BSTNode<T> node)
{
if (isLeaf(node))
{
BSTNode<T> parent = node.getParent();
if (parent == null) root = null;
else parent.removeChild(node);
size--;
return parent;
}
BSTNode<T> descendant = descendant(node);
promoteDescendant(node, descendant);
return remove(descendant);
}
private void promoteDescendant(BSTNode<T> parent, BSTNode<T> descendant)
{
parent.setData(descendant.getData());
}
private BSTNode<T> descendant(BSTNode<T> parent)
{
BSTNode<T> child = parent.getLeftChild();
if (child != null)
{
while (child.getRightChild() != null) child = child.getRightChild();
return child;
}
child = parent.getRightChild();
if (child != null)
{
while (child.getLeftChild() != null) child = child.getLeftChild();
return child;
}
return child;
}
public T get(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return null;
return node.getData();
}
public boolean contains(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return false;
return true;
}
private BSTNode<T> find(T data)
{
if(root() == null) return null;
return findRecursively(root(), data);
}
private BSTNode<T> findRecursively(BSTNode<T> parent, T data)
{
int comparison = data.compareTo(parent.getData());
if(comparison == 0) return parent;
else if(comparison < 0 && parent.getLeftChild() != null) return findRecursively(parent.getLeftChild(), data);
else if(comparison > 0 && parent.getRightChild() != null) return findRecursively(parent.getRightChild(), data);
return parent;
}
public boolean isEmpty()
{
return size() == 0;
}
public int size()
{
return size;
}
private BSTNode<T> parent(BSTNode<T> child)
{
return child.getParent();
}
private boolean isInternal(BSTNode<T> node)
{
return node.children().hasNext();
}
private boolean isLeaf(BSTNode<T> node)
{
return !isInternal(node);
}
private int depth(BSTNode<T> node)
{
if(isLeaf(node)) return 0;
return depth(node.getParent()) + 1;
}
private int height(BSTNode<T> node)
{
if(isLeaf(node)) return 0;
int maxHeight = 0;
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
int height = height(children.next());
if(height > maxHeight) maxHeight = height;
}
return maxHeight + 1;
}
public int height()
{
if(root == null) return -1;
return height(root);
}
public List<T> preOrder()
{
List<T> list = new LinkedList<>();
preOrder(root, list);
return list;
}
private void preOrder(BSTNode<T> node, List<T> list)
{
if(node == null) return;
list.add(node.getData());
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
preOrder(children.next(), list);
}
}
public List<T> postOrder()
{
List<T> list = new LinkedList <>();
postOrder(root(), list);
return list;
}
private void postOrder(BSTNode<T> node, List<T> list)
{
if(node == null) return;
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
postOrder(children.next(), list);
}
list.add(node.getData());
}
public List<T> levelOrder()
{
List<T> nodeList = new LinkedList <>();
if(root() == null) return nodeList;
Queue<BSTNode> nodeQueue = new ConcurrentLinkedQueue <>();
try
{
nodeList.add(root().getData());
nodeQueue.add(root());
while (!nodeQueue.isEmpty())
{
BSTNode<T> node = nodeQueue.poll();
Iterator<BSTNode> nodeItr = node.children();
while (nodeItr.hasNext())
{
BSTNode<T> treeNode = nodeItr.next();
nodeQueue.add(treeNode);
nodeList.add(treeNode.getData());
}
}
}
catch (Exception ex)
{
System.out.println(ex.getMessage());
}
return nodeList;
}
public List<T> inOrder()
{
List<T> answer = new LinkedList <>();
inOrder(root(), answer);
return answer;
}
private void inOrder(BSTNode<T> node, List<T> list)
{
if (node == null) return;
inOrder(node.getLeftChild(), list);
list.add(node.getData());
inOrder(node.getRightChild(), list);
}
@Override
public String toString()
{
return inOrder().toString();
}
}
java object-oriented tree generics search
asked 9 mins ago
Hamidur Rahman
486
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
There is an implementation of Binary Search Tree. This is kind of based on Set Theory that duplicates are not allowed but an attempt to adding the same node twice will replace the older node.
BSTNode Class:
package nodes.treeNodes.binaryTreesNode.bstNode;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class BSTNode<T>
{
private BSTNode<T> parent;
private BSTNode<T> leftChild;
private BSTNode<T> rightChild;
private T data;
public BSTNode(T data)
{
this(null, null, null, data);
}
public BSTNode(BSTNode<T> parent, BSTNode<T> leftChild, BSTNode<T> rightChild, T data)
{
this.parent = parent;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.data = data;
}
public BSTNode <T> getParent()
{
return parent;
}
public void setParent(BSTNode <T> parent)
{
this.parent = parent;
}
public BSTNode <T> getLeftChild()
{
return leftChild;
}
public void setLeftChild(BSTNode <T> leftChild)
{
this.leftChild = leftChild;
}
public BSTNode <T> getRightChild()
{
return rightChild;
}
public void setRightChild(BSTNode <T> rightChild)
{
this.rightChild = rightChild;
}
public T getData()
{
return data;
}
public void setData(T data)
{
this.data = data;
}
public void removeChild(BSTNode<T> child)
{
if(child == null) return;
if(this.getRightChild() == child)
{
this.setRightChild(null);
return;
}
if(this.getLeftChild() == child)
this.setLeftChild(null);
}
public Iterator<BSTNode> children()
{
List<BSTNode> childList = new LinkedList<>();
if(this.leftChild != null) childList.add(leftChild);
if(this.rightChild != null) childList.add(rightChild);
return childList.iterator();
}
}
BST Class:
package trees.binaryTrees.bst;
import nodes.treeNodes.binaryTreesNode.bstNode.BSTNode;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
public class BST<T extends Comparable<T>>
{
private BSTNode<T> root;
private int size;
public BST() {}
private BSTNode<T> root()
{
return root;
}
private void addRoot(T data) throws Exception
{
if(root != null) throw new Exception("Root exists is the tree.");
root = new BSTNode <>(data);
size++;
}
public void add(T data) throws Exception
{
BSTNode<T> node = find(data);
if (node == null)
addRoot(data);
else if (node.getData().compareTo(data) > 0)
addLeft(node, data);
else if (node.getData().compareTo(data) < 0)
addRight(node, data);
else node.setData(data);
}
private void addLeft(BSTNode<T> parent, T data)
{
BSTNode<T> left = new BSTNode <>(data);
parent.setLeftChild(left);
left.setParent(parent);
size++;
}
private void addRight(BSTNode<T> parent, T data)
{
BSTNode<T> right = new BSTNode <>(data);
parent.setRightChild(right);
right.setParent(parent);
size++;
}
public void remove(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return;
remove(node);
}
private BSTNode<T> remove(BSTNode<T> node)
{
if (isLeaf(node))
{
BSTNode<T> parent = node.getParent();
if (parent == null) root = null;
else parent.removeChild(node);
size--;
return parent;
}
BSTNode<T> descendant = descendant(node);
promoteDescendant(node, descendant);
return remove(descendant);
}
private void promoteDescendant(BSTNode<T> parent, BSTNode<T> descendant)
{
parent.setData(descendant.getData());
}
private BSTNode<T> descendant(BSTNode<T> parent)
{
BSTNode<T> child = parent.getLeftChild();
if (child != null)
{
while (child.getRightChild() != null) child = child.getRightChild();
return child;
}
child = parent.getRightChild();
if (child != null)
{
while (child.getLeftChild() != null) child = child.getLeftChild();
return child;
}
return child;
}
public T get(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return null;
return node.getData();
}
public boolean contains(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return false;
return true;
}
private BSTNode<T> find(T data)
{
if(root() == null) return null;
return findRecursively(root(), data);
}
private BSTNode<T> findRecursively(BSTNode<T> parent, T data)
{
int comparison = data.compareTo(parent.getData());
if(comparison == 0) return parent;
else if(comparison < 0 && parent.getLeftChild() != null) return findRecursively(parent.getLeftChild(), data);
else if(comparison > 0 && parent.getRightChild() != null) return findRecursively(parent.getRightChild(), data);
return parent;
}
public boolean isEmpty()
{
return size() == 0;
}
public int size()
{
return size;
}
private BSTNode<T> parent(BSTNode<T> child)
{
return child.getParent();
}
private boolean isInternal(BSTNode<T> node)
{
return node.children().hasNext();
}
private boolean isLeaf(BSTNode<T> node)
{
return !isInternal(node);
}
private int depth(BSTNode<T> node)
{
if(isLeaf(node)) return 0;
return depth(node.getParent()) + 1;
}
private int height(BSTNode<T> node)
{
if(isLeaf(node)) return 0;
int maxHeight = 0;
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
int height = height(children.next());
if(height > maxHeight) maxHeight = height;
}
return maxHeight + 1;
}
public int height()
{
if(root == null) return -1;
return height(root);
}
public List<T> preOrder()
{
List<T> list = new LinkedList<>();
preOrder(root, list);
return list;
}
private void preOrder(BSTNode<T> node, List<T> list)
{
if(node == null) return;
list.add(node.getData());
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
preOrder(children.next(), list);
}
}
public List<T> postOrder()
{
List<T> list = new LinkedList <>();
postOrder(root(), list);
return list;
}
private void postOrder(BSTNode<T> node, List<T> list)
{
if(node == null) return;
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
postOrder(children.next(), list);
}
list.add(node.getData());
}
public List<T> levelOrder()
{
List<T> nodeList = new LinkedList <>();
if(root() == null) return nodeList;
Queue<BSTNode> nodeQueue = new ConcurrentLinkedQueue <>();
try
{
nodeList.add(root().getData());
nodeQueue.add(root());
while (!nodeQueue.isEmpty())
{
BSTNode<T> node = nodeQueue.poll();
Iterator<BSTNode> nodeItr = node.children();
while (nodeItr.hasNext())
{
BSTNode<T> treeNode = nodeItr.next();
nodeQueue.add(treeNode);
nodeList.add(treeNode.getData());
}
}
}
catch (Exception ex)
{
System.out.println(ex.getMessage());
}
return nodeList;
}
public List<T> inOrder()
{
List<T> answer = new LinkedList <>();
inOrder(root(), answer);
return answer;
}
private void inOrder(BSTNode<T> node, List<T> list)
{
if (node == null) return;
inOrder(node.getLeftChild(), list);
list.add(node.getData());
inOrder(node.getRightChild(), list);
}
@Override
public String toString()
{
return inOrder().toString();
}
}
java object-oriented tree generics search
asked 9 mins ago
Hamidur Rahman
486
There is an implementation of Binary Search Tree. This is kind of based on Set Theory that duplicates are not allowed but an attempt to adding the same node twice will replace the older node.
BSTNode Class:
package nodes.treeNodes.binaryTreesNode.bstNode;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class BSTNode<T>
{
private BSTNode<T> parent;
private BSTNode<T> leftChild;
private BSTNode<T> rightChild;
private T data;
public BSTNode(T data)
{
this(null, null, null, data);
}
public BSTNode(BSTNode<T> parent, BSTNode<T> leftChild, BSTNode<T> rightChild, T data)
{
this.parent = parent;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.data = data;
}
public BSTNode <T> getParent()
{
return parent;
}
public void setParent(BSTNode <T> parent)
{
this.parent = parent;
}
public BSTNode <T> getLeftChild()
{
return leftChild;
}
public void setLeftChild(BSTNode <T> leftChild)
{
this.leftChild = leftChild;
}
public BSTNode <T> getRightChild()
{
return rightChild;
}
public void setRightChild(BSTNode <T> rightChild)
{
this.rightChild = rightChild;
}
public T getData()
{
return data;
}
public void setData(T data)
{
this.data = data;
}
public void removeChild(BSTNode<T> child)
{
if(child == null) return;
if(this.getRightChild() == child)
{
this.setRightChild(null);
return;
}
if(this.getLeftChild() == child)
this.setLeftChild(null);
}
public Iterator<BSTNode> children()
{
List<BSTNode> childList = new LinkedList<>();
if(this.leftChild != null) childList.add(leftChild);
if(this.rightChild != null) childList.add(rightChild);
return childList.iterator();
}
}
BST Class:
package trees.binaryTrees.bst;
import nodes.treeNodes.binaryTreesNode.bstNode.BSTNode;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
public class BST<T extends Comparable<T>>
{
private BSTNode<T> root;
private int size;
public BST() {}
private BSTNode<T> root()
{
return root;
}
private void addRoot(T data) throws Exception
{
if(root != null) throw new Exception("Root exists is the tree.");
root = new BSTNode <>(data);
size++;
}
public void add(T data) throws Exception
{
BSTNode<T> node = find(data);
if (node == null)
addRoot(data);
else if (node.getData().compareTo(data) > 0)
addLeft(node, data);
else if (node.getData().compareTo(data) < 0)
addRight(node, data);
else node.setData(data);
}
private void addLeft(BSTNode<T> parent, T data)
{
BSTNode<T> left = new BSTNode <>(data);
parent.setLeftChild(left);
left.setParent(parent);
size++;
}
private void addRight(BSTNode<T> parent, T data)
{
BSTNode<T> right = new BSTNode <>(data);
parent.setRightChild(right);
right.setParent(parent);
size++;
}
public void remove(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return;
remove(node);
}
private BSTNode<T> remove(BSTNode<T> node)
{
if (isLeaf(node))
{
BSTNode<T> parent = node.getParent();
if (parent == null) root = null;
else parent.removeChild(node);
size--;
return parent;
}
BSTNode<T> descendant = descendant(node);
promoteDescendant(node, descendant);
return remove(descendant);
}
private void promoteDescendant(BSTNode<T> parent, BSTNode<T> descendant)
{
parent.setData(descendant.getData());
}
private BSTNode<T> descendant(BSTNode<T> parent)
{
BSTNode<T> child = parent.getLeftChild();
if (child != null)
{
while (child.getRightChild() != null) child = child.getRightChild();
return child;
}
child = parent.getRightChild();
if (child != null)
{
while (child.getLeftChild() != null) child = child.getLeftChild();
return child;
}
return child;
}
public T get(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return null;
return node.getData();
}
public boolean contains(T data)
{
BSTNode<T> node = find(data);
if(node == null || !node.getData().equals(data)) return false;
return true;
}
private BSTNode<T> find(T data)
{
if(root() == null) return null;
return findRecursively(root(), data);
}
private BSTNode<T> findRecursively(BSTNode<T> parent, T data)
{
int comparison = data.compareTo(parent.getData());
if(comparison == 0) return parent;
else if(comparison < 0 && parent.getLeftChild() != null) return findRecursively(parent.getLeftChild(), data);
else if(comparison > 0 && parent.getRightChild() != null) return findRecursively(parent.getRightChild(), data);
return parent;
}
public boolean isEmpty()
{
return size() == 0;
}
public int size()
{
return size;
}
private BSTNode<T> parent(BSTNode<T> child)
{
return child.getParent();
}
private boolean isInternal(BSTNode<T> node)
{
return node.children().hasNext();
}
private boolean isLeaf(BSTNode<T> node)
{
return !isInternal(node);
}
private int depth(BSTNode<T> node)
{
if(isLeaf(node)) return 0;
return depth(node.getParent()) + 1;
}
private int height(BSTNode<T> node)
{
if(isLeaf(node)) return 0;
int maxHeight = 0;
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
int height = height(children.next());
if(height > maxHeight) maxHeight = height;
}
return maxHeight + 1;
}
public int height()
{
if(root == null) return -1;
return height(root);
}
public List<T> preOrder()
{
List<T> list = new LinkedList<>();
preOrder(root, list);
return list;
}
private void preOrder(BSTNode<T> node, List<T> list)
{
if(node == null) return;
list.add(node.getData());
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
preOrder(children.next(), list);
}
}
public List<T> postOrder()
{
List<T> list = new LinkedList <>();
postOrder(root(), list);
return list;
}
private void postOrder(BSTNode<T> node, List<T> list)
{
if(node == null) return;
Iterator<BSTNode> children = node.children();
while (children.hasNext())
{
postOrder(children.next(), list);
}
list.add(node.getData());
}
public List<T> levelOrder()
{
List<T> nodeList = new LinkedList <>();
if(root() == null) return nodeList;
Queue<BSTNode> nodeQueue = new ConcurrentLinkedQueue <>();
try
{
nodeList.add(root().getData());
nodeQueue.add(root());
while (!nodeQueue.isEmpty())
{
BSTNode<T> node = nodeQueue.poll();
Iterator<BSTNode> nodeItr = node.children();
while (nodeItr.hasNext())
{
BSTNode<T> treeNode = nodeItr.next();
nodeQueue.add(treeNode);
nodeList.add(treeNode.getData());
}
}
}
catch (Exception ex)
{
System.out.println(ex.getMessage());
}
return nodeList;
}
public List<T> inOrder()
{
List<T> answer = new LinkedList <>();
inOrder(root(), answer);
return answer;
}
private void inOrder(BSTNode<T> node, List<T> list)
{
if (node == null) return;
inOrder(node.getLeftChild(), list);
list.add(node.getData());
inOrder(node.getRightChild(), list);
}
@Override
public String toString()
{
return inOrder().toString();
}
}
java object-oriented tree generics search
java object-oriented tree generics search
asked 9 mins ago
Hamidur Rahman
486
asked 9 mins ago
Hamidur Rahman
486
asked 9 mins ago
Hamidur Rahman
486
asked 9 mins ago
Hamidur Rahman
486
asked 9 mins ago
Hamidur Rahman
486
486
add a comment |
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209751%2fgeneric-binary-search-tree-implementation-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209751%2fgeneric-binary-search-tree-implementation-in-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
