java - 使用不比较节点值的链接列表创建完整的二叉树

Question

我正在尝试使用链表而不是 arraylist 创建一个完整的二叉树，而不比较节点值。 我的意思是在插入一个新值时，我不想比较该值是否小于、大于或等于根的值，以便将其添加到左侧链接或右侧链接，但仍然能够创建一个完整的二叉树。

你觉得可能吗？如果是，你有什么想法或者你能告诉我一些我可以使用/阅读的东西吗？

编辑:

Here's an example to make my question more clear:
I am adding the numbers in the order presented through the insert method: 1 2 3 4 5 6
the insert method takes care of the structure of the tree.
1 becomes the root since it's the first value added.
2 is the left child of 1
3 the right child of 1
4 the left child of 2
5 the right child of 2
6 the left child of 3

SOLUTION:

public void insert(Comparable item) {
    total++;
    if (root == null) {
        root = new TreeNode(item);
    } else {
        int quotient=total;
        Stack path = new Stack();
        TreeNode p = root;  // helper node to follow path
        quotient /= 2;  // skip last step
        while (quotient>1) {    // build path to follow
            path.push(quotient%2);
            quotient /= 2;
        }
        while (!path.isEmpty()) {
            Object q = path.pop();
            if (q.equals(0))
                p = p.getLeft();
            else
                p = p.getRight();
        }
        if (total%2==0) // check last step
            p.setLeft(new TreeNode(item));
        else
            p.setRight(new TreeNode(item));
    }
}

Answer 1

记下树中有多少项。

然后，要添加第 n 项，请遵循通过将 n 重复除以 2 并跟踪余数而创建的路径。遵循由余数反向创建的“路线”:其中 1 表示向右，0 表示向左。

例如，要添加第 11 项:

11/2 = 5 (1)
5/2 = 2 (1)
2/2 = 1 (0)

这意味着从根开始，你会向左、向右、向右。