Want more features on Pastebin? Sign Up, it's FREE!
Guest

Binary Tree and Double Linked List Implementation

By: a guest on Mar 5th, 2014  |  syntax: Java  |  size: 16.80 KB  |  views: 75  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /** Node of a singly linked list of strings. */
  2. class Node
  3. {
  4.     private int data;
  5.     private Node leftNode;
  6.     private Node rightNode;
  7.     private Node nextDataNode;
  8.     private Node prevDataNode;
  9.     private Node parent;
  10.  
  11.     /** Creates a node with the given element and next node. */
  12.     public Node(int input, Node leftNode, Node rightNode, Node nextDataNode, Node prevDataNode)
  13.     {
  14.         data = input;
  15.         this.leftNode = leftNode;
  16.         this.rightNode = rightNode;
  17.         this.nextDataNode = nextDataNode;
  18.         this.prevDataNode = prevDataNode;
  19.         parent = null;
  20.     }
  21.    
  22.     protected Node add (int data, Node head, Node smallestDataNode)
  23.     {
  24.         if (this.contains(data))
  25.         {
  26.             System.out.println("Tree already contains " + data + "; not adding it");
  27.             return smallestDataNode;
  28.         }
  29.         //System.out.println("Adding " + data);
  30.         Node currentNode = this;
  31.         Node tempNode = new Node (data, null, null, null, null);
  32.         while (true)
  33.         {
  34.             if (data < currentNode.getData())
  35.             {
  36.                 if (currentNode.getLeft() == null)
  37.                 {
  38.                     currentNode.setLeft(tempNode);
  39.                     tempNode.setParent(currentNode);
  40.                     break;
  41.                 }
  42.                 else
  43.                 {
  44.                     currentNode = currentNode.getLeft();
  45.                 }
  46.             }
  47.             else
  48.             {
  49.                 if (currentNode.getRight() == null)
  50.                 {
  51.                     currentNode.setRight(tempNode);
  52.                     tempNode.setParent(currentNode);
  53.                     break;
  54.                 }
  55.                 else
  56.                 {
  57.                     currentNode = currentNode.getRight();
  58.                 }
  59.             }
  60.         }
  61.        
  62.         //add it to the double linked list        
  63.         currentNode = smallestDataNode;
  64.        
  65.         if (currentNode.getData() > data)
  66.         {
  67.             //System.out.println("Adding " + data + " between null and " + currentNode.getData());
  68.             currentNode.setPrevDataNode(tempNode);
  69.             tempNode.setNextDataNode(currentNode);
  70.             return tempNode;
  71.         }
  72.         else
  73.         {
  74.             if (currentNode.getNextDataNode() == null)
  75.             {
  76.                 //System.out.println("DLL has one element and adding " + data + " at the end of it between " + currentNode.getData() + " and null");
  77.                 currentNode.setNextDataNode(tempNode);
  78.                 tempNode.setPrevDataNode(currentNode);
  79.             }
  80.             else
  81.             {
  82.                 while (currentNode.getNextDataNode() != null && currentNode.getNextDataNode().getData() < data)
  83.                 {
  84.                     currentNode = currentNode.getNextDataNode();
  85.                 }
  86.                 if (currentNode.getNextDataNode() == null)
  87.                 {
  88.                     //System.out.println("Adding " + data + " at the end, between " + currentNode.getData() + " and null");
  89.                     currentNode.setNextDataNode(tempNode);
  90.                     tempNode.setPrevDataNode(currentNode);
  91.                 }
  92.                 else
  93.                 {
  94.                     //System.out.println("Adding " + data + " between " + currentNode.getPrevDataNode().getData() + " and " + currentNode.getNextDataNode().getData());
  95.                     tempNode.setNextDataNode(currentNode.getNextDataNode());
  96.                     tempNode.setPrevDataNode(currentNode);
  97.                     currentNode.getNextDataNode().setPrevDataNode(tempNode);
  98.                     currentNode.setNextDataNode(tempNode);
  99.                 }
  100.             }
  101.             return smallestDataNode;
  102.         }
  103.     }
  104.    
  105.     //---------------------------</add>
  106.    
  107.    
  108.     protected Node remove(int target, Node currentNode, Node head)
  109.     {
  110.         //System.out.println("Trying to remove " + target + " from node that has data " + currentNode.getData());
  111.  
  112.         if (currentNode.getParent() == null) //it is the root Node
  113.         {
  114.             //System.out.println("Removing the root");
  115.             if (currentNode.isLeaf())
  116.             {
  117.                 return null;
  118.             }
  119.             else if (currentNode.getLeft() == null) //the head node only has a Right branch
  120.             {
  121.                 //System.out.println("  The root only has a Right branch");
  122.                 Node newHead = currentNode.getRight();
  123.                 currentNode.getRight().setParent(null);
  124.                 currentNode.setRight(null);
  125.                 currentNode.removeNodeLinkedList();
  126.                 return newHead;
  127.             }
  128.             else if (currentNode.getRight() == null) //the head node only has a Left branch
  129.             {
  130.                 //System.out.println("  The root only has a Left branch");
  131.                 Node newHead = currentNode.getLeft();
  132.                 currentNode.getLeft().setParent(null);
  133.                 currentNode.setLeft(null);
  134.                 currentNode.removeNodeLinkedList();
  135.                 return newHead;
  136.             }
  137.             else //the head node has two branches
  138.             {
  139.                 //System.out.println("  The root has a two branches");
  140.                 Node newHead = currentNode.getLeft().getRightmostNode();
  141.                 Node oldHead = currentNode;                
  142.                 if (newHead.getLeft() != null)
  143.                 {
  144.                     //System.out.println("    The new root has a left branch");
  145.                     newHead.getLeft().setParent(newHead.getParent());
  146.                     newHead.getParent().setRight(newHead.getLeft());
  147.                     newHead.setLeft(oldHead.getLeft());
  148.                     oldHead.getLeft().setParent(newHead);
  149.                     newHead.setRight(oldHead.getRight());
  150.                     oldHead.getRight().setParent(newHead);
  151.                     newHead.setParent(null);
  152.                     oldHead.setLeft(null);
  153.                     oldHead.setRight(null);
  154.                     oldHead.removeNodeLinkedList();
  155.                     return newHead;
  156.                 }
  157.                 else
  158.                 {
  159.                     //System.out.println("    The new root is a leaf");
  160.                     newHead.getParent().setRight(newHead.getLeft());
  161.                     newHead.setLeft(oldHead.getLeft());
  162.                     oldHead.getLeft().setParent(newHead);
  163.                     oldHead.getRight().setParent(newHead);
  164.                     newHead.setRight(oldHead.getRight());
  165.                     newHead.setParent(null);
  166.                     oldHead.setLeft(null);
  167.                     oldHead.setRight(null);
  168.                     oldHead.removeNodeLinkedList();
  169.                     return newHead;
  170.                 }
  171.             }
  172.         }
  173.         else if (currentNode.isLeaf())
  174.         {
  175.             //System.out.println("It is a leaf");
  176.             if (currentNode.getParent().getLeft() == currentNode) //the Node is the left child
  177.             {
  178.                 //System.out.println("  It is the left child");
  179.                 currentNode.getParent().setLeft(null);
  180.                 currentNode.setParent(null);
  181.                
  182.                 currentNode.removeNodeLinkedList();
  183.             }
  184.             else //it is the right child
  185.             {
  186.                 //System.out.println("  It is the right child");
  187.                 currentNode.getParent().setRight(null);
  188.                 currentNode.setParent(null);
  189.                
  190.                 currentNode.removeNodeLinkedList();
  191.             }
  192.         }
  193.         else if (currentNode.getRight() == null || currentNode.getLeft() == null)
  194.         { //the node that we want to delete has only one branch
  195.             //System.out.println("Node only has one branch");
  196.             if (currentNode.getParent().getLeft() == currentNode) //the Node is the left child
  197.             {
  198.                 //System.out.println("  It is the left child");
  199.                 if (currentNode.getRight() == null) //the node has an empty right side
  200.                 {
  201.                     //System.out.println("    It has an empty right side");
  202.                     currentNode.getParent().setLeft(currentNode.getLeft());
  203.                     currentNode.getLeft().setParent(currentNode.getParent());
  204.                     currentNode.setParent(null);
  205.                    
  206.                     currentNode.removeNodeLinkedList();
  207.                 }
  208.                 else //the node has an empty left side
  209.                 {
  210.                     //System.out.println("    It has an empty left side");
  211.                     currentNode.getParent().setLeft(currentNode.getRight());
  212.                     currentNode.getRight().setParent(currentNode.getParent());
  213.                     currentNode.setParent(null);
  214.                    
  215.                     currentNode.removeNodeLinkedList();
  216.                 }
  217.             }
  218.             else //it is the right child
  219.             {
  220.                 //System.out.println("  It is the right child");
  221.                 if (currentNode.getRight() == null) //the node has an empty right side
  222.                 {
  223.                     //System.out.println("    It has an empty right side");
  224.                     currentNode.getParent().setRight(currentNode.getLeft());
  225.                     currentNode.getLeft().setParent(currentNode.getParent());
  226.                     currentNode.getLeft().setParent(currentNode.getParent());
  227.                     currentNode.setParent(null);
  228.                    
  229.                     currentNode.removeNodeLinkedList();
  230.                 }
  231.                 else //the node has an empty left side
  232.                 {
  233.                     //System.out.println("    It has an empty left side");
  234.                     currentNode.getParent().setRight(currentNode.getRight());
  235.                     currentNode.getRight().setParent(currentNode.getParent());
  236.                     currentNode.getLeft().setParent(currentNode.getParent());
  237.                     currentNode.setParent(null);
  238.                    
  239.                     currentNode.removeNodeLinkedList();
  240.                 }
  241.             }
  242.         }
  243.         else //the node that we want to delete has two branches
  244.         {
  245.             //System.out.println("Node has two branches");
  246.             if (currentNode.getParent().getLeft() == currentNode) //the Node is the left child
  247.             {
  248.                 //System.out.println("  It is the left child");
  249.                 Node movingNode = currentNode.getLeft().getRightmostNode();
  250.                 movingNode.setRight(currentNode.getRight());
  251.                 movingNode.getParent().setRight(movingNode.getLeft());
  252.                 currentNode.setLeft(null);
  253.                 currentNode.removeNodeLinkedList();
  254.                 currentNode.getParent().setLeft(movingNode);
  255.                 movingNode.setParent(currentNode.getParent());
  256.                 currentNode.setParent(null);
  257.             }
  258.             else
  259.             {
  260.                 //System.out.println("  It is the right child");
  261.                 Node movingNode = currentNode.getLeft().getRightmostNode();
  262.                 movingNode.setRight(currentNode.getRight());
  263.                 movingNode.getParent().setRight(movingNode.getLeft());
  264.                 currentNode.setRight(null);
  265.                 currentNode.removeNodeLinkedList();
  266.                 currentNode.getParent().setRight(movingNode);
  267.                 movingNode.setParent(currentNode.getParent());
  268.                 currentNode.setParent(null);
  269.             }
  270.         }
  271.         return head;
  272.     }
  273.  
  274.     //---------------------------</remove>
  275.    
  276.     protected void removeNodeLinkedList()
  277.     {
  278.         //System.out.println("Removing " + this.getData() + " from the DLL");
  279.         if (this.getNextDataNode() == null && this.getPrevDataNode() == null)
  280.         {
  281.             //not needed
  282.         }
  283.         else if (this.getNextDataNode() == null) //it is the tail node
  284.         {
  285.             //System.out.println("It is the tail node with previous data " + this.getPrevDataNode().getData());
  286.             this.getPrevDataNode().setNextDataNode(null);
  287.             this.setPrevDataNode(null);
  288.         }
  289.         else if (this.getPrevDataNode() == null) //it is the head node
  290.         {
  291.             //System.out.println("It is the head node with next data " + this.getNextDataNode().getData());
  292.             this.getNextDataNode().setPrevDataNode(null);
  293.             this.setNextDataNode(null);
  294.         }
  295.         else //it is somewhere in the middle of the LinkedList
  296.         {
  297.             //System.out.println("It is in the middle with prev data " + this.getPrevDataNode().getData() + " and next data " + this.getNextDataNode().getData());
  298.             this.getNextDataNode().setPrevDataNode(this.getPrevDataNode());
  299.             this.getPrevDataNode().setNextDataNode(this.getNextDataNode());
  300.             this.setNextDataNode(null);
  301.             this.setPrevDataNode(null);
  302.         }
  303.     }
  304.    
  305.     protected boolean contains(int data)
  306.     {
  307.         if (this.getData() == data)
  308.             return true;
  309.         else if (this.isLeaf())
  310.             return false;
  311.         else if (this.getData() > data)
  312.         {
  313.             if (this.getLeft() == null)
  314.                 return false;
  315.             return this.getLeft().contains(data);
  316.         }
  317.         else
  318.         {
  319.             if (this.getRight() == null)
  320.                 return false;
  321.             return this.getRight().contains(data);
  322.         }
  323.     }
  324.    
  325.     protected Node getNodeThatHasData(int data)
  326.     {
  327.         if (this.getData() == data)
  328.             return this;
  329.         else if (this.isLeaf())
  330.             return null;
  331.         else if (this.getData() > data)
  332.         {
  333.             if (this.getLeft() == null)
  334.                 return null;
  335.             return this.getLeft().getNodeThatHasData(data);
  336.         }
  337.         else
  338.         {
  339.             if (this.getRight() == null)
  340.                 return null;
  341.             return this.getRight().getNodeThatHasData(data);
  342.         }
  343.     }
  344.    
  345.     protected void inOrder()
  346.     {
  347.         if (this.getLeft() != null)
  348.             this.getLeft().inOrder();
  349.         System.out.print(data + " ");
  350.         if (this.getRight() != null)
  351.             this.getRight().inOrder();
  352.     }
  353.    
  354.     protected void preOrder()
  355.     {
  356.         System.out.print(data + " ");
  357.         if (this.getLeft() != null)
  358.             this.getLeft().preOrder();
  359.         if (this.getRight() != null)
  360.             this.getRight().preOrder();
  361.     }
  362.    
  363.     protected void postOrder()
  364.     {
  365.         if (this.getLeft() != null)
  366.             this.getLeft().postOrder();
  367.         if (this.getRight() != null)
  368.             this.getRight().postOrder();
  369.         System.out.print(data + " ");
  370.     }
  371.    
  372.     public boolean isLeaf() { return (this.getLeft() == null && this.getRight() == null); }
  373.    
  374.     public double getRightmostData()
  375.     {
  376.         if (this.getRight() == null)
  377.             return data;
  378.         else
  379.             return this.getRight().getRightmostData();
  380.     }
  381.    
  382.     public double getLeftmostData()
  383.     {
  384.         if (this.getLeft() == null)
  385.             return data;
  386.         else
  387.             return this.getLeft().getLeftmostData();
  388.     }
  389.    
  390.     public Node getRightmostNode()
  391.     {
  392.         if (this.getRight() == null)
  393.             return this;
  394.         else
  395.             return this.getRight().getRightmostNode();
  396.     }
  397.    
  398.     public Node getLeftmostNode()
  399.     {
  400.         if (this.getLeft() == null)
  401.             return this;
  402.         else
  403.             return this.getLeft().getLeftmostNode();
  404.     }
  405.    
  406.     /** Sets the parent node */
  407.     public void setParent(Node parent) { this.parent = parent; }
  408.     /** Returns the parent node */
  409.     public Node getParent() { return parent; }
  410.    
  411.     /** Returns the element of this node. */
  412.     public int getData() { return data; }
  413.    
  414.     /** Returns the left node of this node. */
  415.     public Node getLeft() { return leftNode; }
  416.     /** Returns the right node of this node. */
  417.     public Node getRight() { return rightNode; }
  418.    
  419.     /** Returns the next highest data node of this node. */
  420.     public Node getNextDataNode() { return nextDataNode; }
  421.     /** Returns the next lower data node of this node. */
  422.     public Node getPrevDataNode() { return prevDataNode; }
  423.    
  424.     /** Sets the element of this node. */
  425.     public void setElement(int newData ) { data = newData; }
  426.    
  427.     /** Sets the left node of this node. */
  428.     public void setLeft(Node newLeft) { leftNode = newLeft; }
  429.     /** Sets the right node of this node. */
  430.     public void setRight(Node newRight) { rightNode = newRight; }
  431.    
  432.     /** Sets the next highest data node of this node. */
  433.     public void setNextDataNode(Node newNext) { nextDataNode = newNext; }
  434.     /** Sets the next lower data node of this node. */
  435.     public void setPrevDataNode(Node newPrev) { prevDataNode = newPrev; }
  436. }
clone this paste RAW Paste Data