Обход предзаказа в дереве бинарного поиска - PullRequest
Новая
       38

Обход предзаказа в дереве бинарного поиска

1 голос
/ 25 сентября 2011

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

void preOrder(Node node) {
    print(node);

    if (node.left() != null)
        preOrder(node.left());
    if (node.right() != null)
        preOrder(node.right());
}

По какой-то причине моя функция распечатывает только левое поддерево корневого узла, и дважды печатает самый нижний узел. Я запустил метод search для одного из элементов с правой стороны, и он вернул true, поэтому я предполагаю, что моя вставка работает правильно. Почему это происходит?

Мой код указан ниже. Открытый метод вызывает приватный. В частном случае первые два оператора if предназначены для печати левого и правого узлов, подключенных к этому узлу. Последние два делают реальный рекурсивный алгоритм. 

public void print() {

    if (root == null)
        System.out.println("Tree is empty");
    else
        print(root);
}


private void print(NodeBST node) {

        printOut(node);

        if (node.left() != null) {
            System.out.print("Left: ");
            printOut(node.left());
        }

        else
            System.out.println("No left");

        if (node.right() != null) {
            System.out.print("Right: ");
            printOut(node.right());
        }

        else
            System.out.println("No right");

        System.out.println("");

        if (node.left() != null) {
            node = node.left();
            print(node);
        }

        if (node.right() != null) {
            node = node.right();
            print(node);
        }
    }

Ответы [ 2 ]

1 голос
/ 01 июня 2014 
struct node *MakeBst(int preOrder[],int str,int end)
{
    struct node *newnode;
    if(str>end)
        return NULL;
    newnode = malloc(sizeof(node));
    if(!newnode)
        return NULL;
    if(str == end)
        return newnode;
    newnode->data = preOrder[str];
    str++;
    x = search_Index(number>preOrder[str-1]);
    newnode->left = MAkeBst(preOrder,str,x-1);
    newnode->right = MAkeBst(preOrder,x-1,end);
}
1 голос
/ 25 сентября 2011

Что ж, у вас есть одна ошибка: вы перезаписываете node в строке непосредственно перед первым print(node), а затем снова используете измененную версию сразу же после этого.Предположительно, вы хотите, чтобы node было исходным значением при выполнении теста if(node.right() != null)?

Вы можете избежать этого, например, просто позвонив print(node.left()); в первый if.

...