Хранить счетчик в рекурсивной функции двоичного дерева в Java

Question

Я делаю упражнение для школы, где мне нужно создать метод в java (не более O (n) времени), в котором хранится порядок, в котором заданное значение появляется в двоичном дереве, будь то в последующем порядке, в -заказ или обход предварительного заказа. Пока у меня есть рабочий код, но счетчик не увеличивается должным образом. Может кто-нибудь сообщить мне, что я делаю не так? Мой код выглядит следующим образом:

public class Node {

int value;                // data used as key value
Node left;                // this node's left child
Node right;               // this node's right child
int preorderNumber; // node number in preorder
int inorderNumber; // node number in inorder
int postorderNumber; // node number in postorder


public Node(int item) { //instantiates node.
    value = item;
    left = right = null;
    preorderNumber = inorderNumber = postorderNumber = 0;
}

}

/* Given a binary tree, print its nodes according to the postorder traversal. */
private void printPostorder(Node node) {
    int counter = 0;

    if (node == null) { //the tree is empty. 
        return;
    }
    printPostorder(node.left); // first recur on left subtree 
    printPostorder(node.right); // then recur on right subtree
    System.out.print(node.value + " "); // now deal with the node
    counter++;
    node.postorderNumber = counter;
}

/* Given a binary tree, print its nodes in inorder*/
private void printInorder(Node node) {
    int counter = 0;

    if (node == null) {
        return;
    }
    printInorder(node.left);   // first recur on left child
    System.out.print(node.value + " "); // then print the data of node
    counter++;
    node.inorderNumber = counter;
    printInorder(node.right); // now recur on right child 
}

/* Given a binary tree, print its nodes in preorder*/
private void printPreorder(Node node) {
    int counter = 0;

    if (node == null) { //binary tree is empty. 
        return;
    }
    System.out.print(node.value + " "); // first print data of node.
    counter++;
    node.preorderNumber = counter;
    printPreorder(node.left); //  recur on left subtree 
    printPreorder(node.right); // now recur on right subtree 
}

public int find(int valueToFind) { 
    Node current = root, prior = null; 
    while (current != null) {
        int compare;
        compare = (valueToFind - current.value);
        if (compare < 0) {
            prior = current;
            current = current.left;
        } else if (compare > 0) {
            current = current.right;
        } else {
            System.out.println("The node value searched for is : " + valueToFind);
            System.out.println("The in order value is: " + current.inorderNumber);
            System.out.println("The post order value is: " + current.postorderNumber);
            System.out.println("The pre order value is: " + current.preorderNumber);
            return current.value;
        }
    }
    return prior == null ? null : prior.value;
}

}

Однако всякий раз, когда я пытаюсь запустить это, я получаю что-то вроде следующего:

Количество узлов: 2 Предзаказ обхода бинарного дерева 3 4 Обход по бинарному дереву 3 4 Обращение по порядку бинарного дерева 4 3 Требуемое значение узла: 4 Значение в заказе: 1 Значение почтового заказа: 1 Предварительный заказ: 1

Я не уверен, как передать значение счетчика узлу, чтобы он содержал правильное значение (в данном случае 2, 2 и 1). Спасибо!

Answer 1

Вам нужно получить счетчик от значения prv. В противном случае он будет сброшен все время. сделать это как показано ниже

private void printPostorder(Node node) {

    if (node == null) { //the tree is empty. 
        return;
    }

    int counter = node.postorderNumber;

    printPostorder(node.left); // first recur on left subtree 
    printPostorder(node.right); // then recur on right subtree
    System.out.print(node.value + " "); // now deal with the node
    counter++;
    node.postorderNumber = counter;
}

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