Advertisement
Guest User

Untitled

a guest
Feb 19th, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.04 KB | None | 0 0
  1. class Node:
  2. def __init__(self, val):
  3. self.l = None
  4. self.r = None
  5. self.v = val
  6.  
  7. class Tree:
  8. def __init__(self):
  9. self.root = None
  10.  
  11. def getRoot(self):
  12. return self.root
  13.  
  14. def add(self, val):
  15. if(self.root == None):
  16. self.root = Node(val)
  17. else:
  18. self._add(val, self.root)
  19.  
  20. def _add(self, val, node):
  21. if(val < node.v):
  22. if(node.l != None):
  23. self._add(val, node.l)
  24. else:
  25. node.l = Node(val)
  26. else:
  27. if(node.r != None):
  28. self._add(val, node.r)
  29. else:
  30. node.r = Node(val)
  31.  
  32. def find(self, val):
  33. if(self.root != None):
  34. return self._find(val, self.root)
  35. else:
  36. return None
  37.  
  38. def _find(self, val, node):
  39. if(val == node.v):
  40. return node
  41. elif(val < node.v and node.l != None):
  42. self._find(val, node.l)
  43. elif(val > node.v and node.r != None):
  44. self._find(val, node.r)
  45.  
  46. def deleteTree(self):
  47. # garbage collector will do this for us.
  48. self.root = None
  49.  
  50. def printTree(self):
  51. if(self.root != None):
  52. self._printTree(self.root)
  53.  
  54. def _printTree(self, node):
  55. if(node != None):
  56. self._printTree(node.l)
  57. print str(node.v) + ' '
  58. self._printTree(node.r)
  59.  
  60. def hm_L_ch(self):
  61. if (self.root != None):
  62. return self._hm_ch(self.root.l, k = -1)
  63. else: return 0;
  64.  
  65. def _hm_ch(self, node, k):
  66. if(node != None):
  67. k = k + 1
  68. self._hm_ch(node.l, k)
  69. self._hm_ch(node.r, k)
  70. return k
  71. else: return None
  72.  
  73.  
  74. N = input()
  75.  
  76. a = []
  77.  
  78. tree = Tree()
  79. i = 0
  80. while i < N:
  81. k = input()
  82. tree.add(k)
  83. i = i + 1
  84.  
  85. print tree.hm_L_ch()
  86. #tree.printTree()
  87. #print (tree.find(3)).v
  88. #print tree.find(10)
  89. #tree.deleteTree()
  90. #tree.printTree()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement