SHARE
TWEET

TreePosition

Krokant17 Jul 17th, 2017 64 in 25 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Note: Implementation is a sample framework, e.g. it would be better to define an Exception "PathException" instead of throwing "Exception"
  2. public class TreePosition{
  3.     private static Tree testTree;
  4.     private static void initializeTestTree(){
  5.         testTree = new Tree();
  6.         testTree.insert(15);
  7.         testTree.insert(10);
  8.         testTree.insert(20);
  9.         testTree.insert(5);
  10.         testTree.insert(12);
  11.         testTree.insert(17);
  12.         testTree.insert(25);
  13.         testTree.insert(7);
  14.         testTree.insert(34);
  15.         //This is the testTree:
  16.         //              15
  17.         //         ____/  \____
  18.         //       10            20
  19.         //     _/  \_        _/  \_
  20.         //    5      12    17      25
  21.         //     \                  /
  22.         //      7               34
  23.     }
  24.     public static void main(String[] args){
  25.         initializeTestTree();
  26.         //Example for a Position in testTree: root -> left son -> right son
  27.         TreePosition testPos1 = new TreePosition(testTree, "lr");
  28.         System.out.println("Print of TestPosition:");
  29.         System.out.println(testPos1);
  30.        
  31.         //(TODO) Choose a path for testPos each for preNext and postNext:
  32.         String testPathPre = "";
  33.         String testPathPost = "";
  34.        
  35.         //Not to do ;) :
  36.         TreePosition testPosPre = new TreePosition(testTree, testPathPre);
  37.         TreePosition testPosPost = new TreePosition(testTree, testPathPost);
  38.        
  39.         //After implementation of preNext, postNext: UNCOMMENT this:
  40.         //System.out.println(preNext(testPosPre));
  41.         //System.out.println(postNext(testPosPost));
  42.     }
  43.     //A TreePosition is implemented as a tuple (Tree, String):
  44.     /**
  45.     * Tree is the information about the tree to which the TreePosition refers to
  46.     */
  47.     Tree treeContainingNode;
  48.     /**
  49.     * String represents the position as path from the root of the Tree, with:
  50.     * <code>l</code> for a walk to the left child, and
  51.     * <code>r</code> for a walk to the right child.
  52.     * Walk is performed from leftmost index to rightmost.
  53.     * Empty String means root.
  54.     */
  55.     String positionAsLRPath;
  56.    
  57.     public TreePosition(Tree treeContainingNode){
  58.         this.treeContainingNode = treeContainingNode;
  59.         positionAsLRPath = "";
  60.     }
  61.     public TreePosition(Tree treeContainingNode, String positionAsLRPath){
  62.         this.treeContainingNode = treeContainingNode;
  63.         this.positionAsLRPath = positionAsLRPath;
  64.     }
  65.    
  66.     //TODO
  67.     public static TreePosition preNext(TreePosition v){
  68.         //TODO
  69.         return null;
  70.     }
  71.     public static TreePosition postNext(TreePosition v){
  72.         //TODO
  73.         return null;
  74.     }
  75.    
  76.    
  77.     //Useful methods
  78.     private static boolean hasLeftChild(TreePosition v){
  79.         try{
  80.             return v.nodeAtPosition().left == null;
  81.         } catch(Exception e){
  82.             return false;
  83.         }
  84.     }
  85.     private static boolean hasRightChild(TreePosition v){
  86.         try{           
  87.             return v.nodeAtPosition().right == null;
  88.         } catch(Exception e){
  89.             return false;
  90.         }
  91.     }
  92.     private static boolean isRoot(TreePosition v){
  93.         return v.positionAsLRPath.equals("");
  94.     }
  95.     private static boolean isInternal(TreePosition v){
  96.         try{
  97.             TreeNode tn = v.nodeAtPosition();
  98.             return tn.left != null || tn.right != null;
  99.         } catch(Exception e){
  100.             return false;
  101.         }
  102.     }
  103.     private static TreePosition leftChild(TreePosition v){
  104.         return v.walk("l");
  105.     }
  106.     private static TreePosition rightChild(TreePosition v){
  107.         return v.walk("r");
  108.     }
  109.     private static TreePosition parent(TreePosition v){
  110.         return v.walk("f");
  111.     }
  112.    
  113.     /**
  114.     * Walk through tree, l: left son, r: right son, f: father/parent
  115.     */
  116.     TreePosition walk(String path){
  117.         String pathToWalk = this.positionAsLRPath;
  118.         for(char c : path.toCharArray()){
  119.             switch(c){
  120.                 case 'l':
  121.                 case 'r':
  122.                     pathToWalk += c;
  123.                     break;
  124.                 case 'f':
  125.                     pathToWalk = (pathToWalk.length() == 0 ? "" : pathToWalk.substring(0, pathToWalk.length()-1));
  126.                     break;
  127.                 default:
  128.                     //ignore wrong symbols
  129.                     break;
  130.             }
  131.         }
  132.         return new TreePosition(this.treeContainingNode, pathToWalk);
  133.     }
  134.     TreeNode nodeAtPosition() throws Exception {
  135.         String errorMessage = "Path not valid in this tree.";
  136.         if(treeContainingNode.root == null)
  137.             throw new Exception(errorMessage);
  138.         TreeNode currentNode = treeContainingNode.root;
  139.         for(
  140.                 String walkingLeft = positionAsLRPath;
  141.                 walkingLeft.length() > 0;
  142.                 walkingLeft = walkingLeft.substring(1)
  143.             ){
  144.             TreeNode next = null;
  145.             switch(walkingLeft.charAt(0)){
  146.                 case 'l':
  147.                     next = currentNode.left;
  148.                     if(next == null)
  149.                         throw new Exception(errorMessage);
  150.                     currentNode = next;
  151.                     break;
  152.                 case 'r':
  153.                     next = currentNode.right;
  154.                     if(next == null)
  155.                         throw new Exception(errorMessage);
  156.                     currentNode = next;
  157.                     break;
  158.                 default:
  159.                     //ignore wrong symbols
  160.                     break;
  161.             }
  162.         }
  163.         return currentNode;
  164.     }
  165.     int keyAtPosition() throws Exception {
  166.         return nodeAtPosition().key;
  167.     }
  168.    
  169.     @Override
  170.     public String toString(){
  171.         String ret = "Tree:\n"+treeContainingNode.toString()+"\nPath to position: ";
  172.         if(positionAsLRPath.length() == 0){
  173.             ret += "[no path]";
  174.         } else {
  175.             switch(positionAsLRPath.charAt(0)){
  176.                 case 'l':
  177.                     ret += "left";
  178.                     break;
  179.                 case 'r':
  180.                     ret += "right";
  181.                     break;
  182.                 //Ensure that the FIRST CHARACTER is correct! This is an issue.
  183.             }
  184.                 String pathLeft = positionAsLRPath.substring(1);
  185.                 while(pathLeft.length() > 0){
  186.                     switch(pathLeft.charAt(0)){
  187.                     case 'l':
  188.                         ret += " -> left";
  189.                         break;
  190.                     case 'r':
  191.                         ret += " -> right";
  192.                         break;
  193.                     default:
  194.                         //ignore wrong symbols
  195.                         break;
  196.                     }
  197.                     pathLeft = pathLeft.substring(1);
  198.                 }
  199.             }
  200.         //Code can be improved e.g. by determining the node at this position while traversing here, this is just a sample solution.
  201.         try{
  202.             ret += "\nKey at position: "+keyAtPosition();          
  203.         } catch (Exception e){
  204.             System.err.println(e);
  205.         }
  206.         return ret;
  207.     }
  208. }
  209. class Tree{
  210.     TreeNode root;
  211.    
  212.     public Tree(){
  213.         root = null;
  214.     }
  215.    
  216.     public boolean find(int key){
  217.         return (root == null ? false : root.contains(key));
  218.     }
  219.    
  220.     public void insert(int key){
  221.         if(root == null)
  222.             root = new TreeNode(key);
  223.         else
  224.             root.insert(key);
  225.     }
  226.    
  227.     public void printPreOrder(){
  228.         if(root == null)
  229.             System.out.println("[empty tree]");
  230.         else
  231.             root.printPreOrder();
  232.     }
  233.     public void printInOrder(){
  234.         if(root == null)
  235.             System.out.println("[empty tree]");
  236.         else
  237.             root.printInOrder();
  238.     }
  239.     public void printPostOrder(){
  240.         if(root == null)
  241.             System.out.println("[empty tree]");
  242.         else
  243.             root.printPostOrder();
  244.     }
  245.    
  246.     @Override
  247.     public String toString(){
  248.         return (root == null ? "[empty tree]" : root.toString());
  249.     }
  250. }
  251. class TreeNode{
  252.     int key;
  253.     TreeNode left;
  254.     TreeNode right;
  255.    
  256.     public TreeNode(int key){
  257.         this.key = key;
  258.         left = null;
  259.         right = null;
  260.     }
  261.    
  262.     public boolean contains(int key){
  263.         if(key < this.key)
  264.             return (left == null ? false : left.contains(key));
  265.         if(this.key < key)
  266.             return (right == null ? false : right.contains(key));
  267.         return true;
  268.     }
  269.    
  270.     public void insert(int key){
  271.         if(this.key < key){
  272.             if(right == null)
  273.                 right = new TreeNode(key);
  274.             else
  275.                 right.insert(key);
  276.         } else if(key < this.key){
  277.             if(left == null)
  278.                 left = new TreeNode(key);
  279.             else
  280.                 left.insert(key);
  281.         }
  282.     }
  283.    
  284.     public void printPreOrder(){
  285.         System.out.print(" <"+key+"> ");
  286.         if(left != null)
  287.             left.printPreOrder();
  288.         if(right != null)
  289.             right.printPreOrder();
  290.     }
  291.     public void printInOrder(){
  292.         if(left != null)
  293.             left.printInOrder();
  294.         System.out.print(" <"+key+"> ");
  295.         if(right != null)
  296.             right.printInOrder();
  297.     }
  298.     public void printPostOrder(){
  299.         if(left != null)
  300.             left.printPostOrder();
  301.         if(right != null)
  302.             right.printPostOrder();
  303.         System.out.print(" <"+key+"> ");
  304.     }
  305.    
  306.     @Override
  307.     public String toString(){
  308.         return "key: "+key+", left: "+(left == null ? "-" : "("+left.toString()+")") + ", right: "+ (right == null ? "-" : "("+ right.toString() +")");
  309.     }
  310. }
RAW Paste Data
Pastebin PRO Summer Special!
Get 60% OFF on Pastebin PRO accounts!
Top