Как сохранить каждый узел в двоичном дереве поиска в списке?

Question

Я пытаюсь написать функцию в двоичном дереве поиска, который вернет число узлов в дереве, которые имеют значения больше n в форме public int greater (int n). Я полагал, что было бы легче хранить все значения в списке, а затем перебирать список и увеличивать счетчик каждый раз, когда число будет больше, чем n. Как я могу это реализовать?

Это мой класс до сих пор:

public class BST 
{ private BTNode<Integer> root; 
    private int count = 0; 
    List<Integer> arr = new ArrayList<>(); 
    private BST right = new BST(); 
    private BST left = new BST(); 

    public BST() 
    { root = null; 
    } 

    public boolean find(Integer i) 
    { BTNode<Integer> n = root; 
    boolean found = false; 

    while (n!=null && !found) 
    { int comp = i.compareTo(n.data); 
     if (comp==0) 
     found = true; 
     else if (comp<0) 
     n = n.left; 
     else 
     n = n.right; 
    } 

    return found; 
    } 

    public boolean insert(Integer i) 
    { BTNode<Integer> parent = root, child = root; 
    boolean goneLeft = false; 

    while (child!=null && i.compareTo(child.data)!=0) 
    { parent = child; 
     if (i.compareTo(child.data)<0) 
     { child = child.left; 
     goneLeft = true; 
     } 
     else 
     { child = child.right; 
     goneLeft = false; 
     } 
    } 

    if (child!=null) 
     return false; // number already present 
    else 
    { BTNode<Integer> leaf = new BTNode<Integer>(i); 
     if (parent==null) // tree was empty 
     root = leaf; 
     else if (goneLeft) 
     parent.left = leaf; 
     else 
     parent.right = leaf; 
     return true; 
    } 
    } 

    public int greater(int n){ //TODO 
     return 0; 
    } 
} 

class BTNode<T> 
{ T data; 
    BTNode<T> left, right; 

    BTNode(T o) 
    { data = o; left = right = null; 
    } 
} 

Answer 1

Я бы не использовать список в качестве временного хранения.

Существует концепция, называемая Tree Traversal, позволяющая посещать каждый узел вашего дерева.

Вот некоторые псевдо-код:

preorder(node) 
    if (node = null) 
    return 
    visit(node) 
    preorder(node.left) 
    preorder(node.right) 

visit функция здесь выполняется ровно один раз на каждом узле. Для специализированного обхода, как подсчетом вы описали, вы можете просто заменить visit с функциональностью вы хотите, как:

if (node.data > n) { 
    count += 1 
} 

Еще лучше было бы, если вы реализуете Preorder класс, который вы можете расширить, чтобы обеспечить его с пользовательская функция посещения.