求一个倾斜90度打印树的方法

源代码如下public class BinarySearchTree<T extends KeyedItem<KT>,
                             KT extends Comparable<? super KT>>
             extends BinaryTreeBasis<T> {
  // inherits isEmpty(), makeEmpty(), getRootItem(), and
  // the use of the constructors from BinaryTreeBasis
   
  public BinarySearchTree() {
  }  // end default constructor
   
  public BinarySearchTree(T rootItem) {
    super(rootItem);
  }  // end constructor  public void setRootItem(T newItem) 
              throws UnsupportedOperationException {
    throw new UnsupportedOperationException();
  }  // end setRootItem  public void insert(T newItem) {
    root = insertItem(root, newItem);
  }  // end insert
   
  public T retrieve(KT searchKey) {
    return retrieveItem(root, searchKey);
  }  // end retrieve
   
  public void delete(KT searchKey)
              throws TreeException {
    root = deleteItem(root, searchKey);
  }  // end delete
   
  public void delete(T item) 
              throws TreeException {
    root = deleteItem(root, item.getKey());
  }  // end delete
   
  protected TreeNode<T> insertItem(TreeNode<T> tNode, 
                                   T newItem) {
    TreeNode<T> newSubtree;
    if (tNode == null) {
      // position of insertion found; insert after leaf
      // create a new node
      tNode = new TreeNode<T>(newItem, null, null);
      return tNode;
    }  // end if
    T nodeItem = tNode.getItem();
      
    // search for the insertion position
      
    if (newItem.getKey().compareTo(nodeItem.getKey()) < 0) {
      // search the left subtree
      newSubtree = insertItem(tNode.getLeft(), newItem);
      tNode.setLeft(newSubtree);
      return tNode;
    }
    else { // search the right subtree
      newSubtree = insertItem(tNode.getRight(), newItem);
      tNode.setRight(newSubtree);
      return tNode;
    }  // end if
  }  // end insertItem
   
  protected T retrieveItem(TreeNode<T> tNode, 
                           KT searchKey) {
    T treeItem;
    if (tNode == null) {
      treeItem = null;
    }
    else {
      T nodeItem = tNode.getItem();
      if (searchKey.compareTo(nodeItem.getKey()) == 0) {
        // item is in the root of some subtree
        treeItem = tNode.getItem();
      }
      else if (searchKey.compareTo(nodeItem.getKey()) < 0) {
        // search the left subtree
        treeItem = retrieveItem(tNode.getLeft(), searchKey);
      }
      else { // search the right subtree
        treeItem = retrieveItem(tNode.getRight(), searchKey);
      }  // end if
    }  // end if
    return treeItem;
  }  // end retrieveItem
   
  protected TreeNode<T> deleteItem(TreeNode<T> tNode, 
                                   KT searchKey) {
    // Calls: deleteNode.
    TreeNode<T> newSubtree;
    if (tNode == null) {
throw new TreeException("TreeException: Item not found");
}
    else {
      T nodeItem = tNode.getItem();
      if (searchKey.compareTo(nodeItem.getKey()) == 0) {
        // item is in the root of some subtree
        tNode = deleteNode(tNode);  // delete the item
      }
      // else search for the item
      else if (searchKey.compareTo(nodeItem.getKey()) < 0) {
        // search the left subtree
        newSubtree = deleteItem(tNode.getLeft(), searchKey);
        tNode.setLeft(newSubtree);
      }
      else { // search the right subtree
        newSubtree = deleteItem(tNode.getRight(), searchKey);
        tNode.setRight(newSubtree);
      }  // end if
    }  // end if
    return tNode;
  }  // end deleteItem
   
  protected TreeNode<T> deleteNode(TreeNode<T> tNode) {
    // Algorithm note: There are four cases to consider:
    //   1. The tNode is a leaf.
    //   2. The tNode has no left child.
    //   3. The tNode has no right child.
    //   4. The tNode has two children.
    // Calls: findLeftmost and deleteLeftmost
    T replacementItem;
      
    // test for a leaf
    if ( (tNode.getLeft() == null) &&
         (tNode.getRight() == null) ) {
      return null;
    }  // end if leaf
         
    // test for no left child
    else if (tNode.getLeft() == null) {
      return tNode.getRight();
    }  // end if no left child
         
    // test for no right child
    else if (tNode.getRight() == null) {
      return tNode.getLeft();
    }  // end if no right child
         
    // there are two children:
    // retrieve and delete the inorder successor
    else {
      replacementItem = findLeftmost(tNode.getRight());
      tNode.setItem(replacementItem);
      tNode.setRight(deleteLeftmost(tNode.getRight()));
      return tNode;
    }  // end if
  }  // end deleteNode
   
  protected T findLeftmost(TreeNode<T> tNode)  {
    if (tNode.getLeft() == null) {
      return tNode.getItem();
    }
    else {
      return findLeftmost(tNode.getLeft());
    }  // end if
  }  // end findLeftmost
   
  protected TreeNode<T> deleteLeftmost(TreeNode<T> tNode) {
    if (tNode.getLeft() == null) {
      return tNode.getRight();
    }
    else {
      tNode.setLeft(deleteLeftmost(tNode.getLeft()));
      return tNode;
    }  // end if
  }  // end deleteLeftmost
  
     
}  // end BinarySearchTreepublic abstract class BinaryTreeBasis<T> {
  protected TreeNode<T> root;  public BinaryTreeBasis() {
    root = null;
  }  // end default constructor  public BinaryTreeBasis(T rootItem) {
    root = new TreeNode<T>(rootItem, null, null);
  }  // end constructor  public boolean isEmpty() {
  // Returns true if the tree is empty, else returns false.
    return root == null;
  }  // end isEmpty  public void makeEmpty() {
  // Removes all nodes from the tree.
    root = null;
  }  // end makeEmpty  public T getRootItem() throws TreeException {
  // Returns the item in the trees root.
    if (root == null) {
      throw new TreeException("TreeException: Empty tree");
    }
    else {
      return root.getItem();
    }  // end if
  }  // end getRootItem  public abstract void setRootItem(T newItem); 
    // Throws UnsupportedOperationException if operation
    // is not supported. }  // end BinaryTreeBasis
