CODEWITHSUNDEEP
c++binary-treetree-traversal
Ryan
Ryan

Reputation: 11

C++, How to create and draw a Binary Tree then traverse it in Pre-Order

How do I create a Binary Tree and draw it using a Pre-Order Traversal strategy? The root would be the first number going in.

I have a set of numbers: 48 32 51 54 31 24 39. 48 would be the root. How are the child nodes pushed onto the Binary Tree in a Pre-Order traversal?

Upvotes: 0

Views: 1930

Answers (2)

NoxSatuKeir
NoxSatuKeir

Reputation: 27

Say you have the following binary tree:

        A
      /    \  
    B        C   
   / \      / \
  D   E    F   G
     / \    
    H   I

A Pre-Order Traversal goes NODE, LEFT, RIGHT.

So Pre-Order of this binary tree would be: A B D E H I C F G

For more details on how to implement this in C++: https://stackoverflow.com/a/17658699/445131

Upvotes: 2

Shahbaz
Shahbaz

Reputation: 47583

Imagine the following sub-problem. You have a set of numbers:

N A1...AX B1...BY

You know that N is the root of the corresponding tree. All you need to know is what numbers form the left sub-tree. Obviously the rest of the numbers form the right sub-tree.

If you remember the properties of a binary-search trees, you would know that elements of the left sub-tree have values smaller than the root (while the ones on the right have values bigger).

Therefore, the left sub-tree is the sequence of numbers that are smaller than (or possibly equal to) N. The rest of the numbers are in the right sub-tree.

Recursively solve for

A1...AX

and

B1...BY

For example given:

10 1 5 2 9 3 1 6 4 11 15 12 19 20

You get:

  • root: 10
  • left sub-tree: 1 5 2 9 3 1 6 4
  • right sub-tree: 11 15 12 19 20

Upvotes: 2

Related Questions