python - Perfect Binary Tree with correct data -
i having problem trying fill data perfect binary tree known number of nodes correct data. basically, have implementation creates this:
7 5 6 1 2 3 4
however, looking create tree this:
7 3 6 1 2 4 5
my current implementation inserting nodes of tree follows.
def _add_node(self, val, ref = none): # reference root of tree ref = self.root if ref none else ref if ref.right none: ref.right = node(val, ref) return elif ref.left none: ref.left = node(val, ref) return else: parent = (val - 1) / 2 if parent % 2 == 0: self._add_node(val, ref.left) else: self._add_node(val, ref.right)
given x
nodes create tree using range(x)
, calling add_node(i)
each iteration. works fine except order incorrect.
for life of me cannot figure out easy way set values represent bottom layout rather top. can me out?
this seems issue order entering data in. how passing in data?
also think implementation. check see whether right child empty , if place node there. however, if isn't move on left node. issue happening.
assuming passing in data in reverse chronological order start 7 @ root. move 6 place in right node. move on 5; check see whether right node empty, isn't because filled 6, move on check if left node empty , find is. place 5 there.
do see issue?
you need figure out way around issue, in helping debug.
good luck!
Comments
Post a Comment