Wie speichert man jeden Knoten in einem binären Suchbaum in einer Liste?

Question

Ich versuche, eine Funktion in einer binären Suchbaum-Klasse zu schreiben, die die Anzahl der Knoten in der Struktur zurückgibt, die Werte größer als n in der Form public int greater (int n) haben. Ich dachte, es wäre einfacher, alle Werte in einer Liste zu speichern und dann über die Liste zu iterieren und die Anzahl zu erhöhen, wenn eine Zahl größer als n ist. Wie würde ich das umsetzen?

Das ist meine Klasse so weit:

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

ich eine Liste nicht als Zwischenspeicher verwenden würde.

Es gibt ein Konzept namens Tree Traversal, mit dem Sie jeden Knoten Ihres Baums besuchen können. Hier

ist einige Pseudocode:

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

Die visit hier Funktion genau einmal an jedem Knoten ausgeführt wird. Für eine spezielle Traversal wie das Zählen Sie beschrieben, könnten Sie einfach visit mit der Funktionalität ersetzen Sie wollen, wie:

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

Noch besser wäre es, wenn Sie eine Preorder Klasse implementieren, die Sie es mit einem schaffen verlängern benutzerdefinierte Besuchsfunktion.