FilesExpand file tree

master

/

P43_BinarySearchTree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

145 lines (120 loc) · 3.94 KB

master

/

P43_BinarySearchTree.py

Copy path

Top

File metadata and controls

• Code
• Blame

145 lines (120 loc) · 3.94 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

# Author: OMKAR PATHAK

# This program illustrates an example of Binary Search Tree using Python

class Node(object):

def __init__(self, data):

self.data = data

self.leftChild = None

self.rightChild = None

def insert(self, data):

''' For inserting the data in the Tree '''

if self.data == data:

return False # As BST cannot contain duplicate data

elif data < self.data:

''' Data less than the root data is placed to the left of the root '''

if self.leftChild:

return self.leftChild.insert(data)

else:

self.leftChild = Node(data)

return True

else:

''' Data greater than the root data is placed to the right of the root '''

if self.rightChild:

return self.rightChild.insert(data)

else:

self.rightChild = Node(data)

return True

def find(self, data):

''' This function checks whether the specified data is in tree or not '''

if(data == self.data):

return True

elif(data < self.data):

if self.leftChild:

return self.leftChild.find(data)

else:

return False

else:

if self.rightChild:

return self.rightChild.find(data)

else:

return False

def preorder(self):

'''For preorder traversal of the BST '''

if self:

print(str(self.data), end = ' ')

if self.leftChild:

self.leftChild.preorder()

if self.rightChild:

self.rightChild.preorder()

def inorder(self):

''' For Inorder traversal of the BST '''

if self:

if self.leftChild:

self.leftChild.inorder()

print(str(self.data), end = ' ')

if self.rightChild:

self.rightChild.inorder()

def postorder(self):

''' For postorder traversal of the BST '''

if self:

if self.leftChild:

self.leftChild.postorder()

if self.rightChild:

self.rightChild.postorder()

print(str(self.data), end = ' ')

class Tree(object):

def __init__(self, initial_data = []):

self.root = None

# If provided, add initial data

for data in initial_data:

self.insert(data)

def insert(self, data):

if self.root:

return self.root.insert(data)

else:

self.root = Node(data)

return True

def find(self, data):

if self.root:

return self.root.find(data)

else:

return False

def preorder(self):

if self.root is not None:

print()

print('Preorder: ')

self.root.preorder()

def inorder(self):

print()

if self.root is not None:

print('Inorder: ')

self.root.inorder()

def postorder(self):

print()

if self.root is not None:

print('Postorder: ')

self.root.postorder()

def pprint(self, head_node=0, _pre="", _last=True, term=False):

head_node = self.root if head_node == 0 else head_node

data = "*" if head_node is None else head_node.data

print(_pre, "`- " if _last else "|- ", data, sep="")

_pre += " " if _last else "| "

if term: return

for i, child in enumerate([head_node.leftChild, head_node.rightChild]):

self.pprint(child, _pre, bool(i) ,term=not(bool(child)))

if __name__ == '__main__':

tree = Tree()

tree.insert(10)

tree.insert(12)

tree.insert(5)

tree.insert(4)

tree.insert(20)

tree.insert(8)

tree.insert(7)

tree.insert(15)

tree.insert(13)

tree.pprint()

print(tree.find(1))

print(tree.find(12))

tree.preorder()

tree.inorder()

tree.postorder()