Basic traversal on tree is best explained on http://en.wikipedia.org/wiki/Tree_traversal .
In Order:
Pre Order:
Post Order:
If anything is missing in explanation, you can google it and I know you all are expert as me.
Now my part starts from here.
How to implement it in java.
Project Structure in Eclipse:
Node.java (nodeInfo variable has no logical meaning, it is just for printing purpose)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
package datastructure.tree; public class Node { private Node leftNode; private Node rightNode; private int nodeValue; private String nodeInfo; public Node(String nodeInfo,int nodeValue){ this.nodeInfo = nodeInfo; this.nodeValue = nodeValue; } public Node getLeftNode() { return leftNode; } public void setLeftNode(Node leftNode) { this.leftNode = leftNode; } public Node getRightNode() { return rightNode; } public void setRightNode(Node rightNode) { this.rightNode = rightNode; } public int getNodeValue() { return nodeValue; } public void setNodeValue(int nodeValue) { this.nodeValue = nodeValue; } public String getNodeInfo() { return nodeInfo; } public void setNodeInfo(String nodeInfo) { this.nodeInfo = nodeInfo; } } |
Tree.java
|
1 2 3 4 5 6 7 8 9 10 11 12 |
package datastructure.tree; public interface Tree { void insertNode(Node node); void deleteNode(Node node); Node searchNode(Node node); void inOrderTraversal(Node node); void preOrderTraversal(Node node); void postOrderTraversal(Node node); } |
TreeImpl.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 |
package datastructure.tree; public class TreeImpl implements Tree{ int tree_node_count = 0; public Node rootNode = null; public Node getRootNode() { return rootNode; } public void setRootNode(Node rootNode) { this.rootNode = rootNode; } public TreeImpl(Node rootNode){ this.rootNode = rootNode; tree_node_count = 1; } @Override public void insertNode(Node node){ Node treeNode = rootNode; while(true){ if(node.getNodeValue()<treeNode.getNodeValue()){ if(treeNode.getLeftNode()!=null){ treeNode = treeNode.getLeftNode(); }else{ treeNode.setLeftNode(node); System.out.println("Node "+node.getNodeValue()+" saved at left child of node :"+treeNode.getNodeValue()); break; } }else if(node.getNodeValue()>treeNode.getNodeValue()){ if(treeNode.getRightNode()!=null){ treeNode = treeNode.getRightNode(); }else{ treeNode.setRightNode(node); System.out.println("Node "+node.getNodeValue()+" saved at Right child of node :"+treeNode.getNodeValue()); break; } }else{ System.out.println("Duplicate Node can not be saved"); break; } } } @Override public Node searchNode(Node node){ Node currentNode = rootNode; while(currentNode!=null){ if(currentNode.getNodeValue()==node.getNodeValue()){ System.out.println("Node "+node.getNodeValue()+" Found"); return currentNode; }else{ if(node.getNodeValue()<currentNode.getNodeValue()){ currentNode = currentNode.getLeftNode(); }else{ currentNode = currentNode.getRightNode(); } } } System.out.println("Node "+node.getNodeValue()+" Not Found"); return null; } @Override public void deleteNode(Node node) { Node previousNode = null; Node currentNode = rootNode; if(node.getNodeValue()==currentNode.getNodeValue()){ System.out.println("Your Tree is Vanished"); }else if(node.getNodeValue()<currentNode.getNodeValue()){ previousNode = currentNode; currentNode = currentNode.getLeftNode(); }else{ previousNode = currentNode; currentNode = currentNode.getRightNode(); } while(true){ if(node.getNodeValue()==currentNode.getNodeValue()){ if(currentNode.getRightNode()!=null){ Node tempPreviousNode = currentNode; Node tempNode = currentNode.getRightNode(); if(tempNode.getLeftNode()!=null){ while(tempNode.getLeftNode()!=null){ tempPreviousNode = tempNode; tempNode = tempNode.getLeftNode(); } if(tempNode.getRightNode()!=null){ tempPreviousNode.setLeftNode(tempNode.getRightNode()); previousNode.setRightNode(tempNode); tempNode.setLeftNode(currentNode.getLeftNode()); break; }else{ tempNode.setLeftNode(currentNode.getLeftNode()); tempNode.setRightNode(currentNode.getRightNode()); previousNode.setRightNode(tempNode); tempPreviousNode.setLeftNode(null); break; } }else{ tempNode.setLeftNode(currentNode.getLeftNode()); previousNode.setRightNode(tempNode); break; } }else if(currentNode.getLeftNode()!=null){ previousNode.setLeftNode(currentNode.getLeftNode()); currentNode = null; break; }else{ currentNode = null; break; } }else if(node.getNodeValue()<currentNode.getNodeValue()){ previousNode = currentNode; currentNode = currentNode.getLeftNode(); }else{ previousNode = currentNode; currentNode = currentNode.getRightNode(); } } } @Override public void inOrderTraversal(Node node) { if(node!=null){ inOrderTraversal(node.getLeftNode()); System.out.println("Node Value:"+node.getNodeValue()); inOrderTraversal(node.getRightNode()); } } @Override public void preOrderTraversal(Node node) { // TODO Auto-generated method stub if(node!=null){ System.out.println("Node Value:"+node.getNodeValue()); preOrderTraversal(node.getLeftNode()); preOrderTraversal(node.getRightNode()); } } @Override public void postOrderTraversal(Node node) { // TODO Auto-generated method stub if(node!=null){ postOrderTraversal(node.getLeftNode()); postOrderTraversal(node.getRightNode()); System.out.println("Node Value:"+node.getNodeValue()); } } } |
MainPractise,java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
import datastructure.tree.Node; import datastructure.tree.TreeImpl; public class MainPractise implements Cloneable{ public static void main(String[] args) { Node node = new Node("Root Node",12); TreeImpl ti = new TreeImpl(node); Node leafNode = new Node("Leaf Node",5); ti.insertNode(leafNode); leafNode = new Node("Leaf Node",16); ti.insertNode(leafNode); leafNode = new Node("Leaf Node",2); ti.insertNode(leafNode); leafNode = new Node("Leaf Node",1); ti.insertNode(leafNode); leafNode = new Node("Leaf Node",3); ti.insertNode(leafNode); leafNode = new Node("Leaf Node",15); ti.insertNode(leafNode); leafNode = new Node("Leaf Node",19); ti.insertNode(leafNode); leafNode = new Node("Leaf Node",18); ti.insertNode(leafNode); Node deleteNode = new Node("Leaf Node",16); ti.deleteNode(deleteNode); System.out.println("==============In Order Traversal==================="); ti.inOrderTraversal(ti.getRootNode()); System.out.println("==============Pre Order Traversal=================="); ti.preOrderTraversal(ti.getRootNode()); System.out.println("==============Post Order Traversal================="); ti.postOrderTraversal(ti.getRootNode()); System.out.println("==================================================="); Node searchNode = new Node("Leaf Node", 17); ti.searchNode(searchNode); searchNode = new Node("Leaf Node", 3); ti.searchNode(searchNode); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
Node 5 saved at left child of node :12 Node 16 saved at Right child of node :12 Node 2 saved at left child of node :5 Node 1 saved at left child of node :2 Node 3 saved at Right child of node :2 Node 15 saved at left child of node :16 Node 19 saved at Right child of node :16 Node 18 saved at left child of node :19 ==============In Order Traversal=================== Node Value:1 Node Value:2 Node Value:3 Node Value:5 Node Value:12 Node Value:15 Node Value:18 Node Value:19 ==============Pre Order Traversal================== Node Value:12 Node Value:5 Node Value:2 Node Value:1 Node Value:3 Node Value:18 Node Value:15 Node Value:19 ==============Post Order Traversal================= Node Value:1 Node Value:3 Node Value:2 Node Value:5 Node Value:15 Node Value:19 Node Value:18 Node Value:12 =================================================== Node 17 Not Found Node 3 Found |
I haven’t defined any methods of isEmpty() and as such methods. So if you need one let me know.
You can have above code from GIT.
https://github.com/Niravkumar-Patel/SnippetExampleRepo.git