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

ツリーが深すぎてメモリ不足になると思われる場合は、再帰を使用するのではなく、ループを使用してロジックを実装することをお勧めします。temproot=ルート; while(挿入!=真){

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

コーディングでは、作成します

値とブール変数 isLeaf のみを含むノード クラス。

要素が作成されるたびに、挿入された要素に基づいて新しいバイナリ ツリーを作成し、メイン ツリーに追加します。

二分木を実装する別の方法は、

Node クラスには、独自の値である左ノードと右ノードが含まれます。

要素の挿入は依然として再帰的ですが、要素を挿入するたびに、新しいバイナリ ツリーを作成する必要はありません。ここのような新しいノードだけです。

于 2012-10-01T03:43:06.090 に答える