Sharedsage_worksheets / binary_tree_sort.sagews.htmlOpen in CoCalc
Worksheets related to Applied Discrete Structures


AuthorKen Levasseur
Original filebinary_tree_sort.sagews
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.
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.
[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]