Blog

Posted on by

Data-structure – Ordered Tree vs Unordered Tree

Posted on by

A binary tree can be ordered or an unordered tree, so what is the difference between these two trees. In this lesson, you will compare the ordered tree vs. unordered tree and tell the difference.

Ordered Tree Example

The name suggests that the ordered tree must be an organized tree in which nodes are in some order. What is the common ordering method?

In the figure above, for any node, its left child has less value than the node itself and the right child has a value greater than the node.

Unordered Tree

In a binary tree, when nodes are not in a particular order it is called a unordered tree.

See the root, all the left descendants of the root are less than the root value and all right descendant has a value greater than the root.

Unordered Tree - ordered tree vs. unordered tree — Unordered Tree

This is the primary difference between the ordered tree vs. unordered tree.

References

R.G.Dromey. 2008. How to Solve it by Computer. Pearson Education India.

Robert Kruse, Cl Tondo. n.d. Data Structures and Program Design in C. Pearson Education India.

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.

Data Structure – Binary Tree Concepts

Posted on by

A binary tree is a special kind of tree and important in computer science. There is plenty of real-world application of binary trees. The scope of this lesson is limited to the learning the binary tree concepts.

Learn Tree Basics

Informal definition

A tree is called a binary tree if it has the following properties.

It is an empty tree with no nodes.
The tree has a root node, left sub-tree and right sub-tree.
The sub-trees are binary tree themselves.

Strictly Binary Tree

Suppose there is a binary tree with right sub-tree and left sub-tree. The sub-trees are in turn non-empty, then such a binary tree is called a strictly binary tree.

In the above figure, one is a strictly binary tree and the second tree is not a strictly binary tree, but it is certainly a binary tree and satisfy all the properties of a binary tree.

Complete Binary Tree

A complete binary tree has a level L and all its leaf nodes are available at level L. At each level the complete binary tree contains 2^Lnodes.

Let us show this with an example,

Complete Binary Tree - Binary Tree Concepts — Complete Binary Tree – Binary Tree Concepts

The root is at level 0, therefore, L = 0 and 2^L = 2^0 = 1.

Conversion of a Binary Forest into a Binary Tree

Suppose we have a forest with two trees as follows,

Forest with Two Trees - binary tree concepts — Forest with Two Trees

\begin{aligned} &T1 = { 1,2,3,4,5,6}\\ &T2 = { 7,8,9,10,11,12} \end{aligned}

The figure below show the two separate trees in the forest.

The first step is to order the nodes of both trees using following formula.

If a node has left child, then if comes immediately below the node.
If a node has another node in the save level, then it becomes the right child of the node.
If a node has right child then, ignore it.

Such a representation of two trees is given below.

Forest with Two Ordered Trees - binary tree concepts — Forest with Two Ordered Trees

Your next step should be to join these two tree into one by connecting their roots. This is because the roots of the trees are at the same level. See the figure below

Forest with Two Ordered Trees Joined - Binary tree concepts — Forest with Two Ordered Trees Joined

The new tree is a binary tree, the node at the save level in above diagram becomes the right child. The final tree structure look like the one in figure below.

Final Joined Binary Tree - Binary Tree Concepts — Final Joined Binary Tree

Total Number of Edges

In a complete binary tree, the total number of edges is given by the formula,

\begin{aligned} 2 (N_L - 1)\hspace{1ex} where \hspace{1ex}N_L\hspace{1ex} is \hspace{1ex}total\hspace{1ex} number \hspace{1ex}of\hspace{1ex} leaf \hspace{1ex}nodes. \end{aligned}

For example, see the tree below.

Complete Binary Tree with Edge Labelled -Binary Tree Concepts — Complete Binary Tree with Edge Labelled

In the above diagram, we have $N_L = 8$ .

Therefore,

\begin{aligned} &= 2( N_L - 1) \\ &= 2 ( 8 - 1) \\ &= 2 (7) \\ &= 14\hspace{1ex} edges. \end{aligned}

Height of a Binary Tree

The maximum level of any node of the binary tree is called the height of a binary tree.

For example, see the figure below.

Height Of The Tree - Binary Tree Concepts — Height Of The Tree

In the above tree figure, the maximum level of the tree is $4$ ,

Therefore, the height of the tree is $Height(T) = 4$ .

References

R.G.Dromey. 2008. How to Solve it by Computer. Pearson Education India.

Robert Kruse, Cl Tondo. n.d. Data Structures and Program Design in C. Pearson Education India.

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.

Data Structure – Tree Basics

