各ノードをバイナリ検索ツリーにリストに格納する方法は？

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を置き換えることができます：あなたはあなたがそれを提供するために拡張することができPreorderクラスを実装する場合になりさらに良い

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

カスタム訪問機能。