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.1. A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic and Boolean.
2.2. Prefix: Parent, left, right (PLR) Infix : Left, Parent, Right (LPR) Postfix: Left, right,Parent (LRP)
2.3. P E M D A S
2.3.1. Parentheses, Exponents, Multiplication, Division, Add,Sub
2.4. Example: arithmetic expression tree for the expression (2 x (a-1)+(3 x b)) + x x 2 - 3 b a 1
3. Tree
3.1. A tree is a collection of nodes with one root and branches
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.1. Binary search trees support three main operations;insertion, deletion and lookup
5.2. A binary search tree (BST) is a binary tree data structure which has the following properties: Each node (item in the tree) has a real value. Both the left and right sub trees must also be binary search trees.
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); }