我理解整数上的二叉搜索树，因为我知道左子节点必须小于节点，右子节点必须大于节点，当涉及到“char”或“string”类型时，情况完全不同，我们不能说 ( 'a' < 'b' ) or any other logical operations . how can i compare the char values?!
这是我的二叉树http://share.pho.to/89JtW我无法工作，因为每次我插入代码时。所有节点都插入到子节点的右侧。
节点代表一个页面，我想检查每个页面以检测用户是人类还是垃圾邮件机器人。
每个页面可以链接到另外 2 个页面。人类将穿越 网页的方式使其能够转到它们链接到的上一页或后两页之一。否则，它们将被归类为垃圾邮件机器人。
我试图实现这段代码
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);
}
}
}
如何比较字符和字符串
首先，我应该说
charstringcharbytebytecompareTo为什么节点总是被添加到右侧
我假设您是说插入树中的节点始终添加到根节点的右侧。代码中的根节点是字符
AA如果您说节点始终添加到整个树的右侧（因此它看起来像一条没有分支的长线），那是因为您选择的字母以及将它们添加到树中的顺序。如果您遵循代码，请将“b”添加到“A”。 'b' > 'A' 因此它被添加到右侧。接下来添加“d”。 'd' > 'b'，以便该节点添加到右侧。然后添加“c”和“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.
如何让你的树看起来像图中的那棵
如果你真的想让你的树看起来像图片中的那样，你必须为字符分配数字，使得“B”小于“A”，“C”大于“A”，等等。然后在您的
insert下面是 B-Tree 与 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
}//结课
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
}//结课
这应该可以让您在实际实施中取得领先。