使用链接列表创建完整的二叉树，不比较节点值 [英] Create a Complete Binary Tree using Linked Lists w/o comparing node values

问题描述

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

I am trying to create a complete binary tree using a linked list, instead of arraylist, without comparing node values. What I mean is on inserting a new value, I do not wish to compare if the value is less, greater or equal than the root's value, so as to add it either to the left link or to the right link, but still be able to create a complete binary tree.

您认为有可能吗?如果是，您有任何想法吗?或者您可以指出我可以使用/阅读的方法吗?

Do you think it's possible? If yes, do you have any idea or can you point me to something I can use/read to do it?

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

解决方案:

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

推荐答案

保持对树中有多少项的计数.

Keep a count of how many items you have in the tree.

然后，要添加第n个项目，请遵循以下步骤创建的路径:将n重复除以2，并跟踪其余部分.遵循其余部分反向创建的路线":其中1表示右侧，0表示左侧.

Then, to add the nth item follow the path created by dividing n repeatedly by two and keeping track of the remainder. Follow the "route" created by the remainder in reverse: where 1 means right and 0 means left.

例如，要添加第11个项目:

For example, to add the 11th item:

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

这意味着从根开始，您将向左，向右，向右走.

That means from the root, you'd go left, right, right.

这篇关于使用链接列表创建完整的二叉树，不比较节点值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！