In this task the aim is to make a simple tree and then traverse it in many diffe
ID: 3775574 • Letter: I
Question
In this task the aim is to make a simple tree and then traverse it in many different ways. The tree consists of nodes, so making the Node class is required. The tree is described by only the root node, while each node is described by the value of the node, the reference to the left and right child. Create the Node class and construct the tree that is displayed above. It is not possible to test if the previous task is done until traversing is implemented Implement In order, Preorder and Post order traversals on the given tree and print the results. Keep in mind that this task is usually done using recursion.Explanation / Answer
public class BinaryTree {
Node root;
public void addNode(int key, String name) {
Node newNode = new Node(key, name);
if (root == null) {
root = newNode;
} else {
Node focusNode = root;
Node parent;
while (true) {
parent = focusNode;
if (key < focusNode.key) {
focusNode = focusNode.leftChild;
if (focusNode == null) {
parent.leftChild = newNode;
return; // All Done
}
} else {
focusNode = focusNode.rightChild;
if (focusNode == null) {
parent.rightChild = newNode;
return; // All Done
}
}
}
}
}
public void inOrderTraverseTree(Node focusNode) {
if (focusNode != null) {
// Traverse the left node
inOrderTraverseTree(focusNode.leftChild);
// Visit the currently focused on node
System.out.println(focusNode);
// Traverse the right node
inOrderTraverseTree(focusNode.rightChild);
}
}
public void preorderTraverseTree(Node focusNode) {
if (focusNode != null) {
System.out.println(focusNode);
preorderTraverseTree(focusNode.leftChild);
preorderTraverseTree(focusNode.rightChild);
}
}
public void postOrderTraverseTree(Node focusNode) {
if (focusNode != null) {
postOrderTraverseTree(focusNode.leftChild);
postOrderTraverseTree(focusNode.rightChild);
System.out.println(focusNode);
}
}
public Node findNode(int key) {
// Start at the top of the tree
Node focusNode = root;
// While we haven't found the Node
// keep looking
while (focusNode.key != key) {
// If we should search to the left
if (key < focusNode.key) {
// Shift the focus Node to the left child
focusNode = focusNode.leftChild;
} else {
// Shift the focus Node to the right child
focusNode = focusNode.rightChild;
}
// The node wasn't found
if (focusNode == null)
return null;
}
return focusNode;
}
public static void main(String[] args) {
BinaryTree theTree = new BinaryTree();
theTree.addNode("2");
theTree.addNode("3");
theTree.addNode("4");
theTree.addNode("5");
theTree.addNode("6");
theTree.addNode("7");
// theTree.inOrderTraverseTree(theTree.root);
// Different ways to traverse binary trees
// theTree.preorderTraverseTree(theTree.root);
// theTree.postOrderTraverseTree(theTree.root);
System.out.println(" Node with the key 1");
System.out.println(theTree.findNode(1));
}
}
class Node {
int key;
String name;
Node leftChild;
Node rightChild;
Node(int key, String name) {
this.key = key;
this.name = name;
}
public String toString() {
return name + " has the key " + key;
/*
* return name + " has the key " + key + " Left Child: " + leftChild +
* " Right Child: " + rightChild + " "
*/
}
}
public class BinaryTree {
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.