Как я могу установить позиции для каждого узла в дереве двоичного поиска? - PullRequest
Новая
       40

Как я могу установить позиции для каждого узла в дереве двоичного поиска?

0 голосов
/ 27 июня 2018

Я хочу построить BST и установить каждый из моих узлов в порядке возрастания. Например, если двоичное дерево поиска содержит 3, 6, 2, 4, позиции узла должны быть pos1-2, pos2-3, pos3-4, pos4-6. Вот мой метод insertBST 

TreeNode insertBST(TreeNode parent, int value) {
    if (parent == null) {
        parent = new TreeNode(value);
        return parent;
    }
    if (value <= parent.value) {
        parent.leftChild = this.insertBST(parent.leftChild, value);
    } else if (value >= this.root.value) {
        parent.rightChild = this.insertBST(this.root.rightChild, value);
    }

    return parent;
}

Вот метод inOrderTraverseBST, для которого я хочу установить позиции. 

int count = 0;
public void inOrderTraverseBST(TreeNode root) {
    if (root == null) {
        return;
    }
    this.inOrderTraverseBST(root.leftChild);
    root.position = this.count;
    this.count++;
    this.inOrderTraverseBST(root.rightChild);
    root.position = this.count;
}

Но метод inOrderTraversBST неверен. Поэтому я хочу знать, как я могу написать метод для метода inOrderTraverseBST, чтобы установить все позиции для узлов.

1 Ответ

0 голосов
/ 27 июня 2018

Просто удалите последнюю строку. С его помощью вы переназначаете позицию узла после прохождения его правого поддерева.

Немного упрощая 

public void inOrderTraverseBST(TreeNode root) {
    if (root == null) {
        return;
    }
    this.inOrderTraverseBST(root.leftChild);
    root.position = this.count++;
    this.inOrderTraverseBST(root.rightChild);
}
...