search

xqian / cpp_projects

cplusplus projects for myself
2 stars 2 forks source link

print the perimeter of a Binary tree #4

Closed xqian closed 11 years ago

xqian commented 11 years ago

/*

The last RD83's solution is good. "handles Yossi's example"

xqian commented 11 years ago

commit ad255070e273441860b343a455e19b7541fe63ef Author: Xin Qian xinqian@datillus.com Date: Thu May 23 23:33:14 2013 -0700

Tree One

recursive:(90(40(20(10(5),),(30,(35))),(60(50,(55)),(70))),)

90, 40, 20, 10, 5, 35, 55, 70, 60,

         90

      40

  20      60

10 30   50    70

5 35 55

perimeter- 90, 40, 20, 10, 5, 35, 55, 70, 60,

Tree Two:

pre_order recursive:(40(20(10(5),),(30,(35))),(60(50,(55)),(70,(90))))

40, 20, 10, 5, 35, 55, 90, 70, 60,

          40

    20            60

10 30 50 70

5 35 55 90

perimeter- 40, 20, 10, 5, 35, 55, 90, 70, 60,

xqian commented 11 years ago

The code is in bst.cc and testCase9

xqian commented 11 years ago

bug fix:

commit 31008cc48c7eb51dbb0c6314e5cb77f64e15c8e5 Author: Xin Qian xinqian@datillus.com Date: Thu May 23 23:54:05 2013 -0700

fix bugs, left boundary might contain right child, and it will always print out, which is not like right boundary
xqian commented 11 years ago

I compose a more complext tree to test, the current left/leaf/right code works pretty well on that:

                    8
                             90
                    40
               20             60
          10     30      50     70
             12   35  55  65
          11   15               68
xqian commented 11 years ago

commit c528ae32bd23518ce59c3613b95bdf063e2bba4c Author: Xin Qian xinqian@datillus.com Date: Sat May 25 01:42:48 2013 -0700

issue #4

1. add a test case
2. add a recursive method, it is really teadious and easy to make mistake
xqian commented 11 years ago

caset 9:

pre_order recursive:(5,(90(40(20(10,(12(11),(15))),(30,(35))),(60(50,(55)),(70(65,(68)),))),)) 5, 90, 40, 20, 10, 12, 11, 15, 35, 55, 68, 65, 70, 60, pre_order recursive:(40(20(10(5),),(30,(35))),(60(50,(55)),(70,(90)))) 40, 20, 10, 5, 35, 55, 90, 70, 60,

case 10:

pre_order recursive:(5,(90(40(20(10,(12(11),(15))),(30,(35))),(60(50,(55)),(70(65,(68)),))),)) 5, 90, 40, 20, 10, 12, 11, 15, 35, 55, 68, 65, 70, 60, pre_order recursive:(40(20(10(5),),(30,(35))),(60(50,(55)),(70,(90)))) 40, 20, 10, 5, 35, 55, 90, 70, 60,