java 二叉树数据结构和方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12667058/
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
BinaryTree Data structure with methods
提问by Bob
I implemented a binary tree data structure. The data structure allows a binary tree to be built from a list (elements are inserted from left to right). How can I optimize insertElement? At the moment, it is recursive, so if tree is deep, it will run out of memory. How can I make it tail-recursive or even end-recursive?
我实现了一个二叉树数据结构。数据结构允许从列表构建二叉树（元素从左到右插入）。如何优化insertElement？目前，它是递归的，所以如果树很深，它将耗尽内存。我怎样才能使它成为尾递归甚至是尾递归？
public class Node {
private int value;
private boolean isLeaf;
public Node (int value, boolean isLeaf){
this.value = value;
this.isLeaf = isLeaf;
}
public int getValue(){
return value;
}
public void setLeaf(boolean value){
this.isLeaf = value;
}
public boolean isLeaf(){
return isLeaf;
}
}
public class BinaryTree {
Node root;
BinaryTree left_child;
BinaryTree right_child;
public BinaryTree(){
}
public BinaryTree(Node root, BinaryTree left_child, BinaryTree right_child){
this.root = root;
this.left_child = left_child;
this.right_child = right_child;
}
public BinaryTree insertElement(int element){
if (root==null)
return new BinaryTree(new Node(element, true), null, null);
else {
if (root.isLeaf()){
root.setLeaf(false);
if (element < root.getValue())
return new BinaryTree(root, new BinaryTree(new Node(element, true), null, null), null);
else
return new BinaryTree(root, null, new BinaryTree(new Node(element, true), null, null));
} else {
if (element < root.getValue())
if (left_child!=null)
return new BinaryTree(root, left_child.insertElement(element), right_child);
else
return new BinaryTree(root, new BinaryTree(new Node(element, true), null, null), right_child);
else
if (right_child!=null)
return new BinaryTree(root, left_child, right_child.insertElement(element));
else
return new BinaryTree(root, left_child, new BinaryTree(new Node(element, true), null, null));
}
}
}
public BinaryTree getLeftChild(){
return left_child;
}
public BinaryTree getRightChild(){
return right_child;
}
public void setLeftChild(BinaryTree tree){
this.left_child = tree;
}
public void setRightChild(BinaryTree tree){
this.right_child = tree;
}
public BinaryTree buildBinaryTree(int[] elements){
if (elements.length==0)
return null;
else{
BinaryTree tree = new BinaryTree(new Node(elements[0], true), left_child, right_child);
for (int i=1;i<elements.length;i++){
tree = tree.insertElement(elements[i]);
}
return tree;
}
}
public void traversePreOrder(){
if (root!=null)
System.out.print(root.getValue() + " ");
if (left_child!=null)
left_child.traversePreOrder();
if (right_child!=null)
right_child.traversePreOrder();
}
public void traverseInOrder(){
if (left_child!=null)
left_child.traverseInOrder();
if (root!=null)
System.out.print(root.getValue() + " ");
if (right_child!=null)
right_child.traverseInOrder();
}
public void traversePostOrder(){
if (left_child!=null)
left_child.traversePostOrder();
if (right_child!=null)
right_child.traversePostOrder();
if (root!=null)
System.out.print(root.getValue() + " ");
}
public static void main(String[] args){
int[] elements = new int[]{5,7,2,1,4,6,8};
BinaryTree tree = new BinaryTree();
tree = tree.buildBinaryTree(elements);
tree.traversePreOrder();
System.out.println();
tree.traverseInOrder();
System.out.println();
tree.traversePostOrder();
System.out.println();
}
}
回答by rbhawsar
if you think the tree would be too deep and run out of memory, better implement the logic with loop rather than using the recursion. temproot=root; while(inserted != true){
如果您认为树太深并且内存不足，最好使用循环而不是使用递归来实现逻辑。临时根=根；而（插入！=真）{
if(root==null)
//add at the root.
else if(item<temproot->item )//it should go to left.
{
if(temproot->left==null)
//add your node here and inserted=true or put break; else just move pointer to left.
temproo=temproot->left; //take left address.
}
else if(it should go to right)
//check the logic of above if clause.
}//end of while loop
and if you find that it should go to left and there is no child in left just add your node there. no need to put all the visited nodes in the system stack because anyway you are not using those nodes.
如果您发现它应该向左移动并且左边没有孩子，只需在那里添加您的节点。无需将所有访问过的节点放在系统堆栈中，因为无论如何您都没有使用这些节点。
回答by swemon
In your coding, you create
在您的编码中，您创建
Node class which contains only value and boolean variable isLeaf.
仅包含值和布尔变量 isLeaf 的节点类。
Whenever an element is created, you create a new binary tree based on the inserted element and append to the main tree.
每当创建一个元素时，您都会根据插入的元素创建一个新的二叉树并附加到主树中。
The other way you can implement binary tree is
实现二叉树的另一种方法是
Node class contains its own value, left node and right node.
Node 类包含它自己的值，左节点和右节点。
Inserting element still recursive but whenever you insert an element you do not need to create a new binary tree, just a new nodelike here
插入元素仍然是递归的，但是每当你插入一个元素时，你不需要创建一个新的二叉树，只需要一个像这里的新节点
