Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

x
x
For better view click here
x
Hire a Tutor
DISCOVER

Notes On Binary Tree Data Structure

Loading...

Published in: C / C++ | Data Structures
2,069 Views

Unlike lineardata structures (Arrays, Linked Lists, Stacks, and Queues), Binary trees are hierarchical.

Prantik S / Kolkata

11 years of teaching experience

Qualification: MCA (Jaipur National University - [JNU], Jaipur - 2017)

Teaches: Basic Computer, Computer for official job, MS Office, School Level Computer, ICT Training, Computer Science, Information Practice, IT & Computer Subjects, BCA Tuition, IT, Computer, C / C++, C# (C Sharp), Java And J2EE, Python Programming, Visual Basic, BCA Subjects, Hardware Training, Networking, Java Script

Contact this Tutor
  1. Binary Tree Unlike linear data structures (Arrays, Linked Lists, Stacks, and Queues), Binary trees are hierarchical. They consist of interconnected nodes. The topmost node is called the root. For a given node, the nodes that are directly under are called its children. The tree is called binary because each node can have at most two children. The node directly above another node is called its parent. The tree which is a child of a node is called subtree. Elements with no children are called leaves. The maximum number of nodes from root to leaf is called the height. Check out the image below for a visual representation of these terms: Root B c Siblings Parent Node Child Node Types G Level O Level 1 Level 2 Level 3 Sub-tree Leaf Node There are various types of binary trees, each having characteristics suitable for its purpose. Full Binary Tree A binary tree is considered full if every node has 0 or 2 children.
  2. Illustrations lnOrder(root) visits nodes in the following order: 4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90 A Pre-order traversal visits nodes in the following order: 25 15, 10, 4 12, 22, 18, 24 50, 35, 31,44 70, 66, 90 A Post-order traversal visits nodes in the following order: 4, 12, 10, 18, 24, 22, 15, 31, 44, 35, 66, 90, 70, 50, 25 10 (32 9 roo 15 9 22 (18 25 24 9 35 (31 c} 9 50 44 9 70 66 90
  3. ABCDEF 0123456 c E Inorder : DBHEIAFCG Preorder : ABDEHICFG Postorder : DHIEBFGCA 7
  4. For example, a full binary tree of height 3 contains 23+1 1 15 nodes. 1 2 6 Strict Birary Tree 3 7 13 1 2 9 1 5 1 6 3 4 5 6 7 12 2 4 8 Strictly Complete binary tee 3 (b) 5 3 6 2 4 7 10 11 12 13 Full binary tree 7 14 15 (d) Complete binary tree Complete Binary Tree A binary tree is considered complete if all levels are completely filled except possibly the last level and the last level has all nodes as far left as possible. Note: One of the most common applications of the binary tree is the Binary Search Tree (BST), which is used in many search applications. Perfect Binary Tree A binary tree is considered perfect if all internal nodes have two children and all leaves are at the same level. Advantages
  5. - Trees reflect structural relationships in the data, and are used to represent hierarchies. - Trees provide efficient insertion and searching. - Trees are very flexible, allowing subtrees to be moved around with minimum effort. A demo code #include #include typedef struct node{ int data; struct node* left; struct node* right; root, int if(root == NULL){ temp = temp -> data = x; temp -> left = temp -> right = NULL; return temp; if(x < root -> data){ root -> left = add_node(root->left, x);
  6. else if(x > root -> data){ root -> right = add_node(root->right, x); return root; int find_min(NODE_T* root){ if(root == NULL) printf("tree is empty\n"); if(root->left) return find_min(root->left); else printf("smallest value: %d\n", root -> data); return 0; int find_max(NODE_T* root){ if(root == NULL) printf("tree is empty\n"); if(root->right) return find_max(root->right); else printf("largest value: %d\n", root -> data); return 0;
  7. NODE_T* search(NODE_T* root, int target){ if(root == NULL) printf("tree is empty\n"); else if(target < root -> data) root -> left = search(root -> left, target); else if(target > root -> data) root -> right = search(root -> right, target); else printf("\nelement %d exists in the tree\n", root->data); return root; void preorder(NODE_T* root){ if(root != NULL) printf("%d\t", root -> data); preorder(root -> left); preorder(root -> right); void inorder(NODE_T* root){ if(root != NULL) inorder(root->left);
  8. printf("%d\t", root -> data); inorder(root->right); void postorder(NODE_T* root){ if(root != NULL) postorder(root -> left); postorder(root -> right); printf("%d\t", root -> data); int main(){ root = NULL; root = add_node(root,4); printf("added as root: %d\n", root -> data); add_node(root,5); add_node(root,0); add_node(root,8); add_node(root,l ); add_node(root,9); add_node(root,3);
  9. find_max(root); find_min(root); root = search(root,8); printf("\npreorder : I); preorder(root); printf("\ninorder inorder(root); printf("\npostorder: postorder(root); OUTPUT added as root: largest value: smallest value: 4 9 o element 8 preorder inorder postorder: exists in the tree 4013589 0134589 3109854 Code to create Binary Tree #include #include typedef struct node
  10. int data; struct node *left; struct node *right; } node; node *create() node *p; int x; printf("Enter data(-l for no node):"); scanf("%d" ,&x); if(x==-l ) return NULL; p=(node*)malloc(sizeof(node)); p->data=x; printf("Enter left child of %d:\n",x); p->left=create(); printf("Enter right child of %d:\n",x); p->right=create(); return p;
  11. void preorder(node *t) printf(" %d",t->data); preorder(t->left); preorder(t->right); void inorder(node *t) inorder(t->left); printf(" %d",t->data); inorder(t->right); void postorder(node *t) postorder(t->left);
  12. postorder(t->right); printf(" %d",t->data); void main() node *root; clrscr(); root=create(); printf("\nThe preorder traversal of tree is: I); preorder(root); printf("\nThe inorder traversal of tree is: I); inorder(root); printf("\nThe postorder traversal of tree is: I); postorder(root); getch();

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related Study Notes

Upload Study Notes

If you have your own Study Notes which you think can benefit others, please upload on LearnPick. For each approved Study Note you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > Study Notes > Notes On Binary Tree Data Structure