What really differentiate Complete Binary Tree from full tree?

As I mentioned on my last blog on Data Structuring, trees have been the center point for most part of Data Composition.

If we mainly reflect back on trees, we find that trees are abstract datatype;which deploy ADT(Abstract Datatype) by imitating their hierarchical structure. These structures are based of the levels that begin from a root value and subtrees of children with a parent node(represented as a set of linked nodes). Under those subtrees, full binary and complete tree do exist to enhance the efficiency of data in trees.

I hope, you have now the taste for full binary and complete tree in trees. Well, let’s dive in to find out more what exactly vary a full binary tree from a complete tree.

In a full binary tree every node has two children except the leaves in the entire tree structure.

However, in a complete binary tree all the nodes in the left side have to be completely filled except the last node in the right side of the tree.

Code Time : Use ordered,in-ordered, and pre-order traversal methods in full and complete tree by adding to find the nodes of the tree.

public class BinaryTree3 {

Node root;

public void addNode(int key, String name) {

// Create a new Node and initialize it

Node newNode = new Node(key, name);

// If there is no root this becomes root

if (root == null) {

root = newNode;

}

else {

// Set root as the Node we will start

// with as we traverse the tree

Node focusNode = root;

// Future parent for our new Node

Node parent;

while (true) {

// root is the top parent so we start

// there

parent = focusNode;

// Check if the new node should go on

// the left side of the parent node

if (key < focusNode.key) {

// Switch focus to the left child

focusNode = focusNode.leftChild;

// If the left child has no children

if (focusNode == null) {

// then place the new node on the left of it

parent.leftChild = newNode;

return; // All Done

}

}

else { // If we get here put the node on the right

focusNode = focusNode.rightChild;

// If the right child has no children

if (focusNode == null) {

// then place the new node on the right of it

parent.rightChild = newNode;

return; // All Done

}

}

}

}

}

// All nodes are visited in ascending order

// Recursion is used to go to one node and

// then go to its child nodes and so forth

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(10, “Boss”);

theTree.addNode(15, “Vice President”);

theTree.addNode(25, “Office Manager”);

theTree.addNode(35, “Secretary”);

theTree.addNode(75, “Sales Manager”);

theTree.addNode(95, “Salesman 1”);

System.out.println(“\nNode with the key 75”);

System.out.println(theTree.findNode(75));

}

}

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;

}

}

#Data Structuring #Trees Full Binary trees #Complete Trees