public abstract class KeyedItem<KT extends Comparable<?super KT>> {
   private KT searchKey;   public KeyedItem(KT key) {
      searchKey = key;
   }  // end constructor   public KT getKey() {
      return searchKey;
   } // end getKey  public String toString() {
    return searchKey.toString();
  } // end toString} // end KeyedItem[code=Java]public class TreeNode<T> {
  private T item;
  private TreeNode<T> leftChild;
  private TreeNode<T> rightChild;  public TreeNode(T newItem) {
  // Initializes tree node with item and no children.
    item = newItem;
    leftChild  = null;
    rightChild = null;
  }  // end constructor
    
  public TreeNode(T newItem, 
                  TreeNode<T> left, TreeNode<T> right) {
  // Initializes tree node with item and
  // the left and right children references.
    item = newItem;
    leftChild  = left;
    rightChild = right;
  }  // end constructor  public T getItem() {
  // Returns the item field.
    return item;
  }  // end getItem  public void setItem(T newItem) {
  // Sets the item field to the new value newItem.
    item  = newItem;
  }  // end setItem  public TreeNode<T> getLeft() {
  // Returns the reference to the left child.
    return leftChild;
  }  // end getLeft  public void setLeft(TreeNode<T> left) {
  // Sets the left child reference to left.
    leftChild  = left;
  }  // end setLeft  public TreeNode<T> getRight() {
  // Returns the reference to the right child.
    return rightChild;
  }  // end getRight  public void setRight(TreeNode<T> right) {
  // Sets the right child reference to right.
    rightChild  = right;
  }  // end setRight
}  // end TreeNodeimport java.util.LinkedList;public class TreeIterator<T> implements java.util.Iterator<T> {
private BinaryTreeBasis<T> binTree;
  private TreeNode<T> currentNode;
  private LinkedList <TreeNode<T>> queue; // from JCF  public TreeIterator(BinaryTreeBasis<T> bTree) {
    binTree = bTree;
    currentNode = null; 
    // empty queue indicates no traversal type currently 
    // selected or end of current traversal has been reached
    queue = new LinkedList <TreeNode<T>>();
  }  // end constructor  public boolean hasNext() {
    return !queue.isEmpty();
  }  // end hasNext  public T next() 
           throws java.util.NoSuchElementException {
      currentNode = queue.remove();
      return currentNode.getItem();
  }  // end next  public void remove() 
              throws UnsupportedOperationException {
    throw new UnsupportedOperationException();
  }  // end remove  public void setPreorder() {
    queue.clear();
    preorder(binTree.root);
  }  // setPreOrder  public void setInorder() {
    queue.clear();
    inorder(binTree.root);
  }  // end setInorder  public void setPostorder() {
    queue.clear();
    postorder(binTree.root);
  }  // end setPostorder  private void preorder(TreeNode<T> treeNode) {
    if (treeNode != null) {  
      queue.add(treeNode);
      preorder(treeNode.getLeft());
      preorder(treeNode.getRight());
    } // end if
  }  // end preorder  private void inorder(TreeNode<T> treeNode) {
    if (treeNode != null) {  
      inorder(treeNode.getLeft());
      queue.add(treeNode);
      inorder(treeNode.getRight());
    } // end if
  }  // end inorder  private void postorder(TreeNode<T> treeNode) {
    if (treeNode != null) {  
      postorder(treeNode.getLeft());
      postorder(treeNode.getRight());
      queue.add(treeNode);
    } // end if
  }  // end postorder
}  // end TreeIterator
[/code]