'Binary Search Tree using char type
I understand Binary Search Tree on integers ,because i know the left child must be less then the node,and right child must be greater then the node ,when it comes to "char" or "string" type ,its totally different case,we can't say ( 'a' < 'b' ) or any other logical operations . how can i compare the char values?!
This is my Binary Tree http://share.pho.to/89JtW i couldn't work because each time i insert to my code.all nodes are inserted to the right of sub-node .
the nodes represent a pages ,i want to check each page to detect if user is human or spambot .
each page can be linked to another 2 pages. A human will traverse on the webpage in a way that it will be able to go to the previous page or one of the next two pages that they are linked to. Otherwise, they will be categorized as spambot.
And this code i trying to implement
package stringBtree;
public class StringBinaryTreeSample {
public static void main(String[] args)
{
new StringBinaryTreeSample().run();
}
static class Node
{
Node left;
Node right;
char value;
public Node(char value) {
this.value = value;
}
}
public void run() {
Node rootnode = new Node('A');
System.out.println("Building tree with rootvalue " + rootnode.value);
System.out.println("=================================");
insert(rootnode, 'b' );
insert(rootnode, 'd' );
insert(rootnode, 'c');
insert(rootnode, 'd');
insert(rootnode, 'e' );
insert(rootnode, 'f');
insert(rootnode, 'g');
insert(rootnode, 'h');
insert(rootnode, 'i');
insert(rootnode, 'j');
insert(rootnode, 'k');
insert(rootnode, 'l');
insert(rootnode, 'm');
insert(rootnode, 'n');
insert(rootnode, 'o');
insert(rootnode, 'p');
insert(rootnode, 'q');
System.out.println("\n\nTraversing tree in order");
System.out.println("=================================");
printInOrder(rootnode);
}
public void insert(Node node, char 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);
}
}
}
Solution 1:[1]
How to compare chars and strings
First, I should say that a char is not a string. In Java (and many other languages), a char is actually a two byte number. Take a look at this ASCII table of characters and you'll see that every character has a unique byte counterpart. Since a byte can be thought of as a number, you actually can compare chars using the usual comparison operators >, <, and ==. Strings, on the other hand, are objects, so you have to compare them using the compareTo method. By reading the documentation on Strings, you can find out that the compareTo method will return a negative or positive number depending on whether the string is alphabetically before or after the other string you're comparing it to (click on the link to read the documentation for more info).
Why nodes are always being added to the right
I'm assuming that you are saying that the nodes that you insert into the tree are always added to the right of the root node. The root node in your code is the character A, which, according to the ASCII table, is actually less than all of the other characters that you add later on since all of the other letters are lowercase. So that means all of the following nodes are going to be added to the right of A. I'm not sure if that's what you want, but it's worth pointing out.
If you are saying that the nodes are always added to the right of the whole tree (so that it looks like a long line with no branches), that's because of the letters you picked and the order you add them to the tree. If you follow your code, you add 'b' to 'A'. 'b' > 'A' so it's added to the right. Next you add 'd'. 'd' > 'b' so that node is added to the right. Then you add 'c', and 'c' < 'd', so that node should be on the left. After that, you add the nodes in alphabetical order, so each subsequent letter you add is greater than the last letter you added. To illustrate, 'd' < 'e' < 'f' < 'g' < ... < 'q'. Hence, all nodes after 'c' are added to the right. This makes sense; on the contrary, the tree in the photo you linked to doesn't make sense. That tree is a binary tree in the sense that each node has only two children, but the child nodes aren't "less" or "greater" than their parent node. I mean, how is 'B' less than 'A' and at the same time 'C' greater than 'A'? I don't see what you would use that tree for, unless the letters mean something other than their literal characters.
How to make your tree look like the one in the picture
If you really wanted to make your tree look like the one in the picture, you would have to assign numbers to the characters so that 'B' is less than 'A', 'C' is greater than 'A', etc. Then in your insert method, you would compare those characters using the number rather than the character. That could be done by making a class with a character field and a number field. You would then set the number field to be whatever you wanted to make your tree look like you need it look like. For instance, 'A' could be 50, 'B' 49, 'C' 51, etc.
Solution 2:[2]
Below is a outline implementation of B-Tree with String:
public class TreeNode {
protected String nodeValue;
protected TreeNode leftChild;
protected TreeNode rightChild;
public TreeNode(String nodeValue){
this.nodeValue=nodeValue;
}//constructor closing
public void addChild(String childNodeValue){
if(childNodeValue.compareTo(nodeValue)<0){//go left
if(leftChild==null)leftChild=new TreeNode(childNodeValue);
else {
if(childNodeValue.compareTo(leftChild.getNodeValue())<0)leftChild.addChild(childNodeValue);
else{
TreeNode tempChild=new TreeNode(childNodeValue);
tempChild.setLeftChild(this.leftChild);
this.leftChild=tempChild;
}//else closing
}//else closing
}//if closing
else if(childNodeValue.compareTo(nodeValue)>0){//go right
if(rightChild==null)rightChild=new TreeNode(childNodeValue);
else {
if(childNodeValue.compareTo(rightChild.getNodeValue())>0)rightChild.addChild(childNodeValue);
else{
TreeNode tempChild=new TreeNode(childNodeValue);
tempChild.setRightChild(this.rightChild);
this.rightChild=tempChild;
}//else closing
}//else closing
}//if closing
else throw new RuntimeException("Problem");
}//addChild closing
public String getNodeValue(){return nodeValue;}
public TreeNode getLeftChild(){return leftChild;}
public TreeNode getRightChild(){return rightChild;}
public void setLeftChild(TreeNode leftChild){this.leftChild=leftChild;}
public void setRightChild(TreeNode rightChild){this.rightChild=rightChild;}
@Override
public String toString() {
String retVal="--"+nodeValue+"--\n";
return retVal;
}//toString closing
}//class closing
public class BTree {
protected TreeNode primaryNode;
public BTree(String primaryNodeValue){
primaryNode=new TreeNode(primaryNodeValue);
}//constructor closing
public void addChild(String childNodeValue){
primaryNode.addChild(childNodeValue);
}//addChild closing
public TreeNode getPrimayNode(){return primaryNode;}
@Override
public String toString() {
return primaryNode.toString();
}//toString closing
public static void main(String[] args) {
String midValue="m";
BTree tree=new BTree(midValue);
tree.addChild("a");
tree.addChild("b");
tree.addChild("y");
tree.addChild("z");
TreeNode mNode=tree.getPrimayNode();
TreeNode leftOfMNode=mNode.getLeftChild();
TreeNode rightOfMNode=mNode.getRightChild();
System.out.print(mNode);
System.out.print(leftOfMNode);
System.out.print(rightOfMNode);
System.out.println("---------------------------------------------------------------");
TreeNode bNode=leftOfMNode;
System.out.print(bNode);
System.out.print(bNode.getLeftChild());
System.out.print(bNode.getRightChild());
System.out.println("---------------------------------------------------------------");
TreeNode yNode=rightOfMNode;
System.out.print(yNode);
System.out.print(yNode.getLeftChild());
System.out.print(yNode.getRightChild());
}//main closing
}//class closing
This should give you a head start with your actual implementation.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 | Ironluca |