How can i make a program that will accept a series of inputs named as inserts and arrange them in the form of binary search trees. Do you have any source codes what I can use as reference?
Your help is very much appreciated! Thanks for the reply
diyes05
0
Newbie Poster
Recommended Answers
Jump to PostWe don't distribute source code. write some code based on your requirements and we'd be more than happy to help you if you get stuck.
I will provide a link that has a java implementation as well as a resource to understanding that algorithm in general so you can …
Jump to PostFor testing I suggest that you use the Scanner class with a String in the program to provide input to be inserted into the BST. This will make the debugging much easier.
String InputData = "First line\nSecond line\nthird line\n"; // Define the lines to read ... Scanner …
All 6 Replies
brandonrunyon
21
Junior Poster
We don't distribute source code. write some code based on your requirements and we'd be more than happy to help you if you get stuck.
I will provide a link that has a java implementation as well as a resource to understanding that algorithm in general so you can start thinking about your assignment critically.
http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html
diyes05
0
Newbie Poster
Thank your for that reference brandonrunyon.
btw, here is the source code
public class binaryTree {
public static void main(String[] args)
{
new BinaryTreeExample().run();
}
static class Node
{
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
}
public void run() {
Node rootnode = new Node(25);
System.out.println("Building tree with rootvalue" + rootnode.value);
System.out.println("=================================");
insert(rootnode, 11);
insert(rootnode, 15);
insert(rootnode, 16);
insert(rootnode, 23);
insert(rootnode, 56);
insert(rootnode, 79);
System.out.println("Traversing tree in order");
System.out.println("=================================");
printInOrder(rootnode);
}
public void insert(Node node, int value) {
if (value < node.value) {
if (node.left != null) {
insert(node.left, value);
} else {
System.out.println(" Inserted " + value + " to left of node " + node.value);
node.left = new Node(value);
}
} else if (value > node.value) {
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println(" Inserted " + value + "to right of node " + node.value);
node.right = new Node(value);
}
}
}
public void printInOrder(Node node) {
if (node != null) {
printInOrder(node.left);
System.out.println(" Traversed " + node.value);
printInOrder(node.right);
}
}
}
My problem is, the inserts are fixed. I want the user to insert values using scanner or joptionpane and the program will arrange it in BST and gives a graphical or instructional output. And I am also stuck in implementing a method the can delete a specific node, and rearrange the tree to make it balance again.
NormR1
563
Posting Sage
Team Colleague
For testing I suggest that you use the Scanner class with a String in the program to provide input to be inserted into the BST. This will make the debugging much easier.
String InputData = "First line\nSecond line\nthird line\n"; // Define the lines to read
...
Scanner scnr = new Scanner(InputData);
....
while(scnr.hasNext()) {
String str = scnr.nextLine();
brandonrunyon
21
Junior Poster
please use code tags as well... it makes it easier to read your syntax. highlight your code and click the (CODE) image.
diyes05
0
Newbie Poster
For the node class
import java.lang.Comparable;
import java.lang.StringBuffer;
public class BSTNode {
private Comparable value;
private BSTNode left;
private BSTNode right;
private BSTNode parent;
private int hash = 0;
private StringBuffer preorderSB;
private StringBuffer inorderSB;
private StringBuffer postorderSB;
public BSTNode(Comparable elem){
this(elem, null, null);
}
public BSTNode(Comparable elem, BSTNode lf, BSTNode rt){
value = elem;
left = lf;
right = rt;
}
public Comparable getValue(){
return value;
}
public BSTNode getLeftChild(){
return left;
}
public BSTNode getRightChild(){
return right;
}
public BSTNode getParent(){
return parent;
}
public void setLeftChild(BSTNode node){
left = node;
}
public void setRightChild(BSTNode node){
right = node;
}
public void setParent(BSTNode node){
parent = node;
}
public boolean hasLeftChild(){
return left != null;
}
public boolean hasRightChild(){
return right != null;
}
public boolean hasParent(){
return parent != null;
}
public boolean hasChildren(){
return hasRightChild() || hasLeftChild();
}
public boolean hasBothChildren(){
return hasRightChild() && hasLeftChild();
}
public boolean isLeaf(){
return (left == null) && (right == null);
}
public boolean isTree(){
return (left != null) && (right != null);
}
public void insertNode(Comparable val){
insertNode(new BSTNode(val));
}
public void insertNode(BSTNode node){
int delta = node.getValue().compareTo(value);
if(delta < 0){
if(left == null){
left = node;
left.setParent(this);
}
else{
left.insertNode(node);
}
}
else if(delta > 0){
if(right == null){
right = node;
right.setParent(this);
}
else{
right.insertNode(node);
}
}
}
public BSTNode findNode(Comparable val){
int delta = val.compareTo(value);
if(delta < 0){
return (left!= null)? left.findNode(val): null;
}
else if (delta > 0){
return (right != null)? right.findNode(val): null;
}
return this;
}
public BSTNode findNode(BSTNode node){
return findNode(node.getValue());
}
public String preorder(){
if(preorderSB == null){
preorderSB = new StringBuffer();
}
else{
preorderSB.delete(0, preorderSB.length());
}
preorderSB.append(toString());
preorderSB.append(hasLeftChild()? left.preorder():"");
preorderSB.append(hasRightChild()? right.preorder():"");
return preorderSB.toString();
}
public String inorder(){
if(inorderSB == null){
inorderSB = new StringBuffer();
}
else{
inorderSB.delete(0, inorderSB.length());
}
inorderSB.append( hasLeftChild()? left.inorder():"" );
inorderSB.append(toString());
inorderSB.append( hasRightChild()? right.inorder():"");
return inorderSB.toString();
}
public String postorder(){
if(postorderSB == null){
postorderSB = new StringBuffer();
}
else{
postorderSB.delete(0, postorderSB.length());
}
postorderSB.append(hasLeftChild()? left.postorder():"");
postorderSB.append(hasRightChild()? right.postorder():"");
postorderSB.append(toString());
return postorderSB.toString();
}
public boolean equals(Object o){
if(o instanceof BSTNode){
BSTNode b = (BSTNode) o;
return b.value.equals(value);
}
return false;
}
public int hashCode(){
// hashCode has not been initialized, so initialize it
if(hash == 0){
hash = value.hashCode();
}
return hash;
}
public String toString(){
return "{" + value.toString() + "}";
}
public static void main(String[] args){
BSTNode node = new BSTNode("B");
BSTNode node1 = new BSTNode("A");
node.insertNode(node1);
node.insertNode("D");
System.out.println(node.hasLeftChild());
System.out.println(node1.getParent());
}
}import java.lang.StringBuffer;
import java.lang.Comparable;
public class BSTree {
private BSTNode root;
public BSTree(){
this(null);
}
public BSTree(BSTNode node){
root = node;
}
public BSTNode getRoot(){
return root;
}
public BSTNode find(Comparable val){
if(root != null){
return root.findNode(val);
}
return null;
}
public BSTNode removeNode(Comparable val){
return removeNode(new BSTNode(val));
}
public BSTNode removeNode(BSTNode node){
return removeNodeHelper(root, node);
}
private BSTNode removeNodeHelper(BSTNode start, BSTNode node){
if(start == null){
return null;
}
else{
int delta = node.getValue().compareTo(start.getValue());
if(delta < 0){
return removeNodeHelper(start.getLeftChild(), node);
}
else if(delta > 0){
return removeNodeHelper(start.getRightChild(), node);
}
else{
if(start.isLeaf()){
return this.removeLeaf(start);
}
else if(start.isTree()){
return this.removeTree(start);
}
else{
return this.removeOneSubTree(start);
}
}
}
}
private BSTNode removeLeaf(BSTNode leaf){
if(leaf.hasParent()){
BSTNode leafParent = leaf.getParent();
leaf.setParent(null);
if(leafParent.hasLeftChild() && leafParent.getLeftChild().equals(leaf)){
leafParent.setLeftChild(null);
}
else{
leafParent.setRightChild(null);
}
}
else{
root = null;
}
return leaf;
}
private BSTNode removeTree(BSTNode tree){
BSTNode replacementNode;
if(heightHelper(tree.getLeftChild()) > heightHelper(tree.getRightChild())){
replacementNode = getMaxHelper(tree.getLeftChild());
}
else{
replacementNode = getMinHelper(tree.getRightChild());
}
if(tree.hasParent()){
if(tree.hasRightChild() && !tree.getRightChild().equals(replacementNode)){
replacementNode.setRightChild(tree.getRightChild());
}
if(tree.hasLeftChild() && !tree.getLeftChild().equals(replacementNode)){
replacementNode.setLeftChild(tree.getLeftChild());
}
BSTNode treeParent = tree.getParent();
if(treeParent.hasLeftChild() && treeParent.getLeftChild().equals(tree)){
treeParent.setLeftChild(replacementNode);
}
else{
treeParent.setRightChild(replacementNode);
}
BSTNode replaceNodeParent = replacementNode.getParent();
if(replaceNodeParent.hasLeftChild()
&& replaceNodeParent.getLeftChild().equals(replacementNode)){
replaceNodeParent.setLeftChild(null);
}
else{
replaceNodeParent.setRightChild(null);
}
replacementNode.setParent(treeParent);
}
else{
// remove root node
BSTNode replaceNodeParent = replacementNode.getParent();
if(replaceNodeParent.hasLeftChild()
&& replaceNodeParent.getLeftChild().equals(replacementNode)){
replaceNodeParent.setLeftChild(null);
}
else{
replaceNodeParent.setRightChild(null);
}
replacementNode.setParent(null);
replacementNode.setRightChild(tree.getRightChild());
replacementNode.setLeftChild(tree.getLeftChild());
tree.getRightChild().setParent(replacementNode);
tree.getLeftChild().setParent(replacementNode);
root = replacementNode;
}
tree.setParent(null);
tree.setRightChild(null);
tree.setLeftChild(null);
return tree;
}
private BSTNode removeOneSubTree(BSTNode start){
if(start.hasParent()){
BSTNode startParent = start.getParent();
if(startParent.hasLeftChild() && startParent.getLeftChild().equals(start)){
BSTNode n = start.hasLeftChild()? start.getLeftChild(): start.getRightChild();
n.setParent(startParent);
startParent.setLeftChild(n);
}
else{
BSTNode n = start.hasLeftChild()? start.getLeftChild(): start.getRightChild();
n.setParent(startParent);
startParent.setRightChild(n);
}
}
else{
if(start.hasLeftChild()){
root = start.getLeftChild();
start.getLeftChild().setParent(null);
}
else{
root = start.getRightChild();
start.getRightChild().setParent(null);
}
}
start.setLeftChild(null);
start.setRightChild(null);
start.setParent(null);
return start;
}
public void insertNode(BSTNode node){
if(root != null){
root.insertNode(node);
}
}
public BSTNode getMaximum(){
if(root != null){
return getMaxHelper(root);
}
return null;
}
private BSTNode getMaxHelper(BSTNode node){
if(node.hasRightChild()){
return getMaxHelper(node.getRightChild());
}
return node;
}
public BSTNode getMinimum(){
if(root != null){
return getMinHelper(root);
}
return null;
}
private BSTNode getMinHelper(BSTNode node){
if(node.hasLeftChild()){
return getMinHelper(node.getLeftChild());
}
return node;
}
public BSTNode removeMinimum(){
return removeMinHelper(root);
}
private BSTNode removeMinHelper(BSTNode start){
if(start == null){
return null;
}
else if(start.hasLeftChild()){
return removeMinHelper(start.getLeftChild());
}
else{
if(start.hasParent()){
start.getParent().setLeftChild(start.getRightChild());
}
else{
root = start.getRightChild();
}
if(start.hasRightChild()){
start.getRightChild().setParent(start.getParent());
}
return start;
}
}
public BSTNode removeMaximum(){
return removeMaxHelper(root);
}
private BSTNode removeMaxHelper(BSTNode start){
if(start == null){
return null;
}
else if(start.hasRightChild()){
return removeMaxHelper(start.getRightChild());
}
else{
if(start.hasParent()){
start.getParent().setRightChild(start.getLeftChild());
}
else{
root = start.getLeftChild();
}
if(start.hasLeftChild()){
start.getLeftChild().setParent(start.getParent());
}
return start;
}
}
public boolean isEmpty(){
return root == null;
}
public void makeEmpty(){
root = null;
}
public int getSize(){
return getSizeHelper(root);
}
private int getSizeHelper(BSTNode start){
if(start == null)
return 0;
else{
return getSizeHelper(start.getLeftChild())
+ getSizeHelper(start.getRightChild()) + 1;
}
}
public int getLeavesCount(){
return leavesCountHelper(root);
}
private int leavesCountHelper(BSTNode start){
if(start == null){
return 0;
}
if(start.isLeaf()){
return 1;
}
else{
return leavesCountHelper(start.getLeftChild())
+ leavesCountHelper(start.getRightChild());
}
}
/*
public int getHeigth(){
return heightHelper(root);
}
private int heightHelper(BSTNode start){
if (start == null){
return 0;
}
else{
return Math.max(heightHelper(start.getLeftChild()), heightHelper(start.getRightChild())) + 1;
}
}
public String preorder(){
if(root != null){
return root.preorder();
}
return null;
}
public String inorder(){
if(root != null){
return root.inorder();
}
return null;
}
public String postorder(){
if(root != null){
return root.postorder();
}
return null;
}
public int hashCode(){
return root.hashCode();
}
public String toString(){
if(root == null)
return "{EmptyTree}\n";
else
return "\n" + showSub(root, 1) + "\n";
}
private String showSub(BSTNode node, int level){
StringBuffer sb = new StringBuffer();
if(node != null){
sb.append(showSub(node.getRightChild(), level+1));
for(int j = 0; j < level; ++ j){
sb.append("\t\t");
}
sb.append(" " + node.toString());
if(node.isTree()){
sb.append("<");
}
else if(node.hasRightChild()){
sb.append("/");
}
else if (node.hasLeftChild()){
sb.append("\\");
}
sb.append("\n" + showSub(node.getLeftChild(), level+1));
}
return sb.toString();
}
public static void main(String[] args){
BSTree tree = new BSTree(new BSTNode(new Integer(37)));
tree.insertNode(new BSTNode(new Integer(24)));
tree.insertNode(new BSTNode(new Integer(42)));
tree.insertNode(new BSTNode(new Integer(7)));
tree.insertNode(new BSTNode(new Integer(2)));
tree.insertNode(new BSTNode(new Integer(40)));
tree.insertNode(new BSTNode(new Integer(32)));
tree.insertNode(new BSTNode(new Integer(120)));
tree.insertNode(new BSTNode(new Integer(100)));
System.out.println(tree);
System.out.println("preorder: " + tree.preorder());
System.out.println("inorder: " + tree.inorder());
System.out.println("postorder: " + tree.postorder());
System.out.println(tree);
System.out.println("remove: " + tree.removeNode(new Integer(37)));
System.out.println(tree);
System.out.println("remove: " + tree.removeNode(new Integer(7)));
System.out.println(tree);
tree.insertNode(new BSTNode(new Integer(900)));
System.out.println(tree);
for(int i = 0; i < 10; ++i){
System.out.println(tree);
System.out.println(tree.removeMaximum());
}
for(int i = 0; i < 10; ++i){
System.out.println(tree);
System.out.println("remove min: " + tree.removeMinimum());
}
tree.removeNode(new Integer(24));
System.out.println(tree);
tree.removeNode(new Integer(37));
System.out.println(tree);
tree.removeNode(new Integer(7));
System.out.println(tree);
}
}It is a code I found in the net. My Problem is, I want the insertion given by the user, and to have an option to delete a particular node. How can I modify this code?
Thank for your reply!!
brandonrunyon
21
Junior Poster
As NormR1 pointed out, the Scanner class is a convenient class for handling user input. There is also BufferedInput. Please consult the javadocs for the most appropriate classes to meet your needs.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.