0
Explain non-recursive and recursive algorithm for postorder traversal on binary tree?
Wiki User
∙ 11y ago
Step 1:- select first root node (t), start travelsing left contin
Wiki User
∙ 11y ago
Add your answer:
Earn +20 pts
Why recursive solution is better for tree traversal?
Because a tree is a recursive data-structure. It's easier to write (and easier to understand) a recursive program for handling it.
Why is there no threading for post order traversal of a binary search tree?
You don't need it. Think about it, you can just use a stack (or a recursive function.)
Write the algorithm for in order traversal?
Inorder(p) { If p = nil return; Inorder(p.left) process(p.data) Inorder(p.right) }
How do you print all data in a Binary Search Tree?
By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.
Which of the following traversal is used for printing the keys of binary search tree in ascending order?
In order traversal is used.
Why recursive solution is better for tree traversal?
Because a tree is a recursive data-structure. It's easier to write (and easier to understand) a recursive program for handling it.
Why is there no threading for post order traversal of a binary search tree?
You don't need it. Think about it, you can just use a stack (or a recursive function.)
Explain the three types of tree traversals with illustration?
Inorder Traversal void inorder(tree t) { if(t == NULL) return; inorder(t->left); printf("%d ", t->val); inorder(t->right); }Preorder Traversalvoid preorder(tree t) { if(t == NULL) return; printf("%d ", t->val); preorder(t->left); preorder(t->right); } Postorder Traversalvoid postorder(tree t) { if(t == NULL) return; postorder(t->left); postorder(t->right); printf("%d ", t->val);
What graph traversal algorithm uses a queue to keep track of vertices which need to be processed?
Breadth-first search
How do you write a c program for expression tree traversal?
#include<stdio.h> #include<conio.h> #define MAX 30 typedef struct ETREE { struct ETREE *lc; char data; struct ETREE *rc; }etree; typedef struct STACK { etree *ST[MAX]; int top; }stack; void initialize_stack(stack *sp) { sp->top = -1; } int isstackempty(int top) { if(top MAX - 1) return(1); else return(0); } void push(stack *sp,etree *x) { if(!isstackfull(sp->top)) { sp->top = sp->top + 1; sp->ST[sp->top] = x; } else printf("\n\nStack full!!"); } etree *pop(stack *sp) { etree *x; if(!isstackempty(sp->top)) { x = sp->ST[sp->top]; sp->top = sp->top - 1; return(x); } else return(NULL); } etree *getnode(char d) { etree *node; node = (etree *)malloc(sizeof(etree)); node->lc = NULL; node->data = d; node->rc = NULL; return(node); } etree *construct_etree_from_postfix_exp(char pos[]) { int i; stack s; etree *root = NULL,*node; initialize_stack(&s); for(i=0;pos[i] != '\0';i++) { node = getnode(pos[i]); if(isalpha(pos[i])) { push(&s,node); } else //operator { node->rc = pop(&s); node->lc = pop(&s); push(&s,node); } } root = pop(&s); return(root); } void inorder(etree *temp) { if(temp!= NULL) { inorder(temp->lc); printf("%c",temp->data); inorder(temp->rc); } } void preorder(etree *temp) { if(temp!= NULL) { printf("%c",temp->data); preorder(temp->lc); preorder(temp->rc); } } void postorder(etree *temp) { if(temp!= NULL) { postorder(temp->lc); postorder(temp->rc); printf("%c",temp->data); } } void inorder_nonrec(etree *root) { stack s; etree *temp; temp = root; initialize_stack(&s); while(temp!=NULL s.top!= -1) { while(temp!=NULL) { push(&s,temp); temp = temp->lc; } temp = pop(&s); printf("%c",temp->data); temp = temp->rc; } } void preorder_nonrec(etree *root) { stack s; etree *temp; temp = root; initialize_stack(&s); while(temp!=NULL s.top!= -1) { while(temp!=NULL) { printf("%c",temp->data); push(&s,temp); temp = temp->lc; } temp = pop(&s); temp = temp->rc; } } void postorder_nonrec(etree *root) { stack s; etree *temp; int i,k=0; char A[30]; temp = root; initialize_stack(&s); while(temp!=NULL s.top!= -1) { while(temp!=NULL) { A[k++] = temp->data; push(&s,temp); temp = temp->rc; } temp = pop(&s); temp = temp->lc; } for(i=k-1;i>=0;i--) { printf("%c",A[i]); } } void main() { char pos[30]; etree *root = NULL; int ch; do { clrscr(); printf("\n Choice 1: Create Etree from postfix expression "); printf("\n Choice 2: Recursive inorder,preorder & postorder traversal"); printf("\n Choice 3: Nonrecursive inorder,preorder & postorder traversal"); printf("\n Choice 4: exit "); printf("\n Enter your choice: "); scanf("%d",&ch); switch(ch) { case 1: printf("\n\nEnter the postfix expression : "); scanf("%s",pos); root = construct_etree_from_postfix_exp(pos); printf("\n\nExpression tree created successfully !!"); break; case 2: printf("\n Inorder traversal is : "); inorder(root); printf("\n preorder traversal is : "); preorder(root); printf("\n postorder traversal is : "); postorder(root); getch(); break; case 3: printf("\n Inorder traversal (nonrecursive) : "); inorder_nonrec(root); printf("\n Preorder traversal (nonrecursive) : "); preorder_nonrec(root); printf("\n Postorder traversal (nonrecursive) : "); postorder_nonrec(root); getch(); break; case 4: printf("\n \t**End of program** \n \t\tThank you\n"); break; default:printf("\n invalid choice try again!!!!"); } getch(); }while(ch!=4); } Written by: Fabianski Benjamin
Write the algorithm for in order traversal?
Inorder(p) { If p = nil return; Inorder(p.left) process(p.data) Inorder(p.right) }
How can you design an algorithm to check if a given graph is connected?
Use a simple DFS/BFS traversal. If you have gone through all nodes, the graph is connected.
What are the advantages and disadvantages of binary trees?
1. This makes the Tree more complex. as we need to keep the record of node's Predecessor and successor 2. Postorder traversal is too complex and there might be changes of errors when both the child are not present & both values of nodes pointer to their Predecessor. -Snehal Javheri
How do you print all data in a Binary Search Tree?
By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.
What is the difference between BFS and DFS?
BFS: This can be throught of as being like Dijkstra's algorithm for shortest paths, but with every edge having the same length. However it is a lot simpler and doesn't need any data structures. We just keep a tree (the breadth first search tree), a list of nodes to be added to the tree, and markings (Boolean variables) on the vertices to tell whether they are in the tree or list. Depth first search is another way of traversing graphs, which is closely related to preorder traversal of a tree. Recall that preorder traversal simply visits each node before its children. It is most easy to program as a recursive routine:
Which of the following traversal is used for printing the keys of binary search tree in ascending order?
In order traversal is used.
What is traverse technique used in chain survey?
1. pre-order b-tree traversal. 2. in-order b-tree traversal. 3. post-order b-tree traversal
