Java二叉树。打印InOrder遍历

Question

我在打印二叉树的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());
    }



}

Answer 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;
    }

Answer 2

您插入的方法有问题。它会找到要附加新元素的正确父节点，但在此过程中，它会弄乱整个树。您应该将插入代码移出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;
    }
}

Answer 3

嘿，伙计们，这里有一个简单的问题..试试看..对我来说效果很好。

public void levelOrderTraversal(Node root){
    Queue<Node> queue = new ArrayDeque<Node>();
    if(root == null) {
        return;
    }
    Node tempNode = root;
    while(tempNode != null) {
        System.out.print(tempNode.data + " ");

        if(tempNode.left != null)   queue.add(tempNode.left);
        if(tempNode.right != null)   queue.add(tempNode.right);

        tempNode = queue.poll();
    }
}