CHAPTER 5

Get Started. It's Free CHAPTER 5 1. Tree Traversal

1.1. process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node

1.1.1. binary tree has a root, left subtree and right subtree. ROOT Left Right Subtree Subtree

1.1.2. In-order Traversal (LPR) A B C D E F G *D->B->E->A->F->C->G*

1.1.3. Pre-order Traversal(PLR) A B C D E F G *A->B->D->E->C->F->G*

1.1.4. Post-order Traversal(LRP) A B C D E F G *D->E->B->F->G->C->A*

1.2. Tree Traversal Arithmetic

1.2.1. Prefix * - / 8 5 + 3 4 2 ((8-8)*((4+2)/3))

1.2.2. Infix * - / 8 5 + 3 4 2 *-8 5/+ 4 2 3

1.2.3. Postfix * - / 8 5 + 3 4 2 8 5-4 2+3/*

2. Arithmetic Tree Expression

2.3. P E M D A S

2.3.1. Parentheses, Exponents, Multiplication, Division, Add,Sub

3. Tree

3.2. The QUEUE and the STACK are linear lists. But they do not imply there is any relationship between the data items themselves. However, TREE is non-linear data structure which used to represent the relationship between data items.

3.2.1. A tree is a finite non-empty set of elements

3.2.2. A tree consists of nodes with a parent-child relation

4. Binary Tree

4.1. A binary tree has a special condition that each node can have two children at maximum

4.1.1. A binary tree is a tree with the following properties: Each internal node has at most two children (degree of two) The children of a node are an ordered pair

5. Binary Tree Search

5.3. LEFT SUB TREE < RIGHT SUB TREE

5.3.1. Example: 20 15 30 13 18 23 45

5.4. Binary search tree. Removing a node There are 3 condition of item that want to be removed:- Node to be removed has no children. Node to be removed has one child Node to be removed has two children.

5.4.1. Deletion(has no children) 5 5 2 18 --> 2 18 -4 3 3

5.4.2. Deletion (has one child) 5 5 2 18 --> 2 21 -4 3 21 19 25 19 25

5.4.3. Deletion (has two child) 5 5 2 12 --> 2 12 -4 3 9 21 -4 3 9 21 19 25 19 25

5.5. Delete item from tree

5.5.1. void Delete(treeNode *& tree, int item) { if(item < tree->info) Delete(tree->left, item); else if(item > tree->info) Delete(tree->right, item); else DeleteNode(tree); } void DeleteNode(treeNode *& tree) { int data; treeNode * tempPtr; // Remove node with 1 right child tempPtr = tree; if(tree->left == NULL) { //right child tree = tree->right; delete tempPtr; }

5.6. Remove item from tree

5.6.1. // Remove node with 1 left child else if(tree->right == NULL) { // left child tree = tree->left; delete tempPtr; } // Remove node with 2 child else {// get predecessor node GetPredecessor(tree->left, data); tree->info = data; Delete(tree->left, data); } } void GetPredecessor(treeNode * &tree, int & data) { while(tree->right != NULL) tree = tree->right; data = tree->info; }

6. Implementation for Tree usingLinked List Declare structure of node for BST ; struct treeNode { int data; struct treeNode *left; struct treeNode *right; }; treeNode * root;

6.1. Create Binary Search Tree; BinarySearchTree() { root = NULL;

6.1.1. Check BST smpty?; int empty() { if(root == NULL) cout<<“Empty BST!” return (1); else return (0); }

6.1.1.1. Insert new node; void InsertData(int data) { Insert(root, data); } void Insert(treeNode*& tree, int data) { if(tree == NULL) { // base case tree = new TreeNode; tree->right = NULL; tree->left = NULL; tree->info = item; } else if(item < tree->info) Insert(tree->left, item); else Insert(tree->right, item); }