Posted on by

A tree is a non-linear data structure. It means you cannot access an element of a tree in a straightforward manner. In this lesson, you learn about tree basics.

This will serve as a foundation for future topics on trees. You can start learning about other topics if familiar with the basics.

Informal definition of Tree

A tree is a set of one or more nodes with a special node called a Root node. Every none points to a left node and a right node. Sometimes left, right or both are missing and a node points to nothing.

Every node is part of some smaller set of nodes called a Sub-tree. Each sub-tree has more sub-trees.

Tree basics – Directed vs Undirected Tree

In an undirected tree, the edge between two nodes has no direction associated with it. However, a directed tree has some important properties.

The directed tree is acyclic means there is loop between the nodes.
The directed tree is digraph means it is like a graph with direction. Each node has associated edges. If the node pointed by some other node, it is called an In-degree and if the node is pointing to some other node, its called an Out-degree.
Root node has in-degree 0 and all other nodes have in-degree of 1.
The minimum number of nodes allowed in a directed tree is 1. So, an isolated node is a directed tree.

A Directed Tree - Tree Basics — A Directed Tree with Root, Branch and Leaf Nodes

Leaf Nodes

In a directed tree with nodes that has an out-degree of 0 is called a Leaf node or Terminal node.

In the above figure, 5, 6, 7, 8, 9 are leaf nodes.

Branch Nodes

In a directed tree with all nodes other than root and leaf nodes are called Branch nodes. For example,

In the above figure, 2, 3 and 4 are branch nodes.

Level of a Tree

Suppose you want to reach the node 8 from root node 1, then starting from root node, we go through following path

1 –> 4 –> 8

So, the level of any node is length of its path from the root node. The level of root node is 0 and level of node 8 is 2.

Tree basics – Ordered Tree

Sometimes the directed tree is ordered, that is, at each level the order is specified, and this type of tree is called an Ordered tree.

Tree A and Tree B - Tree Basics — Tree A and Tree B

In the above figure, the Tree A and Tree B are the same tree but ordered differently.

Node degree

The node degree corresponds to number of children of the node. The node 3,4,and 6 in tree A are leaf nodes and has a degree of 0 because it not a parent of any other node.

The node 2 from tree B has a degree of 2 because node 4 and node 3 are its children.

The Concept of Forest

If we delete root node and its edges from tree A or tree B, we will get two separate trees. This particular set of trees is known as a Forest.

For example, we get the following forest after deleting the root. These forest can be represented as sets.They are the same sets.

Forest A ={ (2,3,4),( 5,6)} Forest B = {(5,6),(2,3,4)}

Descendant and Children of a Node

There is a node called S and it is reachable from node N means there is a path from N to S. Then an such node S is called a Descendant of a node N.

Suppose a node S reachable by a single edge E from node N is called a Child of node N and the node N is a Parent of child node S.

For example, In Tree A

The node 2 and node 5 are children of node 1

The node 3 and node 4 are not children, but descendant of node 1.

Note: We will be using this tree basics terminology in all future lessons. Make yourselves familiar with the concepts.

References

E.Balaguruswamy. 2013. Data Structures Using C. McGraw Hill Education.

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.

Java Program to Compute Average Mark of Students

Posted on by

The program answers how to compute average mark of student. It reads a student’s mark in each subject and then compute the average and displays the results.

First, you will store the student records and second, take the average of the marks obtained in different subjects. This is a simple program that demonstrates the use of arithmetic expressions in a java program. The java program to calculate student marks is intended for beginners of java programming.

A flowchart, program code and a verified output is given to help you learn and practice the program. The program is written using NetBeans 8.2 with Java SDK 8u111.

Problem Definition

The program for computing average mark of students ask for student’s name, roll number and marks in two subjects – sub1 and sub2 using get() function. We have used only two subjects for the program, but you can always change the number of the subject suitable to you.

This will not break the program logic and still calculate average.

Next, the program computes the total marks and divide it with the number of subjects taken by the student.

This will give the average mark obtained by the student. To compute the average use following

Average mark = Total marks all subjects/Total subjects

Finally, the program displays the results using function – disp().

Flowchart – Average Mark of Students

Program Code – Average Mark of Student

/* * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates 
 * and open the template in the editor. */ 

package JavaExamples;

 /** * * @author Admin */ 

class Student{ 

