二进制搜索树 - 打印出叶子的数量

Question

我有一个程序是二叉搜索树，该方法搜索特定的单词。我有两个问题。

1. 首先是我想从这个方法打印true或false（基本上做一个system.out，说如果该单词被找到），我假设我会做主，但我是不知道该怎么做。
2. 第二个问题是我还需要打印出树上有多少叶子，我打算在该方法中使用某种计数器，但是我没有工作。

我的方法在下面，但我也将它包含在课堂内部以帮助消除任何混淆。

任何帮助将不胜感激。

public boolean check(BSTNode t,String key) 
{ 
    if (t == null) return false; 
    if (t.word.equals(key)) return true; 
    if (check(t.left,key)) return true; 
    if (check(t.right,key)) return true; 
    return false; 
} 

---

全班同学：

public class BST 
{ 
    BSTNode root; 
    BST() { 
     root = null; 
    } 

    public void add2Tree(String st) 
    { 
     BSTNode newNode = new BSTNode(st); 
     if (this.root == null) { 
      root = newNode; 
     } else { 
      root = addInOrder(root, newNode); 
     } 
    } 
    // private BSTNode insert2(BSTNode root, BSTNode newNode) 
    // { 
    // if (root == null) 
    // root = newNode; 
    // else { 
    // System.out.println(root.word + " " + newNode.word); 
    // if (root.word.compareTo(newNode.word) > 0) 
    // { 
    // root.left = (insert2(root.lTree, newNode)); 
    // System.out.println(" left "); 
    // } else 
    // { 
    // root.rTree = (insert2(root.rTree, newNode)); 
    // System.out.println(" right "); 
    // } 
    // } 
    // return root; 
    // } 

    public BSTNode addInOrder(BSTNode focus, BSTNode newNode) { 
     int comparevalue = 0; 

     if (focus == null) { 
      focus = newNode; 
     } 

     if (focus != null) { 
      comparevalue = newNode.word.compareTo(focus.word); 
     } 
     if (comparevalue < 0) { 
      focus.left = addInOrder(focus.left, newNode); 
     } else if (comparevalue > 0) { 
      focus.right = addInOrder(focus.right, newNode); 
     } 
     return (focus); 
    } 

    public void ioprint() { 
     System.out.println(" start inorder"); 
     if (root == null) 
      System.out.println(" Null"); 
     printinorder(root); 
    } 

    public void printinorder(BSTNode t) { 
     if (t != null) { 
      printinorder(t.left); 
      System.out.println(t.word); 
      printinorder(t.right); 
     } 
    } 

    public boolean check(BSTNode t,String key) 
    { 
     if (t == null) return false; 
     if (t.word.equals(key)) return true; 
     if (check(t.left,key)) return true; 
     if (check(t.right,key)) return true;  
     return false;  
    } 

    public BSTNode getroot(){ 
     return root; 
    } 
} 

Answer 1

如何打印真/假：

1. 创建另一个类，称之为Solution，Test或任何你喜欢。
2. 添加一个主要方法。
3. 填入您的BST。
4. 致电System.out.println(check(bstRoot, key))。

您可以检查此链接了解如何计算在BST节点的数量，这是非常简单的：

Counting the nodes in a binary search tree

private int countNodes(BSTNode current) { 
    // if it's null, it doesn't exist, return 0 
    if (current == null) return 0; 
    // count myself + my left child + my right child 
    return 1 + nodes(current.left) + nodes(current.right); 
}