java - 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();
    }
}