There are several well-known ways to traverse a binary tree. Let us go through Inorder Traversal, Preorder Traversal, Postorder Traversals.

Consider that we have a tree like this -

DAWN / \ DAVE MIKE / \ / \ BETH DAVID GINA PAT \ \ CINDI SUE

**Inorder traversal**

1) Traverse the left subtree

2) Visit the root

3) Traverse the right subtree

This consists of three overall steps: traverse the left subtree (recursively), visit the root node, and traverse the right subtree (recursively). When we "visit" a node we typically do some processing on it, such as printing out the contents of the node. For example, an inorder traversal of the above binary search tree gives us the names in this order:

BETH

CINDI

DAVE

DAVID

DAWN

GINA

MIKE

PAT

SUE

Note that we got the data back in ascending order. This will always happen when doing an inorder traversal of a Binary SEARCH Tree. In fact, a sort can be done this way.

**One first inserts the data into a binary search tree and then does an inorder traversal to obtain the data in ascending order. Inorder traversal of a BST always gives sorted output.**Some people call this a tree sort.**Postorder traversal**

1) Traverse the left subtree

2) Traverse the right subtree

3) Visit the root

As an example, let's do a postorder traversal of the binary expression tree for 4 * 5 - 3 :

First we traverse the left subtree of the whole binary tree. This is the subtree rooted at *. To do so, we apply our three steps. We traverse its left subtree, which results in printing 4. Then we traverse the right subtree, which results in printing 5. Then we visit the root, printing *. Next, we back up to where we left off with the whole binary tree. We have now traversed the left subtree, so we traverse the right subtree, printing 3. Then we visit the root, printing -. Overall we end up printing 4 5 * 3 -, the postfix form of the expression.- / \ * 3 / \ 4 5

A postfix expression is deciphered by looking at it left to right and using the fact that each operator (such as *) applies to the two previous values. Note that the traversal always works like this: a postorder traversal of a binary expression tree yields the postfix form of the expression.

**Thus, postfix notation can be achieved with POSTORDER traversal of BST.**

In ordinary mathematics, in infix expressions, operators such as + and * come between the two values to which they apply. In postfix - they come after and in prefix they come before.

**Preorder traversal**

1) Visit the root

2) Traverse the left subtree

3) Traverse the right subtree

For practice try a preorder traversal of the same binary expression tree for 4 * 5 - 3. The result should be - * 4 5 3. This is the prefix form of the expression, that is, the form in which each binary operator precedes the two quantities to which it applies. A preorder traversal of a binary expression tree always gives the prefix form of the expression.

I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in TECHNOLOGY , kindly contact us http://www.maxmunus.com/contact

ReplyDeleteMaxMunus Offer World Class Virtual Instructor led training on TECHNOLOGY. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 100000+ trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.

For Demo Contact us.

Saurabh Srivastava

MaxMunus

E-mail: saurabh@maxmunus.com

Skype id: saurabhmaxmunus

Ph:+91 8553576305 / 080 - 41103383

http://www.maxmunus.com/

Trung tâm kế toán Tại cầu giấy

ReplyDeleteTrung tâm kế toán Tại từ liêm

Trung tâm kế toán Tại thanh xuân

Trung tâm kế toán Tại hà đông

Trung tâm kế toán Tại long biên

Trung tâm kế toán Tại nguyễn chính thanh đống đa

Trung tâm kế toán Tại minh khai hai bà trưng

Trung tâm kế toán Tại bắc ninh

Trung tâm kế toán Tại hải phòng

Trung tâm kế toán Tại tphcm

Trung tâm kế toán Tại quận 3

Trung tâm kế toán Tại thủ đức

Trung tâm kế toán Tại đà nẵng

Trung tâm kế toán Tại biên hòa

Trung tâm kế toán Tại đồng nai

Trung tâm kế toán Tại nam định

Trung tâm kế toán Tại thái bình

Trung tâm kế toán Tại bắc giang

Trung tâm kế toán Tại vĩnh phúc

Trung tâm kế toán Tại thái nguyên

Trung tâm kế toán Tại quảng ninh

Trung tâm kế toán Tại hải dương

Trung tâm kế toán Tại hưng yên

Trung tâm kế toán Tại hà nam

Trung tâm kế toán Tại ninh bình

Trung tâm kế toán Tại nghệ an

Trung tâm kế toán Tại vũng tàu

These are the services that in our opinion do a better job at letting you fax from Gmail email. They integrate perfectly with Google’s email service and are 100% reliable for occasional and power users; what’s better, they let you try them for free before you start paying for a plan GmailFaxPro.com

ReplyDeleteVery good informative article. Thanks for sharing such nice article, keep on up dating such good articles.

ReplyDeleteNO.1 SYSTEM INTEGRATION SERVICES | SYSTEM INTEGRATION MIDDLEWARE | MASSIL TECHNOLOGIES

Great information about binary tree, thanks for sharing such a good blog.

ReplyDeleteNO.1 CLOUD SERVICES | Oracle Cloud PAAS | MASSIL TECHNOLOGIES