python/tree_list.py at master · addie/python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# Tree data structure
"""
myTree = \
    ['a',
		['b',
			['d',[],[]],
		    ['e',[],[]]
		],
		['c',
			['f',[],[]],
		    []]
	]
print(myTree)
print('left subtree = ', myTree[1])
print('root = ', myTree[0])
print('right subtree = ', myTree[2])
"""

def BinaryTree(r):
    return [r, [], []]

def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch, [], []])
    return root

def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root

def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

#     a
#  b    c
# d    e  f
def buildTree():
	r = BinaryTree('a')
	insertLeft(r,'b')
	insertLeft(getLeftChild(r), 'd')
	insertRight(r,'c')
	insertLeft(getRightChild(r),'e')
	insertRight(getRightChild(r),'f')
	return r

r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertRight(r,6)
insertRight(r,7)
l = getLeftChild(r)
print(l)

setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))

print (buildTree())

tree2 = \
['a',
	['b',
		['d', [], []], []
	],
	['c',
		['e', [], []],
		['f', [], []]
	]
]