You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

410 lines
12 KiB
Plaintext

{
"cells": [
{
"cell_type": "markdown",
"id": "4708c5dc-a1e8-42e2-8702-ecea9513d54b",
"metadata": {},
"source": [
"# a binary tree of leaves of letters"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "906fc548-a2a5-411b-ad60-9e93e88bf7f5",
"metadata": {},
"outputs": [],
"source": [
"# http://syllabus.cs.manchester.ac.uk/ugt/2021/COMP26912/lab/ex5.html\n",
"# https://web.stanford.edu/class/archive/cs/cs106x/cs106x.1174/assn/twentyOneQuestions.html\n",
"# https://www.openbookproject.net/py4fun/animal/animal.html"
]
},
{
"cell_type": "code",
"execution_count": 330,
"id": "578e93f8-e04f-4b01-a482-ebc78cf2c103",
"metadata": {},
"outputs": [],
"source": [
"# each leaf stores a letter to be asked\n",
"class letterLeaf:\n",
" def __init__(self,letter):\n",
" self.leftAlphabet = None\n",
" self.rightAlphabet = None\n",
" self.letter = letter\n",
" # try using a list structure to contain the words in this node? \n",
" self.words = []"
]
},
{
"cell_type": "code",
"execution_count": 331,
"id": "fa8e3d45-ea21-47e1-9a5a-256e5e7ebed1",
"metadata": {},
"outputs": [],
"source": [
"# tree traversals, here to print stuff \n",
"def inorder(treeName):\n",
" if treeName:\n",
" inorder(treeName.leftAlphabet)\n",
" print(treeName.letter)\n",
" inorder(treeName.rightAlphabet)"
]
},
{
"cell_type": "code",
"execution_count": 332,
"id": "0c75f820-46c4-46af-b5d9-b837cb055b55",
"metadata": {},
"outputs": [],
"source": [
"# printing tree utility \n",
"# this segment is modified from Shubham Singh(SHUBHAMSINGH10)'s contribution \n",
"\n",
"# spacer\n",
"COUNT = [10]\n",
"\n",
"# print a flat lying tree\n",
"# speculation this is a recursion that prints the right leaf until there is nothing left\n",
"def print2DUtil_flat(root, space) :\n",
" # Base case\n",
" if (root == None) :\n",
" return\n",
" # Increase distance between levels\n",
" space += COUNT[0]\n",
" # Process right leaf/branch/child first\n",
" print2DUtil_flat(root.rightAlphabet, space)\n",
" print()\n",
" for i in range(COUNT[0], space):\n",
" print(end = \" \")\n",
" print(root.letter)\n",
" # Process left child\n",
" print2DUtil_flat(root.leftAlphabet, space)\n",
"\n",
" # Wrapper over print2DUtil()\n",
"def print2D(root) :\n",
" #Pass initial space count as 0\n",
" print(\"here is a tree that's laying on the ground: \")\n",
" print2DUtil_flat(root, 0)\n"
]
},
{
"cell_type": "code",
"execution_count": 333,
"id": "5f27d6d6-3019-4714-98d0-9650f1e087bb",
"metadata": {},
"outputs": [],
"source": [
"# utility to read the first letter of the input word \n",
"# press enter key, otherwise notebook will be pending\n",
"def grepFirstLetter():\n",
" word = input()\n",
" firstLetter = word[0]\n",
" return firstLetter\n",
" #print(\"the letter starts with : {}, and will be inserted under the {} leaf\".format(firstLetter, firstLetter))"
]
},
{
"cell_type": "code",
"execution_count": 334,
"id": "11081ff6-0295-4329-885c-6e6ddfddfcbf",
"metadata": {},
"outputs": [],
"source": [
"def insertLeaf(root,firstLetter):\n",
" #create new leaf \n",
" letterLeaf(firstLetter)\n",
" # python pointer implementation\n",
" # a root pointer \n",
" x = root\n",
" # pointer y maintains the trailing\n",
" # pointer of x\n",
" y = None\n",
" # traversal \n",
" # while x != none means the pointer can keep traversing\n",
" while(x != None):\n",
" y = x #trailing pointer points to x \n",
" if (firstLetter < x.letter):\n",
" x = x.leftAlphabet\n",
" else:\n",
" x = x.rightAlphabet\n",
" # insert leaf at root when tree is empty \n",
" if (y == None):\n",
" y = letterLeaf \n",
" # do string comparison, insert at left side of the alphabetTree \n",
" elif (firstLetter < x.letter):\n",
" x.leftAlphabet = letterLeaf\n",
" # insert at right side of the alphabetTree\n",
" else:\n",
" x.rightAlphabet = letterLeaf\n",
" \n",
" # Returns the pointer where the\n",
" # new node is inserted\n",
" # ? \n",
" return y\n"
]
},
{
"cell_type": "code",
"execution_count": 335,
"id": "22301756-70e0-4ff7-b9bb-4f59c458058b",
"metadata": {},
"outputs": [],
"source": [
"# print binary tree in 2D copied from sample program\n",
"COUNT = [10]\n",
"def print2DUtil(root, space) :\n",
"\n",
" # Base case\n",
" if (root == None) :\n",
" return\n",
"\n",
" # Increase distance between levels\n",
" space += COUNT[0]\n",
"\n",
" # Process right child first\n",
" print2DUtil(root.rightAlphabet, space)\n",
"\n",
" # Print current node after space\n",
" # count\n",
" print()\n",
" for i in range(COUNT[0], space):\n",
" print(end = \" \")\n",
" print(root.letter)\n",
"\n",
" # Process left child\n",
" print2DUtil(root.leftAlphabet, space)\n",
"\n",
"# Wrapper over print2DUtil()\n",
"def print2D(root) :\n",
" \n",
" # space=[0]\n",
" # Pass initial space count as 0\n",
" print2DUtil(root, 0)"
]
},
{
"cell_type": "code",
"execution_count": 336,
"id": "883373d0-cccc-4497-b9ff-af45670cb1ce",
"metadata": {},
"outputs": [],
"source": [
"# A utility function to insert a new\n",
"# Node with given key in BST\n",
"def insert(root, letter):\n",
"\n",
" # Create a new Node containing\n",
" # the new element\n",
" newleaf = letterLeaf(letter)\n",
"\n",
" # Pointer to start traversing from root\n",
" # and traverses downward path to search\n",
" # where the new node to be inserted\n",
" x = root\n",
"\n",
" # Pointer y maintains the trailing\n",
" # pointer of x\n",
" y = None\n",
"\n",
" while (x != None):\n",
" y = x\n",
" if (letter < x.letter):\n",
" x = x.leftAlphabet\n",
" else:\n",
" x = x.rightAlphabet\n",
" \n",
" # If the root is None i.e the tree is\n",
" # empty. The new node is the root node\n",
" if (y == None):\n",
" y = newleaf\n",
"\n",
" # If the new key is less then the leaf node key\n",
" # Assign the new node to be its left child\n",
" elif (letter < y.letter):\n",
" y.leftAlphabet = newleaf\n",
"\n",
" # else assign the new node its\n",
" # right child\n",
" else:\n",
" y.rightAlphabet = newleaf\n",
"\n",
" # Returns the pointer where the\n",
" # new node is inserted\n",
" return y\n",
"\n",
"# A utility function to do inorder\n",
"# traversal of BST"
]
},
{
"cell_type": "code",
"execution_count": 337,
"id": "0f0bed93-2858-471b-b827-35f66da519b8",
"metadata": {},
"outputs": [],
"source": [
"def Inorder(root) :\n",
"\n",
" if (root == None) :\n",
" return\n",
" else:\n",
" Inorder(root.leftAlphabet)\n",
" print( root.letter, end = \" \" )\n",
" Inorder(root.rightAlphabet)"
]
},
{
"cell_type": "code",
"execution_count": 338,
"id": "e1884b95-8b53-49d6-b56c-a7226f14937e",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']\n",
"\n",
" z\n",
"\n",
" y\n",
"\n",
" x\n",
"\n",
" w\n",
"\n",
" v\n",
"\n",
" u\n",
"\n",
" t\n",
"\n",
" s\n",
"\n",
" r\n",
"\n",
" q\n",
"\n",
" p\n",
"\n",
" o\n",
"\n",
" n\n",
"\n",
" m\n",
"\n",
" l\n",
"\n",
" k\n",
"\n",
"j\n",
"\n",
" i\n",
"\n",
" h\n",
"\n",
" g\n",
"\n",
" f\n",
"\n",
" e\n",
"\n",
" d\n",
"\n",
" c\n",
"\n",
" b\n",
"\n",
" a\n"
]
}
],
"source": [
"#Driver Code\n",
"import random\n",
"#if __name__ == '__main__':\n",
"\n",
"alphabet = [\"a\",\"b\",\"c\",\"d\",\"e\",\"f\",\"g\",\"h\",\"i\",\"j\",\"k\",\"l\",\"m\",\"n\",\"o\",\"p\",\"q\",\"r\",\"s\",\"t\",\"u\",\"v\",\"w\",\"x\",\"y\",\"z\"]\n",
"root = None\n",
"# pick a random letter in the alphabet\n",
"random_letter = random.choice(alphabet)\n",
"#print(random_letter)\n",
"#insert it into the tree, insert the first one \n",
"root = insert(root, random_letter)\n",
"# remove that letter from list\n",
"alphabet.remove(random_letter)\n",
"print(alphabet)\n",
"len_list = (len(alphabet))\n",
"#print(len_list)\n",
"while len_list > 0:\n",
" random_letter = random.choice(alphabet)\n",
" insert(root,random_letter)\n",
" alphabet.remove(random_letter)\n",
" #print(\"inserting and removing letter {} \".format(random_letter))\n",
" len_list -= 1\n",
"# keep inserting until the list is empty \n",
"# print tree \n",
"print2D(root)\n",
"# can try multiple times for different tree configurations"
]
},
{
"cell_type": "code",
"execution_count": 329,
"id": "d222d70f-2771-45be-9ac1-7ac579a242cb",
"metadata": {},
"outputs": [],
"source": [
"# print a vertical standing tree \n",
"# https://www.geeksforgeeks.org/print-level-order-traversal-line-line/\n",
"# https://www.geeksforgeeks.org/level-order-tree-traversal/"
]
},
{
"cell_type": "code",
"execution_count": 323,
"id": "39d68b3e-064e-4ed6-b10d-c7250a7034e3",
"metadata": {},
"outputs": [],
"source": [
"# a morse code tree\n",
"# https://www.101computing.net/morse-code-using-a-binary-tree/"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f7205015-dd4b-48bf-94c4-be0f96d8988a",
"metadata": {},
"outputs": [],
"source": [
"#firstLetter = grepFirstLetter()\n",
"#print(firstLetter)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.7"
}
},
"nbformat": 4,
"nbformat_minor": 5
}