Java 二叉树按顺序插入

Question

如何将项目插入到 java 中的二叉树中，以便它们按顺序排列？我想使用随机值并将它们从最小到最大排序，然后按以下顺序将它们插入到二叉树中：

          1
     2         3
   4   5     6   7
 8  9

Answer 1

当你说'in order'时，你需要澄清一下，你的意思是排序顺序还是插入顺序等等

inserting into binary trees or the difference between to types of binary trees, or how to print a binary tree diagram 上有很多可用资源，我怀疑这是重复的。

您的示例有何不同？将“1”作为根节点意味着您不能有再平衡树，因为“2”和“3”都大于根节点的值。您的插入规则似乎不一致，因为如果“1”是第一个插入的节点，那么所有其他值都将级联到树的右分支，除非您对根使用不同的规则，然后在其他级别使用不同的规则，这将很难编码。

Answer 2

是这样的吗？:

public class BinaryTree {
    private List<Integer> list = new ArrayList<Integer>();


    public class BinaryTreeNode {
        private int p;

        public BinaryTreeNode(int p) {
            this.p = p;
        }

        private BinaryTreeNode getChild(int childP){
            BinaryTreeNode result= null;
            if (childP < list.size()){
                result = new BinaryTreeNode(childP);
            }
            return result;
        }

        public BinaryTreeNode getLeft(){
            return getChild(p*2+1);
        }

        public BinaryTreeNode getRight(){
            return getChild(p*2+2);
        }

        public int getValue(){
            return list.get(p);
        }
    }

    public void add(int item){
        list.add(item);
    }

    public BinaryTreeNode getRoot(){
        BinaryTreeNode result = null;
        if (!list.isEmpty()){
            result = new BinaryTreeNode(0);
        }
        return result;
    }
}

Answer 3

在 Naftalin, Walder Java Collections and Generics 中，我遇到了我最喜欢的这个实现：

public interface TreeVisitor<E, R> {
    public R visit(E leaf);

    public R visit(E value, Tree<E> left, Tree<E> right);
}

public abstract class Tree<E> {

    public abstract <R> R accept(TreeVisitor<E, R> visitor);

    public static <E> Tree<E> leaf(final E leaf) {
        return new Tree<E>() {
            @Override
            public <R> R accept(TreeVisitor<E, R> visitor) {
                return visitor.visit(leaf);
            }
        };
    }

    public static <E> Tree<E> branch(final E value, final Tree<E> left, final Tree<E> right){
        return new Tree<E>(){
            @Override
            public <R> R accept(TreeVisitor<E, R> visitor) {
                return visitor.visit(value, left, right);
            }
        };
    }
}

现在您可以添加任何您想要的操作并创建您的树，如下所示：

Tree<Integer> t = Tree.branch(1, 
            Tree.branch(2, 
                Tree.branch(4, Tree.leaf(8), Tree.leaf(9)), Tree.leaf(5)),
                Tree.branch(3, Tree.leaf(6), Tree.leaf(7));

Answer 4

我从这个中找到了我需要的答案。

Create a Complete Binary Tree using Linked Lists w/o comparing node values

有人指出我的其他一些东西，要么不是我想要的，要么超过 8 个左右的值就无法正常工作。

Java 二叉树按顺序插入

Java Binary Tree Insert in Order

java

binary-tree