+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: Binary tree (/thread-38886.html)
Binary tree - AlexPython - Dec-06-2022
let said that I get a randomly created array of 12 numbers for this tree below instead of having the number picked by me, should I hand-pick the root? or should I let it be one of the random numbers of the array? I asking this is because I just don't want that by change the tree end up without a number on one of the sides(left or right). For example, let said the random array gives me this list 1-2-3-4-5-6-7-8-9-10 and the program choose 1 as the root I only going to get numbers on the right side. I guess I could just get the mean of the list and use int no to get decimals? or is there an easier way?
class Node:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
def insert(self, data):
if data < self.data:
if self.leftChild:
self.leftChild.insert(data)
else:
self.leftChild = Node(data)
return
else:
if self.rightChild:
self.rightChild.insert(data)
else:
self.rightChild = Node(data)
return
def PrintTree(self):
if self.leftChild:
self.leftChild.PrintTree()
print( self.data),
if self.rightChild:
self.rightChild.PrintTree()
root = Node(27)
root.insert(28)
root.insert(30)
root.insert(26)
root.insert(22)
root.insert(18)
root.insert(17)
root.insert(14)
root.insert(35)
root.insert(31)
root.insert(10)
root.insert(19)
root.PrintTree()Output:10
14
17
18
19
22
26
27
28
30
31
35
Process finished with exit code 0RE: Binary tree - deanhystad - Dec-06-2022
The median, not the mean. The median is the middle value. There will be close to an equal number of values left and right of the median. The mean doesn't have to be close to the middle at all. The mean of 1, 2, 3, 4, 5, 6, 7, 8, 9, 100000 is 10004.5. The median is 5.
That doesn't really balance the tree though. If the values are sorted end up with a funny shape like this:
Output: 5
/ \
1 6
\ \
2 7
\ \
3 8
\ \
4 9root = median(1, 2, 3, 4, 5, 6, 7, 8, 9(
root.left = median(1, 2, 3, 4)
root.right = median(6, 7, 8, 9)
root.left.left = 1
root.left.right = median(3, 4)
root.left.right.right = 4
root.right.left = 6
root.right.right = median(8, 9)
root.right.right.right =
Output: 5
/ \
/ \
2 7
/ \ / \
1 3 6 8
\ \
4 9RE: Binary tree - AlexPython - Dec-06-2022
(Dec-06-2022, 09:43 PM)deanhystad Wrote: The median, not the mean. The median is the middle value. There will be close to an equal number of values left and right of the median. The mean doesn't have to be close to the middle at all. The mean of 1, 2, 3, 4, 5, 6, 7, 8, 9, 100000 is 10004.5. The median is 5.
That doesn't really balance the tree though. If the values are sorted end up with a funny shape like this:
You could comput the median again for values left and right of the top node. And repeat the process for the next level, and the next level and so on. But this still wouldn't keep the tree balanced as values were added later.
What you want to do is balance the tree after values are added. There are many articles written on how to balance binary trees.
Thanks
RE: Binary tree - ndc85430 - Dec-07-2022
Binary search tree.