Course Code : MCS-021
Course Title : Data and file Structures
Last Date of Submission : 15th October, 2019 (For July 2019 Session)
15th April, 2020 (For January 2020 Session)
Q1.Write an algorithm that accept binary tree as input and print the number of leaf nodes to standard output.
Ans:
#include <iostream.h>
using namespace std;
/* A binary tree node has data,
pointer to left child and
a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
/* Function to get the count
of leaf nodes in a binary tree*/
unsigned int getLeafCount(struct node* node)
{
if(node == NULL)
return 0;
if(node->Ieft == NULL && node->right == NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
/*create a tree*/
struct node *root = newNode(l);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/*get leaf count of the above created tree*/
printf( "%d Leaf count of the tree is\n");
getLeafCount(root);
return 0;
}
Q2.Write an algorithm for implementation of a AVL tree.
Ans:
#include <stdio.h>
#include <stdlib.h>
struct avl_node_s {
struct avl_node_s *left;
struct avl_node_s *right;
int value;
};
typedef struct avl_node_s avl_node_t;
struct avl_tree_s {
struct avl_node_s *root;
};
typedef struct avl_tree_s avl_tree_t;
/* Create a new AVL tree. */
avl_tree_t *avl_create() {
avl_tree_t *tree = NULL;
if( ( tree = malloc( sizeof( avl_tree_t )
return NULL;
}
tree—>root = NULL;
return tree;
}
/* Initialize a new node. */
avl node t *avl create node() {
avl_node_t *node = NULL;
if( ( node = malloc( sizeof( avl node t )))==NULL){
return NULL;
}
node—>left = NULL;
node—>right = NULL;
node—>value =0;
return node;
}
/* Insert a new node. */
void avl_insert( avl_tree_t *tree, int value ) {
avl_node_t *node = NULL;
avl_node_t *next = NULL;
avl_node_t *last = NULL;
/* Well, there must be a first case */
if( tree—>root == NULL ) {
node = avl_create_node();
node—>value = value;
tree—>root = node;
/* Okay. We have a root already. Where do we put this? */
} else {
next = tree—>root;
last = NULL;
while( next != NULL )
last = next;
if( value < next—>value ) {
next = next—>left;
} else if( value > next—>value ) {
next = next—>right;
/* Have we already inserted this node? */
} else if( value == next—>value ) {
/* This shouldn't happen. */
}
}
node = avl_create_node();
node—>value = value;
if( value < last—>Value ) last—>left = node;
if( value > last—>Value ) last—>right = node;
}
}
/* Find the height of an AVL node recursively */
int avl_node_height( avl_node t *node ) {
int height_left = 0;
int height_right = 0;
if( node—>left ) height_left = avl_node_height( node—>left );
if( node—>right ) height_right = avl_node_height( node—>right );
return height_right > height_left ? ++height_right
++height_left;
}
/* Find the balance of an AVL node */
int avl_node_balance( avl_node_t *node ) {
int balance = 0;
if( node—>left ) balance += avl node height( node—>left );
if( node—>right ) balance —= avlinodeiheight( node—>right );
return balance;
}
/* Do a depth first traverse of a node. */
void avl_traverse_node_dfs( avl_node_t *node, int depth ) {
int i = 0;
if( node—>left ) avl_traverse_node_dfs( node—>left, depth + 2 );
for( i = 0; i < depth; i++ ) putchar( ' ' );
printf( "%d: %d\n", node—>value, avl_node_balance( node ) );
if( node—>right ) avl_traverse_node_dfs( node—>right, depth + 2
);
}
/* Do a depth first traverse of a tree. */
void avl traverse dfs( avl tree t *tree ) {11
avl_traverse_node_dfs( tree—>root, O );
}
void main()
{
avl_tree_t *tree = NULL;
clrscr();
tree = avl_create();
avl_insert( tree, 30)
avl_insert (tree, 20)
avl_insert (tree, 40)
avl_insert (tree, 10)
avl_insert( tree, 50)
avl_traverse_dfs( tree);
getch();
}
Q3.Write a note of not more than 5 pages summarizing the latest research in the area of "Trees" .Refer of various journals and other online resources .Indicate them in your assignment.
Ans: In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
A tree data structure can be defined recursively as a collection of nodes (starting at a root(node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.
Alternatively, a tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node. Both these perspectives are useful: while a tree can be analyzed
mathematically as a whole, when actually represented as a data structure it is
usually represented and worked with separately by node (rather than as a set of nodes and an adjacency list of edges between nodes, as one may represent a digraph, for instance). For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general as a data structure a given node only contains the list of its children, but does not
contain a reference to its parent (if any).
Unordered tree
Mathematically, an unordered tree[1] (or "algebraic tree"[2]) can be defined as an algebraic structure {\displaystyle (X,parent)} {\displaystyle (X,parent)} where X is the non-empty carrier set of nodes and parent is a function on X which assigns each node x its "parent" node, parent(x). The structure is subject to the condition that every non-empty subalgebra must have the same fixed point. That is, there must be a unique I'root" node r, such that parent(r) = r and
for every node x, some iterative application parent(parent(...parent(x)...)) equals r.
There are several equivalent definitions. As the closest alternative, one can define unordered trees as partial algebras (X, parent) which are obtained from the total algebras described above by letting parent(r) be undefined. That is, the root r is the only node on which the parent function is not defined and for every node x, the root is reachable from x in the directed graph (X, parent). This definition is in fact coincident with that of an anti-arborescence. The TAoCP
book uses the term oriented tree.[3]
Another equivalent definition is that of a set-theoretic tree that is sineg-rooted and whose height is at most (omega sign) (a finite-ish tree[4]). That is, the algebraic structures (X, parent) are equivalent to partial orders {\displaystyle (X,\|eq )} (X, \Ie) that have a top element r and whose every principal upset (aka principal filter) is a finite chain. To be precise, we should speak about
an inverse set-theoretic tree since the set-theoretic definition usually employs opposite ordering. The correspondence between (X, parent) and (X, S) is established via reflexive transitive closure / reduction, with the reduction resulting in the "partial" version without the root cycle.
The definition of trees in descriptive set theory (DST) utilizes the representation of partial orders (X, 2) as prefix orders between finite sequences. In turns out that up to isomorphism, there is a one-to-one correspondence between the (inverse of) DST trees and the tree structures defined so far.
We can refer to the four equivalent characterizations as to tree as an algebra, tree as a partial algebra, tree as a partial order, and tree as a prefix order. There is also a fifth equivalent definition — that of a graph-theoretic rooted tree which is just a connected acyclic rooted graph.
Terminology
A node is a structure which may contain a value or condition, or represent a separate data structure (which could be a tree of its own). Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees are drawn growing downwards). A node that has a child is called the child's parent node (or ancestor node, or superior). A node has at most one parent.An internal node (also known as an inner node, inode for short, or branch node) is any node of a tree that has child nodes. Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes.The topmost node in a tree is called the root node. Depending on definition, a tree may be required to have a root node (in which case all trees are non-empty), or may be allowed to be empty, in which case it does not necessarily have a root node. Being the topmost node, the root node will not have a parent. It is the node at which algorithms on the tree begin, since as a data structure, one can only pass from parents to children. Note that some algorithms (such as post-order depth-first search) begin at the root, but first visit leaf nodes (access the value of
leaf nodes), on|y visit the root last (i.e., they first access the children of the root, but only access the value of the root last). All other nodes can be reached from it by following edges or links. (In the formal definition, each such path is also unique.) In diagrams, the root node is conventionally drawn at the top. In some trees, such as heaps, the root node has special properties. Every node in a tree can be seen as the root node of the subtree rooted at that
node.
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self- balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero.
Conventionally, an empty tree (tree with no nodes, if such are allowed) has height —1.
A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T.[f][21]Nodes thus correspond to subtrees (each node corresponds to the subtree of itself and all itsdescendants) — the subtree corresponding to the root node is the entire tree, and each node is the root node of the subtree it determines; the subtree corresponding to any other node is called a proper subtree (by analogy to a proper subset).
Drawing trees
Trees are often drawn in the plane. Ordered trees can be represented essentially uniquely in the plane, and are hence called plane trees, as follows: if one fixes a conventional order (say, counterclockwise), and arranges the child nodes in that order (first incoming parent edge, then first child edge, etc.), this yields an embedding of the tree in the plane, unique up to ambient isotopy. Conversely, such an embedding determines an ordering of the child nodes.
If one places the root at the top (parents above children, as in a family tree) and places all nodes that are a given distance from the root (in terms of number of edges: the "level" of atree) on a given horizontal line, one obtains a standard drawing of the tree. Given a binary tree,
the first child is on the left (the "Left node"), and the second child is on the right (the "right node").
Representations
There are many different ways to represent trees; common representations represent the nodes as dynamically allocated records with pointers to their children, their parents, or both, or as items in an array, with relationships between them determined by their positions in the array (e.g., binary heap).
Indeed, a binary tree can be implemented as a list of lists (a list where the values are lists): the head of a list (the value of the first term) is the left child (subtree), while the tail (the list of second and subsequent terms) is the right child (subtree). This can be modified to allow values as well, as in Lisp S-expressions, where the head (value of first term) is the value of the node, the head of the tail (value of second term) is the left child, and the tail of the tail (list of third and subsequent terms) is the right child.
In general a node in a tree will not have pointers to its parents, but this information can be included (expanding the data structure to also include a pointer to the parent) or stored separately. Alternatively, upward links can be included in the child node data, as in a threaded binary tree.
Generalizations
Digraphs
If edges (to child nodes) are thought of as references, then a tree is a special case of a digraph, and the tree data structure can be generalized to represent directed graphs by removing the constraints that a node may have at most one parent, and that no cycles are allowed. Edges are still abstractly considered as pairs of nodes, however, the terms parent and child are usually replaced by different terminology (for example, source and target). Different implementation
strategies exist: a digraph can be represented by the same local data structure as a tree (node with value and list of children), assuming that I'list of children" is a list of references, or globally by such structures as adjacency lists.
|n graph theory, a tree is a connected acyclic graph; unless stated otherwise, in graph theory trees and graphs are assumed undirected. There is no one-to-one correspondence between such trees and trees as data structure. We can take an arbitrary undirected tree, arbitrarily pick one of its vertices as the root, make all its edges directed by making them point away from the root node — producing an arborescence — and assign an order to all the nodes. The resultcorresponds to a tree data structure. Picking a different root or different ordering produces a
different one.
Traversal methods
Stepping through the items of a tree, by means of the connections between parents and children, is called walking the tree, and the action is a 'walk' of the tree. Often, an operation might be performed when a pointer arrives at a particular node. A walk in which each parent node is traversed before its children is called a pre-order walk; a walk in which the children are traversed before their respective parents are traversed is called a post-order walk; a walk in which a node's left subtree, then the node itself, and finally its right subtree are traversed is called an in-order traversal. (This last scenario, referring to exactly two subtrees, a left subtree and a right subtree, assumes specifically a binary tree.) A level-order walk effectively performs a breadth-first search over the entirety of a tree; nodes are traversed level by level, where the root node is visited first, followed by its direct child nodes and their siblings, followed by its
grandchild nodes and their siblings, etc., until all nodes in the tree have been traversed.
Q4.Write an algorithm for implementation for stack.
Ans:
// C program for array implementation of stack
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// A structure to represent a stack
struct Stack{
int top;
unsigned capacity;
int* array;
// function to create a stack of given capacity. It initializes size of
// stack as O
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
return stack->top == stack->capacity - 1;
}
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
return stack->to == -1;
}
// Function to add an item to stack. It increases top by 1
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
printf("%d pushed to stack\n", item);
}
// Function to remove an item from stack. It decreases top by 1
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return |NT_M|N;
return stack->array[stack->top--1;
}
// Function to return the top from stack without removing it
int peek(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top];
}
// Driver program to test above functions
int main()
{
struct Stack* stack = createStack(100);
push(stack, 10);
push(stack, 20);
push(stack, 30);
printf("%d popped from stack\n", pop(stack));
return 0;
}
0 comments:
Post a Comment