1

我实现了一个二叉树数据结构。数据结构允许从列表构建二叉树（元素从左到右插入）。如何优化 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();
    }

}
4

2 回答 2

1

如果您认为树太深并且内存不足，最好使用循环而不是使用递归来实现逻辑。临时根=根；而（插入！=真）{

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

如果您发现它应该向左移动并且左侧没有子节点，只需在此处添加您的节点。无需将所有访问过的节点都放在系统堆栈中，因为无论如何您都没有使用这些节点。

于 2012-10-01T03:44:40.670 回答
0

In your coding, you create

Node class which contains only value and boolean variable 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.

Inserting element still recursive but whenever you insert an element you do not need to create a new binary tree, just a new node like here

于 2012-10-01T03:43:06.090 回答