0

バイナリ ツリーの inOrder トラバーサルを出力する際に​​問題が発生しています。ツリーに多くのアイテムを挿入した後でも、3 つのアイテムしか印刷されません。

public class BinaryTree {

    private TreeNode root;
    private int size;

    public BinaryTree(){
        this.size = 0;
    }

    public boolean insert(TreeNode node){

        if( root == null)
            root = node;

        else{
            TreeNode parent = null;
            TreeNode current = root;
            while( current != null){
                if( node.getData().getValue().compareTo(current.getData().getValue()) <0){
                    parent = current;
                    current = current.getLeft();
                }
                else if( node.getData().getValue().compareTo(current.getData().getValue()) >0){
                    parent = current;
                    current = current.getRight();
                }
                else
                    return false;

                if(node.getData().getValue().compareTo(parent.getData().getValue()) < 0)
                    parent.setLeft(node);
                else
                    parent.setRight(node);
                }
            }
            size++;
            return true;
        }


    /**
     * 
     */
    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(TreeNode root){
        if( root.getLeft() !=null)
            this.inOrder(root.getLeft());
        System.out.println(root.getData().getValue());

        if( root.getRight() != null)
            this.inOrder(root.getRight());
    }



}
4

3 に答える 3

1

挿入方法に問題があります。新しい要素をアタッチする適切な親ノードを見つけますが、途中でツリー全体を台無しにします。挿入コードを while ループの外に移動する必要があります。

public boolean insert(TreeNode node){

    if( root == null)
        root = node;

    else{
        TreeNode parent = null;
        TreeNode current = root;
        while( current != null){
            if( node.getData().getValue().compareTo(current.getData().getValue()) <0){
                parent = current;
                current = current.getLeft();
            }
            else if( node.getData().getValue().compareTo(current.getData().getValue()) >0){
                parent = current;
                current = current.getRight();
            }
            else
                return false;
        }

        if(node.getData().getValue().compareTo(parent.getData().getValue()) < 0)
            parent.setLeft(node);
        else
            parent.setRight(node);
        }

        size++;
        return true;
    }
}
于 2010-04-24T21:36:44.223 に答える
1

新しいノードの適切な場所を見つけるために、挿入時にツリーを適切に走査していないようです。現在、挿入コードはループ内にあるため、常にルートの 1 つの子に挿入しています。ループの後whileにある必要があります。

public boolean insert(TreeNode node){

    if( root == null)
        root = node;

    else{
        TreeNode parent = null;
        TreeNode current = root;
        while( current != null){
            if( node.getData().getValue().compareTo(current.getData().getValue()) <0){
                parent = current;
                current = current.getLeft();
            }
            else if( node.getData().getValue().compareTo(current.getData().getValue()) >0){
                parent = current;
                current = current.getRight();
            }
            else
                return false;
        }
        if(node.getData().getValue().compareTo(parent.getData().getValue()) < 0)
            parent.setLeft(node);
        else
            parent.setRight(node);
        }

        size++;
        return true;
    }
于 2010-04-24T21:38:16.463 に答える