FilesExpand file tree

 master

/

binaryTree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

121 lines (107 loc) · 3.34 KB

 master

/

binaryTree.py

Copy path

Top

File metadata and controls

• Code
• Blame

121 lines (107 loc) · 3.34 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

# A binary ordered tree example

class CNode:

left , right, data = None, None, 0

def __init__(self, data):

# initializes the data members

self.left = None

self.right = None

self.data = data

class CBOrdTree:

def __init__(self):

# initializes the root member

self.root = None

def addNode(self, data):

# creates a new node and returns it

return CNode(data)

def insert(self, root, data):

# inserts a new data

if root == None:

# it there isn't any data

# adds it and returns

return self.addNode(data)

else:

# enters into the tree

if data <= root.data:

# if the data is less than the stored one

# goes into the left-sub-tree

root.left = self.insert(root.left, data)

else:

# processes the right-sub-tree

root.right = self.insert(root.right, data)

return root

def lookup(self, root, target):

# looks for a value into the tree

if root == None:

return 0

else:

# if it has found it...

if target == root.data:

return 1

else:

if target < root.data:

# left side

return self.lookup(root.left, target)

else:

# right side

return self.lookup(root.right, target)

def minValue(self, root):

# goes down into the left

# arm and returns the last value

while(root.left != None):

root = root.left

return root.data

def maxDepth(self, root):

if root == None:

return 0

else:

# computes the two depths

ldepth = self.maxDepth(root.left)

rdepth = self.maxDepth(root.right)

# returns the appropriate depth

return max(ldepth, rdepth) + 1

def size(self, root):

if root == None:

return 0

else:

return self.size(root.left) + 1 + self.size(root.right)

def printTree(self, root):

# prints the tree path

if root == None:

pass

else:

self.printTree(root.left)

print root.data,

self.printTree(root.right)

def printRevTree(self, root):

# prints the tree path in reverse

# order

if root == None:

pass

else:

self.printRevTree(root.right)

print root.data,

self.printRevTree(root.left)

if __name__ == "__main__":

# create the binary tree

BTree = CBOrdTree()

# add the root node

root = BTree.addNode(0)

# ask the user to insert values

for i in range(0, 5):

#data = int(raw_input("insert the node value nr %d: " % i))

data = raw_input("insert the node value nr %d: " % i)

# insert values

BTree.insert(root, data)

print

BTree.printTree(root)

print

BTree.printRevTree(root)

print

data = int(raw_input("insert a value to find: "))

if BTree.lookup(root, data):

print "found"

else:

print "not found"

print BTree.minValue(root)

print BTree.maxDepth(root)

print BTree.size(root)