Создайте полное двоичное дерево, используя связанные списки без сравнения значений узлов - PullRequest
Новая
       3

Создайте полное двоичное дерево, используя связанные списки без сравнения значений узлов

1 голос
/ 11 декабря 2011

Я пытаюсь создать полное двоичное дерево с использованием связанного списка, а не массива, без сравнения значений узлов. Я имею в виду, что при вставке нового значения я не хочу сравнивать, является ли значение меньше, больше или равно значению корня, чтобы добавить его либо к левой ссылке, либо к правой ссылке, но все же иметь возможность создать полное двоичное дерево.

Как вы думаете, это возможно? Если да, у вас есть идея или вы можете указать мне на то, что я могу использовать / прочитать, чтобы сделать это?

EDIT: 

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

Ответы [ 3 ]

11 голосов
/ 11 декабря 2011

Сохраняйте количество элементов в дереве.

Затем, чтобы добавить n -й элемент, следуйте по пути, созданному путем повторного деления n на два и отслеживания остатка.,Следуйте «маршруту», созданному остатком в обратном порядке: где 1 означает правое, а 0 означает левое.

Например, чтобы добавить 11-й элемент: 

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

Это означает от корня, ты бы пошел налево, направо, направо.

1 голос
/ 11 декабря 2011

Кажется, ваш вопрос не имеет отношения к LinkedList .Это немного сбивало с толку.

Если вы знаете, сколько элементов уже есть в дереве, вы можете рассчитать положение по этому числу.Это двоичное представление - путь, по которому вы должны идти.См. здесь .

Если вы ничего не знаете о текущем состоянии дерева, вам нужно выполнить Поиск в ширину , чтобы найти первое пустое место.

0 голосов
/ 11 декабря 2011

Вся основа двоичного дерева заключается в сравнении значений и отправке их влево или вправо по дереву.

Следовательно, невозможно создать двоичное дерево без сравнений.

Но вы сказали upon insertion, чтобы вы могли добавить элемент в конец списка, а затем отсортировать его при вызове дерева. Как это: 

list.add(value); //Just add the item to the end

call(); //This method would sort the list into a tree appropriately.

Эта опция также позволяет вам динамически изменять тип дерева, поскольку вы можете добавить параметр к call(), который указывает тип дерева.

...