package lrs.visitor; import lrs.*; import brs.*; /** * Builds a full BST from a sorted list. * @Copyright: Copyright (c) 2003 D.X. Nguyen - All rights reserved * @author D. X. Nguyen * @version 1.0 */ public class BuildFullTree implements IAlgo { public static final BuildFullTree Singleton = new BuildFullTree(); private BuildFullTree() { } /** * What's a full BST that is built from an empty list? * @param host * @param inp * @return BiTree */ public Object emptyCase(LRStruct host, Object inp) { return new BiTree(); } /** * Splits the list in half and recursively builds the right subtree from * the right half and the left subtree from the left half. * @param host * @param inp * @return BiTree */ public Object nonEmptyCase(LRStruct host, Object inp) { LRStruct rightHalf = (LRStruct)host.execute(Splitter.Singleton, null); BiTree result = new BiTree(); result.insertRoot(rightHalf.getFirst()); result.setRightSubTree((BiTree)rightHalf.getRest().execute(this, null)); result.setLeftSubTree((BiTree)host.execute(this,null)); return result; } /** * "Quick and dirty" test. * @param notUsed */ public static void main(String[] notUsed) { LRStruct L = new LRStruct(); L.insertFront(new Integer(8)); L.insertFront(new Integer(7)); L.insertFront(new Integer(6)); L.insertFront(new Integer(5)); L.insertFront(new Integer(4)); L.insertFront(new Integer(3)); L.insertFront(new Integer(2)); L.insertFront(new Integer(1)); System.out.println(L); System.out.println(L.execute(BuildFullTree.Singleton, null)); } }