用Java构建二叉树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20731833/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Constructing a Binary tree in Java
提问by VIN
I am constructing a binary tree. Let me know if this is a right way to do it. If not please tell me how to?? I could not find a proper link where constructing a general binary tree has been coded. Everywhere BST is coded.
我正在构建一个二叉树。让我知道这是否是正确的方法。如果没有请告诉我怎么做？？我找不到正确的链接，其中已对构建通用二叉树进行了编码。到处都是 BST 编码。
3
/ \
1 4
/ \
2 5
This is the binary tree which i want to make.I should be able to do all the tree traversals.Simple stuff.
这是我想要制作的二叉树。我应该能够完成所有的树遍历。简单的东西。
public class Binarytreenode
{
public Binarytreenode left;
public Binarytreenode right;
public int data;
public Binarytreenode(int data)
{
this.data=data;
}
public void printNode()
{
System.out.println(data);
}
public static void main(String ar[])
{
Binarytreenode root = new Binarytreenode(3);
Binarytreenode n1 = new Binarytreenode(1);
Binarytreenode n2 = new Binarytreenode(4);
Binarytreenode n3 = new Binarytreenode(2);
Binarytreenode n4 = new Binarytreenode(5);
root.left = n1;
root.right = n2;
root.right.left = n3;
root.right.right = n4;
}
}
采纳答案by user11057
I think this is what you are looking for:
我认为这就是你要找的：
public class Binarytree
{
private static Node root;
public Binarytree(int data)
{
root = new Node(data);
}
public void add(Node parent, Node child, String orientation)
{
if (orientation.equals("left"))
{
parent.setLeft(child);
}
else
{
parent.setRight(child);
}
}
public static void main(String args[])
{
Node n1 = new Node(1);
Node n2 = new Node(4);
Node n3 = new Node(2);
Node n4 = new Node(5);
Binarytree tree = new Binarytree(3); // 3
tree.add(root, n1, "left"); // 1/ \
tree.add(root, n2, "right"); // 4
tree.add(n2, n3, "left"); // 2/ \
tree.add(n2, n4, "right"); // 5
}
}
class Node {
private int key;
private Node left;
private Node right;
Node (int key) {
this.key = key;
right = null;
left = null;
}
public void setKey(int key) {
this.key = key;
}
public int getKey() {
return key;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getLeft() {
return left;
}
public void setRight(Node right ) {
this.right = right;
}
public Node getRight() {
return right;
}
}
回答by Tim B
What you are doing looks fine as a starting point (although you may want to add a reference to the parent node if you plan to be able to move nodes around in the tree or do reverse traversals).
作为起点，您正在做的事情看起来不错（尽管如果您计划能够在树中移动节点或进行反向遍历，您可能希望添加对父节点的引用）。
Depending on what you are using the binary tree for though you could just use a TreeMap.
根据您使用二叉树的目的，虽然您可以只使用 TreeMap。
The problem is though that we don't know what you are using your Binary Tree for, and a lot of the design and implementation complexities and decisions stem from that.
问题是我们不知道您使用二叉树的目的是什么，许多设计和实现的复杂性和决策源于此。
回答by Hoodlum
In my opinion since we are not sure what implementation the BinaryTree is when it comes to some methods like add and traverse, our best bet is to make it an abstract class. Im pretty sure this code is sufficient for a general Binarytree implementation.
在我看来，由于在涉及 add 和 traverse 等一些方法时，我们不确定 BinaryTree 是什么实现，我们最好的办法是使它成为一个抽象类。我很确定这段代码对于一般的二叉树实现来说已经足够了。
What you want is an instance of a successor of a Binary Tree but I doubt its an instance of it.
你想要的是一个二叉树的继承者的实例，但我怀疑它是它的一个实例。
public abstract class Binarytree
{
private Node root;
public Binarytreenode(int data)
{
root = new Node(data);
}
public abstract void add(int key);
public abstract void traverse();
}
class Node {
private int key;
private Node left;
private Node right;
Node (int key) {
this.key = key;
right = null;
left = null;
}
public void setKey(int key) {
this.key = key;
}
public int getKey() {
return key;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getLeft() {
return left;
}
public void setRight(Node right ) {
this.right = right;
}
public Node getRight() {
return right;
}
}
回答by Philipp
The idea behind a binary tree is that it is sorted. Any values larger than the current value are in the right node and every value smaller is in the left node. That means you shouldn't do the tree-building in your main program. Rather, every node should have an "insert" method which determines whether the new node should go to the left or the right of the current node. When you have a new node, you create that node, and then you call root.insert(newNode).
二叉树背后的想法是它是排序的。任何大于当前值的值都在右节点中，每个较小的值都在左节点中。这意味着您不应该在主程序中进行树构建。相反，每个节点都应该有一个“插入”方法，该方法确定新节点应该位于当前节点的左侧还是右侧。当您有一个新节点时，您创建该节点，然后调用root.insert(newNode).
The insert-method would then work like this (because this is obviously a student assignment and you are supposed to learn from it, you only get pseudo-code from me, no complete solution):
然后插入方法会像这样工作（因为这显然是学生作业，你应该从中学习，你只能从我这里得到伪代码，没有完整的解决方案）：
When value is smaller than own value:
When there already is a left-node:
call left-node.insert(new-node)
When there isn't a left-node yet:
the left-node is now the new-node
When value is larger than own value:
When there already is a right-node:
call right-node.insert(new-node)
When there isn't a right-node yet:
the right-node is now the new-node
When value is equal to own value:
Duplicate value. Either ignore the value or throw an exception.
Finding if an object already is in the tree works the same way:
查找对象是否已经在树中的工作方式相同：
When requested value is equal to the value of this node
return this node
When the requested value is smaller
When a left node exists
call left.find(value)
When no left node exists
value doesn't exist in this tree
When the requested value is larger
When a right node exists
call right.find(value)
When no right node exists
value doesn't exist in this tree
In the case you don't actually want to learn how binary trees work and just use them, just use TreeSetwhich is an already working binary-tree implementation.
如果您实际上不想学习二叉树的工作原理并只是使用它们，只需使用TreeSet，它是一个已经可以工作的二叉树实现。
