clark.anthony.g
BAN USER#!/usr/bin/python
from binarytree import Node, setup, tree, pprint
class MyTree(object):
def __init__(self, initial):
self.root = Node(initial)
def __repr__(self):
pprint(self.root)
return ''
#
# Decode 's' into a tree starting at root.
# The format of the output tree is binary with values less
# than the current node on the left and values greater than on
# the right.
#
def decode_str(s, root):
if not len(s):
return
# have at least 2 chars left in string
if len(s) > 1:
# create a new node with the next 2 chars
root.right = Node(s[:2])
# decode the rest of the string...
decode_str(s[2:], root.right)
# have at least 1 char left in string
if len(s) > 0:
# create a new node with the next 2 chars
root.left = Node(s[:1])
# decode the reset of the string...
decode_str(s[1:], root.left)
# Fills 'paths' will all unique paths through the tree
# via BFS.
def tree_paths(t, paths, path = None):
if not t:
return
if not path:
path = []
path.append(t.value)
if not t.left and not t.right:
paths.append(path)
else:
tree_paths(t.left, paths, path[:])
tree_paths(t.right, paths, path[:])
# Creates a mapping via a=1, b=2, c=3... z=26
def create_alphabet_map():
return {str(k+1):chr(v + 97) for k,v in enumerate(range(26))}
######
amap = create_alphabet_map()
t = MyTree("1123")
decode_str(t.root.value, t.root)
print t
# Do the left and right instead of root to avoid the input
# string as part of the paths
paths = []
tree_paths(t.root.left, paths)
tree_paths(t.root.right, paths)
print 'Total combos (tree paths):', len(paths)
for p in paths:
for c in p:
print amap[c],
print
#### output:
#
#
# _____1123____
# / \
# ___1__ 11
# / \ / \
# 1 12 2 23
# / \ / /
# 2 23 3 3
# /
# 3
#
#
# Total combos (tree paths): 5
# a a b c
# a a w
# a l c
# k b c
# k w
- clark.anthony.g June 29, 2017