FilesExpand file tree

 master

/

binary_tree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

159 lines (135 loc) · 4.4 KB

 master

/

binary_tree.py

Copy path

Top

File metadata and controls

• Code
• Blame

159 lines (135 loc) · 4.4 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

class TreeNode(object):

def __init__(self, key):

self.key = key

self.left = None

self.right = None

class BinaryTree(object):

# class TreeNode(object):

# def __init__(self, key):

# self.key = key

# self.left = None

# self.right = None

def __init__(self, root):

self.root = root

def insert_left(self, val):

if self.left is None:

self.left = BinaryTree(val)

else:

sub_tree = BinaryTree(val)

sub_tree.left = self.left

self.left = sub_tree

def insert_right(self, val):

if self.right is None:

self.right = BinaryTree(val)

else:

sub_tree = BinaryTree(val)

sub_tree.right = self.right

self.right = sub_tree

def traverse_in_order(self):

def _traverse_in_order(tNode):

if tNode is not None:

_traverse_in_order(tNode.left)

print(tNode.key)

_traverse_in_order(tNode.right)

_traverse_in_order(self.root)

def traverse_pre_order(self):

def _traverse_pre_order(tNode):

if tNode is not None:

print(tNode.key)

_traverse_pre_order(tNode.left)

_traverse_pre_order(tNode.right)

_traverse_pre_order(self.root)

def traverse_post_order(self):

def _traverse_post_order(tNode):

if tNode is not None:

_traverse_post_order(tNode.left)

_traverse_post_order(tNode.right)

print(tNode.key)

_traverse_post_order(self.root)

def in_order_search(self, val):

def _in_order_search(tNode):

if tNode is None:

return None

else:

if tNode.key == val:

return tNode

elif tNode.key > val:

return _in_order_search(tNode.left)

else:

return _in_order_search(tNode.right)

return _in_order_search(self.root)

def in_order_insert(self, val):

def _in_order_insert(tNode):

if tNode is None:

new_root = TreeNode(val)

tNode = new_root

return

if val < tNode.key and tNode.left is None:

left_child = TreeNode(val)

tNode.left = left_child

return

if val > tNode.key and tNode.right is None:

right_child = TreeNode(val)

tNode.right = right_child

return

if val < tNode.key and tNode.left is not None:

return _in_order_insert(tNode.left)

if val > tNode.key and tNode.right is not None:

return _in_order_insert(tNode.right)

else:

raise ValueError('Non valid input')

_in_order_insert(self.root)

def getLeftChild(self):

return self.left

def getRightChild(self):

return self.right

def setNodeValue(self, val):

self.root = val

def getNodeValue(self):

return self.root

def print_tree(self, ):

current = self.root

if current is not None:

self.print_tree(self.getLeftChild())

print(current.getNodeValue())

self.print_tree(self.getRightChild())

if __name__ == '__main__':

node1 = TreeNode(1)

node2 = TreeNode(2)

node3 = TreeNode(3)

node4 = TreeNode(4)

node5 = TreeNode(5)

node6 = TreeNode(6)

node7 = TreeNode(7)

node8 = TreeNode(8)

node9 = TreeNode(9)

node10 = TreeNode(10)

# my_tree = BinaryTree(node5)

# node5.left = node3

# node5.right = node9

# node3.left = node1

# node3.right = node4

# node9.left = node7

# node9.right = node10

# node7.right = node8

my_tree = BinaryTree(node7)

my_tree.in_order_insert(1)

my_tree.in_order_insert(3)

my_tree.in_order_insert(9)

my_tree.in_order_insert(4)

my_tree.in_order_insert(10)

my_tree.in_order_insert(8)

my_tree.in_order_insert(5)

my_tree.traverse_in_order()

print'\n'

my_tree.traverse_pre_order()

print '\n'

my_tree.traverse_post_order()

print '\n'

my_tree.in_order_insert(6)

result = my_tree.in_order_search(6)

if result:

print('%s\n' % result.key)

else:

print('Node not in the tree')

my_tree.traverse_in_order()