如何从二进制搜索树按字母顺序打印？

Question

使用这个BST类，我能够打印出字符串，但我不知道如何按字母顺序打印它们。请帮忙。我需要在这个BST类中创建一个方法，其中元素按字母顺序打印出来。谢谢。

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> 
    { 
     /** 
     * Construct the tree. 
     */ 
     private BinaryNode<AnyType> root; 
     public BinarySearchTree() 
    { 
     root = null; 
    } 

    /** 
    * Insert into the tree; duplicates are ignored. 
    * @param x the item to insert. 
    */ 
    public void insert(AnyType x) 
    { 
     root = insert(x, root); 
    } 

    /** 
    * Remove from the tree. Nothing is done if x is not found. 
    * @param x the item to remove. 
    */ 
    public void remove(AnyType x) 
    { 
     root = remove(x, root); 
    } 

    /** 
    * Find the smallest item in the tree. 
    * @return smallest item or null if empty. 
    */ 
    public AnyType findMin() 
    { 
     if(isEmpty()) 
      throw new UnderflowException("No elements found"); 
     return findMin(root).element; 
    } 

    /** 
    * Find the largest item in the tree. 
    * @return the largest item of null if empty. 
    */ 
    public AnyType findMax() 
    { 
     if(isEmpty()) 
      throw new UnderflowException("No elements found"); 
     return findMax(root).element; 
    } 

    /** 
    * Find an item in the tree. 
    * @param x the item to search for. 
    * @return true if not found. 
    */ 
    public boolean contains(AnyType x) 
    { 
     return contains(x, root); 
    } 

    /** 
    * Make the tree logically empty. 
    */ 
    public void makeEmpty() 
    { 
     root = null; 
    } 

    /** 
    * Test if the tree is logically empty. 
    * @return true if empty, false otherwise. 
    */ 
    public boolean isEmpty() 
    { 
     return root == null; 
    } 

    /** 
    * Print the tree contents in sorted order. 
    */ 
    public void printTree() 
    { 
     if(isEmpty()) 
      System.out.println("Empty tree"); 
     else 
      printTree(root); 
    } 

    /** 
    * Internal method to insert into a subtree. 
    * @param x the item to insert. 
    * @param t the node that roots the subtree. 
    * @return the new root of the subtree. 
    */ 
    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) 
    { 
     if(t == null) 
      return new BinaryNode<AnyType>(x, null, null); 

     int compareResult = x.compareTo(t.element); 

     if(compareResult < 0) 
      t.left = insert(x, t.left); // if new item < x --> insert to its left 
     else if(compareResult > 0) 
      t.right = insert(x, t.right); //if new item > x ---> insert to its right 
     else 
      ; // Duplicate; do nothing 
     return t; 
    } 

    /** 
    * Internal method to remove from a subtree. 
    * @param x the item to remove. 
    * @param t the node that roots the subtree. 
    * @return the new root of the subtree. 
    */ 
    private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) 
    { 
     if(t == null) 
      return t; // Item not found; do nothing 

     int compareResult = x.compareTo(t.element); 

     if(compareResult < 0) 
      t.left = remove(x, t.left); 
     else if(compareResult > 0) 
      t.right = remove(x, t.right); 
     else if(t.left != null && t.right != null) // Two children 
     { 
      t.element = findMin(t.right).element; 
      t.right = remove(t.element, t.right); 
     } 
     else 
      t = (t.left != null) ? t.left : t.right; 
     return t; 
    } 

    /** 
    * Internal method to find the smallest item in a subtree. 
    * @param t the node that roots the subtree. 
    * @return node containing the smallest item. 
    */ 
    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) 
    { 
     if(t == null) 
      return null; 
     else if(t.left == null) 
      return t; 
     return findMin(t.left); 
    } 

    /** 
    * Internal method to find the largest item in a subtree. 
    * @param t the node that roots the subtree. 
    * @return node containing the largest item. 
    */ 
    private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) 
    { 
     if(t != null) 
      while(t.right != null) 
       t = t.right; 

     return t; 
    } 

    /** 
    * Internal method to find an item in a subtree. 
    * @param x is item to search for. 
    * @param t the node that roots the subtree. 
    * @return node containing the matched item. 
    */ 
    private boolean contains(AnyType x, BinaryNode<AnyType> t) 
    { 
     if(t == null) 
      return false; 

     int compareResult = x.compareTo(t.element); 

     if(compareResult < 0) 
      return contains(x, t.left); 
     else if(compareResult > 0) 
      return contains(x, t.right); 
     else 
      return true; // Match 
    } 

    /** 
    * Internal method to print a subtree in sorted order. 
    * @param t the node that roots the subtree. 
    */ 
    private void printTree(BinaryNode<AnyType> t) 
    { 
     if(t != null) 
     { 
      printTree(t.left); 
      System.out.println(t.element); 
      printTree(t.right); 
     } 
    } 

    /** 
    * Internal method to compute height of a subtree. 
    * @param t the node that roots the subtree. 
    */ 
    private int height(BinaryNode<AnyType> t) 
    { 
     if(t == null) 
      return -1; 
     else 
      return 1 + Math.max(height(t.left), height(t.right));  
    } 

    // Node object that stores an element + left and right nodes of the same type 
    //*********************************************NEW CLASS******************************************* 
    private static class BinaryNode<AnyType> 
    { 
      // Constructors 
     BinaryNode(AnyType theElement) 
     { 
      this(theElement, null, null); 
     } 

     BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) 
     { 
      element = theElement; 
      left  = lt; 
      right = rt; 
     } 

     AnyType element;   // The data in the node 
     BinaryNode<AnyType> left; // Left child 
     BinaryNode<AnyType> right; // Right child 
    } 

} 
class UnderflowException extends RuntimeException 
{ 
    /** 
    * Construct this exception object. 
    * @param message the error message. 
    */ 
    public UnderflowException(String message) 
    { 
     super(message); 
    } 
} 

Answer 1

当您在BST上执行in-order traversal时，它会按排序顺序为您提供节点。

在类似Java的伪代码的想法：

public void printSorted(node) { 
    if (node == null) return; 
    printSorted(node.left); 
    System.out.println(node.value); //or any other manipulation of the node 
    printSorted(node.right); 
} 

（PS比我建议的是使递归调用的BinaryNode<AnyType>的方法，如果this.left == null和this.right == null递归检查之前更好的设计，并对它们进行递归，这很容易从上面的伪代码中修改它）。

Answer 2

由于字母顺序排列的顺序与您访问的树是无关的，你应该分解你的解决方案是这样的：

1. 参观树储存于容器中的字符串
2. 那种容器