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

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

{
"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
}