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.
class Node: 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.
def insert_sort(r,b): if b<r.key: if r.left==None: r.left=Node(b) else: insert_sort(r.left,b) else: if r.right==None: r.right=Node(b) else: insert_sort(r.right,b)
Once the tree is built, we traverse it with the function inorder_traverse, which assembles a sorted list.
def inorder_traverse(r): if r.left!=None: ls=inorder_traverse(r.left) else: ls=[] m=r.key if r.right!=None: rs=inorder_traverse(r.right) else: rs=[] return ls+[m]+rs
We demonstrate the process with a list of integers.
a=[6953,811,2324,1884,8945,1943,2923,7909,3390,8229,8337,9656,4545,7082,7333,6461,5306,2945,8414,9352,2993,8663,8260,6810,4263]
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 slice
notation, a[1:].
root=Node(a[0])for b in a[1:]: insert_sort(root,b)
Now we traverse the tree to get our sorted list.
inorder_traverse(root)
[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]