Advertisement
Guest User

Untitled

a guest
Apr 26th, 2018
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.12 KB | None | 0 0
  1. import random
  2.  
  3. def Add_Node(Tree, Node):
  4. if Tree[1] > Node:
  5. if Tree[0] == None:
  6. Tree[0] = [None, Node, None]
  7. else:
  8. Tree[0] = Add_Node(Tree[0], Node)
  9. elif Tree[1] <= Node:
  10. if Tree[2] == None:
  11. Tree[2] = [None, Node, None]
  12. else:
  13. Tree[2] = Add_Node(Tree[2], Node)
  14. return Tree
  15.  
  16.  
  17. def Delete_Node(Tree, Node):
  18. if Tree[1] < Node:
  19. Tree[2] = Delete_Node(Tree[2], Node)
  20. elif Tree[1] > Node:
  21. Tree[0] = Delete_Node(Tree[0], Node)
  22. else:
  23. if Tree[0] == None and Tree[2] == None:
  24. return None
  25. elif Tree[0] == None:
  26. return Tree[2]
  27. elif Tree[2] == None:
  28. return Tree[0]
  29. else:
  30. temp, Tree = Delete_2Node(Tree, Node)
  31. Tree[1] = temp
  32. return Tree
  33.  
  34.  
  35. def Delete_2Node(Tree, Node):
  36. if Tree[1] == Node:
  37. temp, Tree[2] = Delete_2Node(Tree[2], Node)
  38. elif Tree[0] != None:
  39. temp, Tree[0] = Delete_2Node(Tree[0], Node)
  40. elif Tree[0] == None and Tree[2] == None:
  41. temp = Tree[1]
  42. Tree = Delete_Node(Tree, temp)
  43. elif Tree[0] == None:
  44. temp = Tree[1]
  45. Tree = Tree[2]
  46. return temp, Tree
  47.  
  48.  
  49. def Print_Tree(Deep, Tree):
  50. if Tree:
  51. Print_Tree(Deep + 1, Tree[2])
  52. print(" " * Deep * 4, Tree[1])
  53. Print_Tree(Deep + 1, Tree[0])
  54.  
  55.  
  56. def Straight_Detour(Tree, Mas):
  57. Mas.append(Tree[1])
  58. if Tree[0] != None:
  59. Straight_Detour(Tree[0], Mas)
  60. if Tree[2] != None:
  61. Straight_Detour(Tree[2], Mas)
  62. return Mas
  63.  
  64.  
  65. def Reverse_Detour(Tree, Mas):
  66. if Tree[0] != None:
  67. Reverse_Detour(Tree[0], Mas)
  68. if Tree[2] != None:
  69. Reverse_Detour(Tree[2], Mas)
  70. Mas.append(Tree[1])
  71. return Mas
  72.  
  73.  
  74. def Dymmetric_Detour(Tree, Mas):
  75. if Tree[0] != None:
  76. Dymmetric_Detour(Tree[0], Mas)
  77. Mas.append(Tree[1])
  78. if Tree[2] != None:
  79. Dymmetric_Detour(Tree[2], Mas)
  80. return Mas
  81.  
  82.  
  83. def Find_Node(Tree, Root):
  84. if Root > Tree[1]:
  85. if Tree[2] != None:
  86. return Find_Node(Tree[2], Root)
  87. return False
  88. elif Root < Tree[1]:
  89. if Tree[0] != None:
  90. return Find_Node(Tree[0], Root)
  91. return False
  92. elif Root == Tree[1]:
  93. return True
  94.  
  95.  
  96. # Digits = [random.randint(1, 100) for x in range(10)]
  97. Digits = [19, 13, 33, 3, 17, 15, 18, 31, 35, 42, 32]
  98.  
  99. Tree = [None, Digits.pop(0), None]
  100. for i in Digits:
  101. Tree = Add_Node(Tree, i)
  102.  
  103. print("Исходное дерево:")
  104. Print_Tree(1, Tree)
  105.  
  106. t = int(input("Удалить элемент:"))
  107. if Find_Node(Tree, t):
  108. print("\nЭлемент {} найден в дереве".format(t),'\n')
  109. Tree = Delete_Node(Tree, t)
  110. print("Дерево после удаления:")
  111. Print_Tree(1, Tree)
  112. else:
  113. print("\nЭлемент {} отсутствует".format(t),'\n')
  114.  
  115. print("Прямой обход:", Straight_Detour(Tree, []),'\n')
  116. print("Обратный обход:", Reverse_Detour(Tree, []),'\n')
  117. print("Симметричный обход:", Dymmetric_Detour(Tree, []))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement