## Trees

Trees Definitions: Binary Tree: A binary tree is either empty or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root. Node: Each element of a binary tree is called a node of a tree. Father: If A is the root of the binary tree and B is the root of its left or right subtree,…

Read more...## Threaded Binary Trees

are closed

Threaded Binary Trees Threaded Binary Trees are an improvement over Binary Search Trees that uses stack for iterative traversal. If a strategy is introduced such that the leaf node of a binary search tree points to its inorder predecessor or its successor, then direct links (called threads) are obtained to traverse a tree without using stack, which basically stores and retrieves the address of nodes in LIFO manner. If the…

Read more...Tags:Data Structure , Threaded Binary Tree , Tree

## Program to implement In-Threaded Binary Tree

are closed

In-Threaded-Binary Tree Program to implement In-Threaded Binary Tree: /*In-threaded Binary Tree*/ #include <stdio.h> #include <conio.h> #include <stdlib.h> typedef struct threadedbinarytree { int info; struct threadedbinarytree *left,*right; int lflag,rflag; }tbt; tbt *create(); tbt *makenode(int); tbt *insert(tbt *,tbt *); int inorderSuccessor(tbt *,tbt *); int inorderPredecessor(tbt *,tbt *); void traverseInorder(tbt *); /*Allocate memory*/ tbt *create() { tbt *temp=(tbt *)malloc(sizeof(tbt)); if(temp==NULL) {printf(“nMemory Allocation Error!”); exit(1); } return temp; } /*Make a new node*/ tbt…

Read more...Tags:Data Structure , Threaded Binary Tree , Tree

## Program to implement Right-In-Threaded Binary Tree

are closed

Right-In-Threaded Binary Tree Program to implement Right-In-Threaded Binary Tree: /*Right In Threaded Binary Tree*/ #include <stdio.h> #include <conio.h> #include <stdlib.h> typedef struct threadedbinarytree {int info; struct threadedbinarytree *left,*right; int rlink; }TBT; TBT *create(); TBT *makenode(int); TBT *insert(TBT *,TBT *); /*inorder or symmetric order*/ void inorder(TBT *); /*Depth first order*/ void preorder(TBT *); TBT *create() { TBT *temp=(TBT *)malloc(sizeof(TBT)); if(temp==NULL) {printf(“Memory Allocation Error!”); exit(1); } return temp; } TBT *makenode(int x)…

Read more...Tags:Data Structure , Threaded Binary Tree , Tree

## Program to implement Left-In-Threaded Binary Tree

are closed

Left-In-Threaded Binary Tree Program to implement Left-In-Threaded Binary Tree: /*Left In Threaded Binary Tree*/ #include <stdio.h> #include <conio.h> #include <stdlib.h> typedef struct threadedbinarytree {int info; struct threadedbinarytree *left,*right; int lflag; }TBT; TBT *create(); TBT *makenode(int); TBT *insert(TBT *,TBT *); void traverseDescending(TBT *); TBT *create() { TBT *temp=(TBT *)malloc(sizeof(TBT)); if(temp==NULL) {printf(“Memory Allocation Error!”); exit(1); } return temp; } TBT *makenode(int x) {TBT *temp=create(); temp->info=x; temp->left=NULL; temp->right=NULL; temp->lflag=1;/*1 for thread,0 for link*/…

Read more...Tags:Data Structure , Threaded Binary Tree , Tree

## Program to implement various operations on a Binary Search Tree

are closed

Binary Search Tree: Program to implement various operations on Binary Search Tree: /*Binary Search Tree*/ #include <stdio.h> #include <alloc.h> #include <conio.h> #include <stdlib.h> #define MAX 10 /* -OPERATIONS- (i) Creation of a Binary Search Tree (ii) Traversal a) Preorder – Recursive/Iterative b) Inorder – Recursive/Iterative c) Postorder – Recursive/Iterative d) Level by Level (iii) Insertion a) Recursive b) Iterative (iv) Deletion a) Recursive b) Iterative (v) Searching a) Recursive b)…

Read more...## Program to create a Binary Search Tree

are closed

Binary Search Trees: A Binary Search Tree is a Binary Tree which satisfies the following conditions: The left subtree of the root contains keys smaller than the root. The right subtree of the root contains keys greater than the root. The left and right subtrees are also Binary Search Trees. There are no duplicates in the tree. Program to create a Binary Search Tree: /*Creating a Binary Search Tree*/ #include…

Read more...## Binary Search Tree

are closed

Binary Search Tree A Binary Search Tree is a Binary Tree which satisfies the following conditions: The left subtree of the root contains keys smaller than the root. The right subtree of the root contains keys greater than the root. The left and right subtrees are also Binary Search Trees. There are no duplicates in the tree. A Binary Search Tree may be represented using arrays and linked list. Representation…

Read more...## Advanced Trees

are closed

Advanced Trees Definitions: Red/Black Tree: It was invented by Rudolf Bayer in 1972. Red-black trees are one of the preferred methods of maintaining binary search trees. An n node red-black tree has the height of O(logn). Moreover balancing time for such a tree on account of insertion and deletion is O(logn). A red-black tree is a binary search tree with the following properties: Every node is colored either red or…

Read more...
are closed