    int rollno; 
    String name; 
    int sub1; 
    int sub2; 
    int Avg; 
    void get(String n, int r, int a, int b) { 
        rollno = r; 
        name = n; 
        sub1 = a; 
        sub2 = b; 
} 

void disp() { 
    Avg = (sub1 + sub2)/2; 
    System.out.println("Rollno=" + rollno); 
    System.out.println("Name=" + name); 
    System.out.println("Sub1=" + sub1); 
    System.out.println("Sub2=" + sub2); 
    System.out.println("Average=" + Avg); 
    } 
} 

public class StudentMarkAvg { 
    public static void main(String[] args){ 
        Student s1 = new Student(); 
        Student s2 = new Student(); 
        Student s3 = new Student(); 
        s1.get("Ram",16345,21,78); 
        s2.get("Judith", 26312, 77,91);
 
        s3.get("Lee", 32132, 85, 65); 
        s1.disp(); 
        s2.disp(); 
        s3.disp(); 
     } 
}

Output – Average Mark

The output of the program compute average mark of student in NetBeans 8.2 is given below. It displays the student details and the average mark in two subjects.

Rollno=16345 

Name=Ram 

Sub1=21 

Sub2=78 

Average=49 

------------------------------ 

Rollno=26312 

Name=Judith 

Sub1=77 

Sub2=91 

Average=84 

------------------------------ 

Rollno=32132 

Name=Wong 

Sub1=85 

Sub2=65 

Average=75 

------------------------------

Java Program to Demo Built-in String Functions

Posted on by

In java programming there are many built-in string manipulation functions.These functions belong to java.lang packages. The Java program to demo built in function use of each commonly used string function .More details about string class will be discussed in our Java Programming Tutorial.

The program is written using NetBean 8.2 and you may also need to install the suitable Java SDK version for NetBean IDE. The operating system platform is Windows 7 64-bit system. The program is a very simple one and intended for beginners of Java programming.

Problem Definition

The program reads 3 string variables and then perform following operations on them.

Find the length of the string using length () function.
Convert the string into uppercase and lowercase using toUpperCase () and toLowerCase () functions respectively.
Concatenate two strings using concat () function.

Flowchart

Program Code

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package JavaExamples;

/**
*
* @author Admin
*/
public class StringDemo {

    public static void main(String[] args) {

        int x, y;

        String S = "Elephant";

        String S1 = "Tiger";

        String S3 = "Hello";

        x = S.length();
        y = S1.length();
    
        System.out.println("Length of S=" + x);
        System.out.println("Length of S1=" + y);
    
        System.out.println(S.toUpperCase());
        System.out.println(S.toLowerCase());

        String S2 = S + S1;

        System.out.println("S2=" + S2);

        String S4 = S3.concat(S1);

        System.out.println(S4);
    }

}

Output

The output of the program is given below. It show the various forms of string variable – uppercase, lowercase, concatenated strings and length of strings.

Length of S=8

Length of S1=5

ELEPHANT

elephant

S2 = ElephantTiger

HelloTiger

Related Articles:-

C++ Program for Factorial without Recursion

Posted on by

Factorial of a number is the number you get by multiplying all the numbers up to that number including the number itself. The program for factorial does not use a programming technique called a recursion. a recursion happens when a function calls itself until the problem is solved.

This program is a simple computation of factorial value, hence, it is suitable for beginner learners of C++ programming. I have written this using Dev-C++ compiler version 4.9.9.2 installed on a windows 7 64-bit system.

Problem Definition

The program requires user input – a positive integer value and computes the factorial of than number.

For example,

Suppose you entered number 6 , then the factorial of this number would be

1 x 2 x 3 x 4 x 5 x 6 = 720

In mathematical terms, if n is a positive integer value, the factorial of n is denoted by n! You can go through the flowchart to understand the logic of factorial applied in this program.

Flowchart – Factorial without Recursion

Program Code – Factorial without Recursion


// Program to compute factorial of n numbers

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>

int main()
{

    int fact,i;

    int n;

//Read the value of N

    cout << "Enter value of N:" ; cin >> n;

//Initialize Factorial to 1 and i to 1

    fact = 1;

    i = 1;

    while(i<=n)
    {

        fact = fact * i;

        i++;

    }

// Print the value of factorial

    for(i=0;i < 30;i++)
    cout << "_";cout << "\n\n";

    cout << "Factorial of N:" << "\t" << fact << endl;

    for(i=0;i << 30;i++)
    cout << "_";cout << "\n\n";

    system("PAUSE");

    return 0;

}

Output

Basic JavaScript – Exercise 06 -Conditional Statements

Posted on by

