undefinedfix
Sign in

C ++ Draw binary tree according to preorder and middle order

rortr edited in Fri, 23 Sep 2022

图片描述

Is the pre order abcdefgh and the middle order cdbagfeh like this? What's the secret of painting this??? Can you give me an answer?? How to distinguish between the left and right subtrees' child nodes on the left or on the right

1 Replies
CodeBreaker
commented on Fri, 23 Sep 2022

First of all, foreword means: middle > left > right middle order means: left > middle > right

analysis

Because the root node is a, CDB is on the left subtree of a and gfeh is on the right subtree of A

First consider the left subtree of A

Because the root node is B, CD is in the left subtree of B

Consider the left subtree of B again

05: CD indicates that the root node is C. 06: CD because the root node is C, D is the right node of C

Consider the right subtree of a again

Since the root node is e, GF is on the left subtree of E, h is on the right subtree of E, and H is the right node of E

Consider the left subtree of e again

09 pre order: FG indicates that the root node is F10 middle order: GF since the root node is f, G is the left node of F

Conclusion:

From 01, the root node is a

From 03, the left node of a is B, from 07, the right node of a is e

It can be seen from 05 that the left node of B is C

From 09, the left node of E is f, from 08, the right node of E is h

From 06, we can see that the right node of C is d

It can be seen from 10 that the left node of F is g

Draw a picture:

            a
          /   \
         b     e
        /     / \ 
       c     f   h
        \   /   
         d g
         

That's about it



Update: draw a binary tree from middle order and back order

The first and second order means: left --> right --> Middle order means: left --> in --> right

analysis

Because the root node is h, aedbc is on the left subtree of H and GF is on the right subtree of H

First consider the left subtree of H

Because the root node is e, a is the left node of E, and DBC is on the right subtree of E

Consider the right subtree of e again

Because the root node is D, BC is in the right subtree of D

Consider the right subtree of D again

Since the root node is C, B is the left node of C

Consider the right subtree of H again

09: FG indicates that the root node is G10: GF since the root node is g, f is the right node of G

Conclusion:

It can be seen from 01 that the root node is h

From 03, the left node of H is e, from 09, the right node of H is g

From 04 we can see that the left node of E is a, from 05 we can see that the right node of E is d

It can be seen from 10 that the right node of G is f

It can be seen from 07 that the right node of D is C

From 08, we can see that the left node of C is B

Draw a picture:

           h
          / \
         e   g
        / \   \
       a   d   f
            \
             c
            /
           b