如何將每個節點存儲在列表中的二叉搜索樹中？

我正在嘗試在二叉搜索樹類中編寫一個函數，該函數將返回值爲public int greater (int n)的值大於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; 
    } 
}

來源

2017-02-04 James McCutcheon

我不會用一個列表作爲臨時存儲。

有一個概念叫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類，你可以擴展爲它提供一個自定義訪問功能。

來源

2017-02-09 00:23:58 Hannes

如何將每個節點存儲在列表中的二叉搜索樹中？

回答

相關問題