Conditional statements in JavaScript uses if-else or switch statement that change the direction of the program in run-time. The conditional statement check certain conditions and then based on the truth value of the condition, execute a block of code.

The if-else statements could be nested to make a if-if-else-else or if-else- else-if statements. The general structure of if-else statement is as follows

if (condition) 
{     
   statement 1... 
} 
else 
{     
   statement 2... 
}

In the above example, if the condition is true – statement 1 is executed, else – the statement 2 is executed. In this article, you will create a JavaScript file with conditional statement called cond.js and then create an HTML page called ex06.html. Keep both in the same directory called Exercise 06.

Conditional Statements in a JavaScript File

You need to create an external JavaScript file called cond.js in a directory called Exercise 06.

The steps to create the JavaScript with conditional statements is given below.

Step 1: Open a new notepad and save it as cond.txt.

Step 2: Open the cond.txt file and insert the following code.

var a = 10 
var b = 100 
var c = a + b 
if(c > 100) 
{ 
    document.write("a = 10" + ""); 
    document.write("b = 100"+ ""); 
    document.write("c= a + b"+ ""); 
    document.write(" " + "C is more than 100" + " "); 
} 
else 
{ 
    document.write("a = 10"+ ""); 
    document.write("b = 100"+ ""); 
    document.write("c= a + b"+ ""); 
    document.write( " " + "C is less than 100" + " "); 
}

Step 3: Save the file as cond.js and close the file.

Figure2-cond.js

HTML Page

Now, you will create a new HTML page called ex06.html and link the cond.js file to the HTML page. To create the HTML page follow the steps below.

Step 1: Open a note pad and save it as ex06.txt.

Step 2: Open the ex06.txt file and insert the following code.

<html>
<head>
<title>
    Basic JavaScript - Exercise-06 - Conditional Statements 
</title>
    <script type="text/javascript" src="cond.js"></script>
</head>
<body>
    <p>Example of Conditional Statement </p>
</body>
</html>

Step 3: Save the ex06.txt file to ex06.html and close it.

Figure2-ex06 - Conditional statements in JavaScript — Figure2-ex06 – Conditional statements in JavaScript

Output

The program read have two variables A = 10, B = 100. There sum is C = A + B . If C is greater then 100 , following output is displayed on the screen, else a different output will be printed. All depends on the condition whether C > 100.

C Program to Implement Stack using Linked-List

Posted on by

A stack is an abstract data structure where elements are pushed and deleted from only one end. We call this top of a stack.

This program implement stack using a linked-list structure. The linked-list is a linear list in which you can enter data only from one end. You must always insert from the front of the linked list so that it works like a stack.

The basic stack operations are given below.

Push()
Pop()

The Push () function insert an item into the stack and Pop () deletes the item from top of the stack. In the figure below, items are added to top and deleted from top. This is called Last In, First Out mechanism.

Problem Definition

A stack can be implemented using array data structure or a dynamically growing linked-list data structures. The linked-list implementation of stack does not need to check for “stack being full” because the list grows dynamically.

A linked-list has nodes that are linked together using pointers. A linked-list node has a data and a link pointer of type node that points to the next node element in the list.

An example of a node

struct node {

 int data;

 node* next;

};

Steps to build a linked-list based stack is as follows

Step 1: Declare pointers to build initial stack.

 struct node *head, *temp;

The *head pointer of type struct points to the first node of the linked-list and the *temp pointer of type struct points to any new node you create. The pointers are created but does not point to anything. You must point to some variable or allocate memory to initialize them.

Step 2: Initialize the head node.

In C programming language, you must initialize any pointer by dynamically allocating memory using function malloc (). You initialize pointer head as follows

head =(struct node* )malloc( ( struct node))

Now that have assigned memory to the head node, give values to its variables.

head->data=10;
head->next =NULL;

See the following diagram to understand what initializing a node means.

The head pointer points to a location which has address 0x3000 and data value is 10. The node->next is also a pointer that maintain the linked-list and currently points to NULL.

Step 3: Create a new node and *temp points to it

We now create a new node by allocating memory dynamically for *temp.

temp = (struct node*) malloc ((struct node));

assign values to the variable and point the next pointer to NULL.

temp->data = 20;
temp->next = NULL;

See the memory drawing below to understand the process.

Right now, we have two independent nodes, not a linked-list. To start building a list and making sure that the linked-list work like a stack.

Step 4: Now temp nodes must point to head node so that it becomes the first node or head node.

temp->next = head;

Step 5: Write a pop () function that removes the top element.

