We implement the binary tree sort algorthm in SageMath by first defining a
Node in the the tree to contain three components, a key value, a left child and a right child. This is accomplished with the following code. An expression of the form
Node(k) creates a node with key
k and no children.
def __init__(self, keyval=None,Lchild=None,Rchild=None):
self.key = keyval
self.left = Lchild
self.right = Rchild
We define the function
insert_sort to recursively insert a key value,
b, into a tree rooted at
r. We will use this function to build a binary tree. Smaller key values are steered to the left and larger ones to the right.
Once the tree is built, we traverse it with the function
inorder_traverse, which assembles a sorted list.
We demonstrate the process with a list of integers.
The first number in the list is placed at the root of our tree and then the rest are inserted using
insert_sort. Note: In Python (and hence in SageMath), all but the first entry in a list
a is most easily specified using
for b in a[1:]:
Now we traverse the tree to get our sorted list.
[811, 1884, 1943, 2324, 2923, 2945, 2993, 3390, 4263, 4545, 5306, 6461, 6810, 6953, 7082, 7333, 7909, 8229, 8260, 8337, 8414, 8663, 8945, 9352, 9656]