Python Binary Tree


/ Published in: Python
Save to your folder(s)



Copy this code and paste it in your HTML
  1. # A binary ordered tree example
  2.  
  3. class CNode:
  4. left , right, data = None, None, 0
  5.  
  6. def __init__(self, data):
  7. # initializes the data members
  8. self.left = None
  9. self.right = None
  10. self.data = data
  11.  
  12. class CBOrdTree:
  13. def __init__(self):
  14. # initializes the root member
  15. self.root = None
  16.  
  17. def addNode(self, data):
  18. # creates a new node and returns it
  19. return CNode(data)
  20.  
  21. def insert(self, root, data):
  22. # inserts a new data
  23. if root == None:
  24. # it there isn't any data
  25. # adds it and returns
  26. return self.addNode(data)
  27. else:
  28. # enters into the tree
  29. if data <= root.data:
  30. # if the data is less than the stored one
  31. # goes into the left-sub-tree
  32. root.left = self.insert(root.left, data)
  33. else:
  34. # processes the right-sub-tree
  35. root.right = self.insert(root.right, data)
  36. return root
  37.  
  38. def lookup(self, root, target):
  39. # looks for a value into the tree
  40. if root == None:
  41. return 0
  42. else:
  43. # if it has found it...
  44. if target == root.data:
  45. return 1
  46. else:
  47. if target < root.data:
  48. # left side
  49. return self.lookup(root.left, target)
  50. else:
  51. # right side
  52. return self.lookup(root.right, target)
  53.  
  54. def minValue(self, root):
  55. # goes down into the left
  56. # arm and returns the last value
  57. while(root.left != None):
  58. root = root.left
  59. return root.data
  60.  
  61. def maxDepth(self, root):
  62. if root == None:
  63. return 0
  64. else:
  65. # computes the two depths
  66. ldepth = self.maxDepth(root.left)
  67. rdepth = self.maxDepth(root.right)
  68. # returns the appropriate depth
  69. return max(ldepth, rdepth) + 1
  70.  
  71. def size(self, root):
  72. if root == None:
  73. return 0
  74. else:
  75. return self.size(root.left) + 1 + self.size(root.right)
  76.  
  77. def printTree(self, root):
  78. # prints the tree path
  79. if root == None:
  80. pass
  81. else:
  82. self.printTree(root.left)
  83. print root.data,
  84. self.printTree(root.right)
  85.  
  86. def printRevTree(self, root):
  87. # prints the tree path in reverse
  88. # order
  89. if root == None:
  90. pass
  91. else:
  92. self.printRevTree(root.right)
  93. print root.data,
  94. self.printRevTree(root.left)
  95.  
  96. if __name__ == "__main__":
  97. # create the binary tree
  98. BTree = CBOrdTree()
  99. # add the root node
  100. root = BTree.addNode(0)
  101. # ask the user to insert values
  102. for i in range(0, 5):
  103. data = int(raw_input("insert the node value nr %d: " % i))
  104. # insert values
  105. BTree.insert(root, data)
  106. print
  107.  
  108. BTree.printTree(root)
  109. print
  110. BTree.printRevTree(root)
  111. print
  112. data = int(raw_input("insert a value to find: "))
  113. if BTree.lookup(root, data):
  114. print "found"
  115. else:
  116. print "not found"
  117.  
  118. print BTree.minValue(root)
  119. print BTree.maxDepth(root)
  120. print BTree.size(root)

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.