In the stack, pop () function directly removes the top element automatically. You need to skip the top element and make the second element as the head of the linked-list based stack.

To make a new head use following code

head = head->next;

Flowchart

Program Code – Stack using Linked-List

#include < stdio.h >
#include < stdlib.h >
#include < malloc.h >

struct node
{

    int data;

    struct node * next;

} * head, * temp, * p;

    void push();
    void pop();

int main()
{

    int n, i;

    char ch;

    printf("how many nodes ?:");

    scanf("%d", & n);

    head = (struct node * ) malloc(sizeof(struct node));
 
    printf("Enter a value for node->data:");

    scanf("%d", & head - > data);

    head - > next = NULL;

    for (i = 0; i < n - 1; i++) 
    { 

        push(); 

    } 

        printf("\n\n"); 

        printf("Top = %d \n\n ", head - > data);

        printf("Do you wish to Pop:y/n:");

        scanf("%s", & ch);

    if (ch == 'y')
    {

        pop();

        printf("\n\n");

        printf("new top = %d\n", head - > data);

        printf("\n\n");

    }

    system("PAUSE");

    return 0;

}

void push()

{

    temp = (struct node * ) malloc(sizeof(struct node));

    printf("Enter a value for node->data:");

    scanf("%d", & temp - > data);

    temp - > next =

    head = temp;

}

void pop()

{

    head = head - > next;

}

Output

When you run the program, enter the number of nodes required for linked-list based stack. Then start entering value to the top of the stack. In the following figure, 434 is the last in entry, so it is the top of the stack, also head of the linked-list.

If you decide to pop() the top element – 434, then the second last entry becomes the top element. In this case, 125 is the new top element.

Basic JavaScript- Exercise-05 – Variable Declarations

Posted on by

Variables are the most important element of any programming language. Variables hold values so that you can write expressions using them.You evaluate the expressions and again use a variable to store the results.

In JavaScript, variables are created using keyword “var”. There is no need to declare the type of the variable before assigning a value because as soon as you assign a value to the variable, the type is automatically decided.In this exercise, you will create an external JavaScript file called main.js and an HTML page called ex05.html and save it to a folder on your windows desktop (exercise-05). To know the difference between external and internal JavaScript files, go through exercise-03 and exercise-02.

JavaScript File

In this section, you will create a new text file, insert the example JavaScript code and save the file as main.js.

Step 1: Create a new folder on your windows desktop called “Exercise-05”.

Step 2: Create a new text file inside the “Exercise-05” folder and save it as main.txt.

Step 3: Open the main.txt file and insert the following JavaScript code.

var carname = "Hundai";
var carnumber = 2340;
var num = 10;
var n = 10;
var i = 0;

document.write("This is a car and it's Model is" 
+ " " + carname + "");

document.write("The car number is " + " " 
+ carnumber + "");

document.write("\n");
var txt1 = "What a very";
var txt2 = "nice day";
var txt3 = txt1 + " " + " " + txt2;document.write(txt3 + " ");
for (i = 0; i < n; i++)
{
   num = num * 4;
}
document.write("Number=" + num);

Step 4: Save the file as main.js in “Exercise-05” folder and close it.

The variable names, carname, txt1, txt2 and txt3 are decided using the keyword “var” and assigned a string value “Hyundai”. It automatically becomes a variable of type String.

Similarly, the variable carnumber, num and i are declared using keyword “var” and assigned an integer value, so they automatically become variables of type integer.

We will discuss more JavaScript data types later.

The JavaScript expressions use variables and in the example JavaScript, variables txt3 stores the result of the concatenation of two strings – txt1 and txt2. The Variable num is multiplied with 4 repeatedly until the loop exits and the final result is stored in variable num itself.

Create an HTML Page

Assuming that you have done all the steps mentioned in the previous section, in this section, you will create an HTML page called ex05.html and link JavaScript file main.js to the HTML document.

Step 1: Create a new text file called ex05.txt in the folder Exercise-05 on your windows desktop.

Step 2: Open the ex05.txt file and insert the following HTML code and save it as ex05.html.

<!DOCTYPE html>
<html>
<head>
   <title>
       Basic Javascript: Exercise-05:Variable Declarations
   </title>
</head>
<body>
    <p>Javascript Variable, String Concatenation and Loop</p>
</body>
</html>

Step 3: Add the following script to link the JavaScript file main.js to the HTML page ex05.html between <head> ... </head> section.

<script type="text/JavaScript" src="main.js"></script>

Output to Browser

You will see the following output in the browser.