Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /** Node of a singly linked list of strings. */
- class Node
- {
- private int data;
- private Node leftNode;
- private Node rightNode;
- private Node nextDataNode;
- private Node prevDataNode;
- private Node parent;
- /** Creates a node with the given element and next node. */
- public Node(int input, Node leftNode, Node rightNode, Node nextDataNode, Node prevDataNode)
- {
- data = input;
- this.leftNode = leftNode;
- this.rightNode = rightNode;
- this.nextDataNode = nextDataNode;
- this.prevDataNode = prevDataNode;
- parent = null;
- }
- protected Node add (int data, Node head, Node smallestDataNode)
- {
- if (this.contains(data))
- {
- System.out.println("Tree already contains " + data + "; not adding it");
- return smallestDataNode;
- }
- //System.out.println("Adding " + data);
- Node currentNode = this;
- Node tempNode = new Node (data, null, null, null, null);
- while (true)
- {
- if (data < currentNode.getData())
- {
- if (currentNode.getLeft() == null)
- {
- currentNode.setLeft(tempNode);
- tempNode.setParent(currentNode);
- break;
- }
- else
- {
- currentNode = currentNode.getLeft();
- }
- }
- else
- {
- if (currentNode.getRight() == null)
- {
- currentNode.setRight(tempNode);
- tempNode.setParent(currentNode);
- break;
- }
- else
- {
- currentNode = currentNode.getRight();
- }
- }
- }
- //add it to the double linked list
- currentNode = smallestDataNode;
- if (currentNode.getData() > data)
- {
- //System.out.println("Adding " + data + " between null and " + currentNode.getData());
- currentNode.setPrevDataNode(tempNode);
- tempNode.setNextDataNode(currentNode);
- return tempNode;
- }
- else
- {
- if (currentNode.getNextDataNode() == null)
- {
- //System.out.println("DLL has one element and adding " + data + " at the end of it between " + currentNode.getData() + " and null");
- currentNode.setNextDataNode(tempNode);
- tempNode.setPrevDataNode(currentNode);
- }
- else
- {
- while (currentNode.getNextDataNode() != null && currentNode.getNextDataNode().getData() < data)
- {
- currentNode = currentNode.getNextDataNode();
- }
- if (currentNode.getNextDataNode() == null)
- {
- //System.out.println("Adding " + data + " at the end, between " + currentNode.getData() + " and null");
- currentNode.setNextDataNode(tempNode);
- tempNode.setPrevDataNode(currentNode);
- }
- else
- {
- //System.out.println("Adding " + data + " between " + currentNode.getPrevDataNode().getData() + " and " + currentNode.getNextDataNode().getData());
- tempNode.setNextDataNode(currentNode.getNextDataNode());
- tempNode.setPrevDataNode(currentNode);
- currentNode.getNextDataNode().setPrevDataNode(tempNode);
- currentNode.setNextDataNode(tempNode);
- }
- }
- return smallestDataNode;
- }
- }
- //---------------------------</add>
- protected Node remove(int target, Node currentNode, Node head)
- {
- //System.out.println("Trying to remove " + target + " from node that has data " + currentNode.getData());
- if (currentNode.getParent() == null) //it is the root Node
- {
- //System.out.println("Removing the root");
- if (currentNode.isLeaf())
- {
- return null;
- }
- else if (currentNode.getLeft() == null) //the head node only has a Right branch
- {
- //System.out.println(" The root only has a Right branch");
- Node newHead = currentNode.getRight();
- currentNode.getRight().setParent(null);
- currentNode.setRight(null);
- currentNode.removeNodeLinkedList();
- return newHead;
- }
- else if (currentNode.getRight() == null) //the head node only has a Left branch
- {
- //System.out.println(" The root only has a Left branch");
- Node newHead = currentNode.getLeft();
- currentNode.getLeft().setParent(null);
- currentNode.setLeft(null);
- currentNode.removeNodeLinkedList();
- return newHead;
- }
- else //the head node has two branches
- {
- //System.out.println(" The root has a two branches");
- Node newHead = currentNode.getLeft().getRightmostNode();
- Node oldHead = currentNode;
- if (newHead.getLeft() != null)
- {
- //System.out.println(" The new root has a left branch");
- newHead.getLeft().setParent(newHead.getParent());
- newHead.getParent().setRight(newHead.getLeft());
- newHead.setLeft(oldHead.getLeft());
- oldHead.getLeft().setParent(newHead);
- newHead.setRight(oldHead.getRight());
- oldHead.getRight().setParent(newHead);
- newHead.setParent(null);
- oldHead.setLeft(null);
- oldHead.setRight(null);
- oldHead.removeNodeLinkedList();
- return newHead;
- }
- else
- {
- //System.out.println(" The new root is a leaf");
- newHead.getParent().setRight(newHead.getLeft());
- newHead.setLeft(oldHead.getLeft());
- oldHead.getLeft().setParent(newHead);
- oldHead.getRight().setParent(newHead);
- newHead.setRight(oldHead.getRight());
- newHead.setParent(null);
- oldHead.setLeft(null);
- oldHead.setRight(null);
- oldHead.removeNodeLinkedList();
- return newHead;
- }
- }
- }
- else if (currentNode.isLeaf())
- {
- //System.out.println("It is a leaf");
- if (currentNode.getParent().getLeft() == currentNode) //the Node is the left child
- {
- //System.out.println(" It is the left child");
- currentNode.getParent().setLeft(null);
- currentNode.setParent(null);
- currentNode.removeNodeLinkedList();
- }
- else //it is the right child
- {
- //System.out.println(" It is the right child");
- currentNode.getParent().setRight(null);
- currentNode.setParent(null);
- currentNode.removeNodeLinkedList();
- }
- }
- else if (currentNode.getRight() == null || currentNode.getLeft() == null)
- { //the node that we want to delete has only one branch
- //System.out.println("Node only has one branch");
- if (currentNode.getParent().getLeft() == currentNode) //the Node is the left child
- {
- //System.out.println(" It is the left child");
- if (currentNode.getRight() == null) //the node has an empty right side
- {
- //System.out.println(" It has an empty right side");
- currentNode.getParent().setLeft(currentNode.getLeft());
- currentNode.getLeft().setParent(currentNode.getParent());
- currentNode.setParent(null);
- currentNode.removeNodeLinkedList();
- }
- else //the node has an empty left side
- {
- //System.out.println(" It has an empty left side");
- currentNode.getParent().setLeft(currentNode.getRight());
- currentNode.getRight().setParent(currentNode.getParent());
- currentNode.setParent(null);
- currentNode.removeNodeLinkedList();
- }
- }
- else //it is the right child
- {
- //System.out.println(" It is the right child");
- if (currentNode.getRight() == null) //the node has an empty right side
- {
- //System.out.println(" It has an empty right side");
- currentNode.getParent().setRight(currentNode.getLeft());
- currentNode.getLeft().setParent(currentNode.getParent());
- currentNode.getLeft().setParent(currentNode.getParent());
- currentNode.setParent(null);
- currentNode.removeNodeLinkedList();
- }
- else //the node has an empty left side
- {
- //System.out.println(" It has an empty left side");
- currentNode.getParent().setRight(currentNode.getRight());
- currentNode.getRight().setParent(currentNode.getParent());
- currentNode.getLeft().setParent(currentNode.getParent());
- currentNode.setParent(null);
- currentNode.removeNodeLinkedList();
- }
- }
- }
- else //the node that we want to delete has two branches
- {
- //System.out.println("Node has two branches");
- if (currentNode.getParent().getLeft() == currentNode) //the Node is the left child
- {
- //System.out.println(" It is the left child");
- Node movingNode = currentNode.getLeft().getRightmostNode();
- movingNode.setRight(currentNode.getRight());
- movingNode.getParent().setRight(movingNode.getLeft());
- currentNode.setLeft(null);
- currentNode.removeNodeLinkedList();
- currentNode.getParent().setLeft(movingNode);
- movingNode.setParent(currentNode.getParent());
- currentNode.setParent(null);
- }
- else
- {
- //System.out.println(" It is the right child");
- Node movingNode = currentNode.getLeft().getRightmostNode();
- movingNode.setRight(currentNode.getRight());
- movingNode.getParent().setRight(movingNode.getLeft());
- currentNode.setRight(null);
- currentNode.removeNodeLinkedList();
- currentNode.getParent().setRight(movingNode);
- movingNode.setParent(currentNode.getParent());
- currentNode.setParent(null);
- }
- }
- return head;
- }
- //---------------------------</remove>
- protected void removeNodeLinkedList()
- {
- //System.out.println("Removing " + this.getData() + " from the DLL");
- if (this.getNextDataNode() == null && this.getPrevDataNode() == null)
- {
- //not needed
- }
- else if (this.getNextDataNode() == null) //it is the tail node
- {
- //System.out.println("It is the tail node with previous data " + this.getPrevDataNode().getData());
- this.getPrevDataNode().setNextDataNode(null);
- this.setPrevDataNode(null);
- }
- else if (this.getPrevDataNode() == null) //it is the head node
- {
- //System.out.println("It is the head node with next data " + this.getNextDataNode().getData());
- this.getNextDataNode().setPrevDataNode(null);
- this.setNextDataNode(null);
- }
- else //it is somewhere in the middle of the LinkedList
- {
- //System.out.println("It is in the middle with prev data " + this.getPrevDataNode().getData() + " and next data " + this.getNextDataNode().getData());
- this.getNextDataNode().setPrevDataNode(this.getPrevDataNode());
- this.getPrevDataNode().setNextDataNode(this.getNextDataNode());
- this.setNextDataNode(null);
- this.setPrevDataNode(null);
- }
- }
- protected boolean contains(int data)
- {
- if (this.getData() == data)
- return true;
- else if (this.isLeaf())
- return false;
- else if (this.getData() > data)
- {
- if (this.getLeft() == null)
- return false;
- return this.getLeft().contains(data);
- }
- else
- {
- if (this.getRight() == null)
- return false;
- return this.getRight().contains(data);
- }
- }
- protected Node getNodeThatHasData(int data)
- {
- if (this.getData() == data)
- return this;
- else if (this.isLeaf())
- return null;
- else if (this.getData() > data)
- {
- if (this.getLeft() == null)
- return null;
- return this.getLeft().getNodeThatHasData(data);
- }
- else
- {
- if (this.getRight() == null)
- return null;
- return this.getRight().getNodeThatHasData(data);
- }
- }
- protected void inOrder()
- {
- if (this.getLeft() != null)
- this.getLeft().inOrder();
- System.out.print(data + " ");
- if (this.getRight() != null)
- this.getRight().inOrder();
- }
- protected void preOrder()
- {
- System.out.print(data + " ");
- if (this.getLeft() != null)
- this.getLeft().preOrder();
- if (this.getRight() != null)
- this.getRight().preOrder();
- }
- protected void postOrder()
- {
- if (this.getLeft() != null)
- this.getLeft().postOrder();
- if (this.getRight() != null)
- this.getRight().postOrder();
- System.out.print(data + " ");
- }
- public boolean isLeaf() { return (this.getLeft() == null && this.getRight() == null); }
- public double getRightmostData()
- {
- if (this.getRight() == null)
- return data;
- else
- return this.getRight().getRightmostData();
- }
- public double getLeftmostData()
- {
- if (this.getLeft() == null)
- return data;
- else
- return this.getLeft().getLeftmostData();
- }
- public Node getRightmostNode()
- {
- if (this.getRight() == null)
- return this;
- else
- return this.getRight().getRightmostNode();
- }
- public Node getLeftmostNode()
- {
- if (this.getLeft() == null)
- return this;
- else
- return this.getLeft().getLeftmostNode();
- }
- /** Sets the parent node */
- public void setParent(Node parent) { this.parent = parent; }
- /** Returns the parent node */
- public Node getParent() { return parent; }
- /** Returns the element of this node. */
- public int getData() { return data; }
- /** Returns the left node of this node. */
- public Node getLeft() { return leftNode; }
- /** Returns the right node of this node. */
- public Node getRight() { return rightNode; }
- /** Returns the next highest data node of this node. */
- public Node getNextDataNode() { return nextDataNode; }
- /** Returns the next lower data node of this node. */
- public Node getPrevDataNode() { return prevDataNode; }
- /** Sets the element of this node. */
- public void setElement(int newData ) { data = newData; }
- /** Sets the left node of this node. */
- public void setLeft(Node newLeft) { leftNode = newLeft; }
- /** Sets the right node of this node. */
- public void setRight(Node newRight) { rightNode = newRight; }
- /** Sets the next highest data node of this node. */
- public void setNextDataNode(Node newNext) { nextDataNode = newNext; }
- /** Sets the next lower data node of this node. */
- public void setPrevDataNode(Node newPrev) { prevDataNode = newPrev; }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement