Назначить упорядоченный индекс двоичному дереву

Как мы назначаем индекс по порядку двоичному дереву?

Учитывая дерево ниже:

      1
   2      3
4    5  6   7

Назначьте индекс ниже дереву выше, как вы можете видеть ниже:

      4
   2      6
1    3  5    7

Следующий код не работает для случая 6, поскольку он присваивает 10, поскольку мы дважды считаем переданный индекс из аргумента и из левого дочернего элемента. Можем ли мы добиться этого без использования глобальной переменной?

  int assignIndex(Node root, int index) {
        if (root == null)
            return 0;

        int leftIndex = assignIndex(root.left, index);

        root.index = leftIndex + index + 1;

        int rightIndex = assignIndex(root.right, root.index);

        if (rightIndex == 0)
            return root.index;
        else
            return rightIndex;
    }

algorithm data-structures array-algorithms binary-tree
person user_1357    schedule 07.03.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

int assignIndex(Node root, int index) {

    if (root.left != null)
       index = assignIndex(root.left, index);  

    index++;
    root.index = index;

    if (root.right != null)
       index = assignIndex(root.right, index);

    return index;

}
person Len    schedule 07.03.2018