Обход в порядке дерева AVL не работает - PullRequest
Новая
       16

Обход в порядке дерева AVL не работает

2 голосов
/ 13 января 2012

Мое дерево AVL реализовано в Java с использованием двумерного массива целых чисел avlTree[35][5] - Столбцы представляют:

  • [0] - Высота слева
  • [1]- Левый ребенок
  • [2] - Данные
  • [3] - Правый ребенок
  • [4] - Высота справа.

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

public void inorderTraversal(int root) {
    if ((Main.avlTree[root][1] == 0) && (Main.avlTree[root][3] == 0)) {
        System.out.println(Main.avlTree[root][2]);
    } else {
        if (Main.avlTree[root][1] != 0) {
            root = Main.avlTree[root][1];
            inorderTraversal(root);
        }
        System.out.println(Main.avlTree[root][2]);

        if (Main.avlTree[root][3] != 0) {
            root = Main.avlTree[root][3];
            inorderTraversal(root);
        }
    }
}

1 Ответ

1 голос
/ 13 января 2012

Я написал эту тестовую программу: 

public class AVLTree {

    /*
        [0] - Height Left
        [1] - Left Child
        [2] - Data
        [3] - Right Child
        [4] - Height Right.
    */
    private static int[][] avlTree;

    public static void main(String[] args) {
        avlTree = new int[4][5];

        // root (L: 1; R: 3)
        avlTree[0][0] = 0;
        avlTree[0][1] = 1;
        avlTree[0][2] = 3005;
        avlTree[0][3] = 2;
        avlTree[0][4] = 1;

        // parent: root (L: -1; R: -1)
        avlTree[1][0] = 0;
        avlTree[1][1] = -1;
        avlTree[1][2] = 73375;
        avlTree[1][3] = -1;
        avlTree[1][4] = 0;

        // parent: root (L: 3; R: -1)
        avlTree[2][0] = 0;
        avlTree[2][1] = 3;
        avlTree[2][2] = 831954;
        avlTree[2][3] = -1;
        avlTree[2][4] = 0;

        // parent: 2 (L: -1; R: -1)
        avlTree[3][0] = 0;
        avlTree[3][1] = -1;
        avlTree[3][2] = 7485;
        avlTree[3][3] = -1;
        avlTree[3][4] = 0;

        inOrder(0);
    }

    private static void inOrder(int root) {
        if(root == -1) {
            // nothing to do
            return ;
        }

        // call function with left child
        inOrder( avlTree[root][1] );

        // print root
        System.out.println( avlTree[root][2]);

        // call function with right child
        inOrder( avlTree[root][3]);
    }
}

, и результат такой, как ожидалось:

73375
3005
7485
831954

У меня тоже нет проблем с вашим кодом;это отлично работает в моем тесте.Может твое дерево ложное?Я бы также предложил использовать -1 в качестве правого / левого ребенка, если его нет;иначе это немного вводит в заблуждение, потому что 0 может означать узел в позиции 0.

...