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

sage_worksheets/binary_tree_sort.sagews

AuthorKen Levasseur
Date2017-02-06T15:13:40
Projectf351622c-d261-4717-abee-4c0bfa210e88
Locationsage_worksheets/binary_tree_sort.sagews
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.
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]