Data Structures Part 6

Can you construct a tree using postorder and preorder traversal? 

          

No Consider 2 trees below Tree1 a b Tree 2 a b preorder = ab postorder = ba Preorder and postorder do not uniquely define a binary tree. Nor do preorder and level order (same example). Given an expression tree, evaluate the expression and obtain a paranthesized form  of the expression.  The code below prints the paranthesized form of a tree. infix_exp(p) { if(p) { printf("("); infix_exp(p->left); printf(p->data); infix_exp(p->right); printf(")"); } } What is a threaded binary tree?   Since traversing the three is the most frequent operation, a method  must be devised to improve the speed. This is where Threaded tree comes into picture. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. An extra field called the rthread is used.  If rthread is equal to 1, then it means that the right link of  the node points to the inorder success. If its equal to 0, then the right link represents an link connecting the right subtree. struct node { int value; struct node *left; struct node *right; int rthread; } Function to find the inorder successor mynode *inorder_successor(mynode *x) { mynode *temp; temp = x->right; if(x->rthread==1)return(temp); while(temp->left!=NULL)temp = temp->left; return(temp); } Function to traverse the threaded tree in inorder void inorder(mynode *head) { mynode *temp; if(head->left==head) { printf("\nTree is empty!\n"); return; } temp = head; for(;;) { temp = inorder_successor(temp); if(temp==head)return; printf("%d ", temp->value); } } Inserting toward the left of a node in a threaded binary tree. void insert(int item, mynode *x) { mynode *temp; temp = getnode(); temp->value = item; x->left = temp; temp->left=NULL; temp->right=x; temp->rthread=1; } Function to insert towards the right of a node in a  threaded binary tree. void insert_right(int item, mynode *x) { mynode *temp, r; temp=getnode(); temp->info=item; r=x->right; x->right=temp; x->rthread=0; temp->left=NULL; temp->right=r; temp->rthread=1; } Function to find the inorder predecessor (for a left threaded binary three) mynode *inorder_predecessor(mynode *x) { mynode *temp; temp = x->left; if(x->lthread==1)return(temp); while(temp->right!=NULL) temp=temp->right; return(temp); }