{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Module 2, Practical 7\n", "\n", "In this practical we will keep working with data structures. In particular, we will see a special data structure called *tree*.\n", "\n", "## Trees\n", "\n", "Trees are data structures composed of two types of elements: *nodes* and *edges*. \n", "Nodes represent *objects* and edges represent *relationships* among **two** nodes. \n", "\n", "The node at the top level of the tree is called the **root**, and is connected to one or more other nodes. \n", "If the root is connected to another node by means of one edge, then it is said to be the **parent** of the node (and that node is the **child** of the root). \n", "Any node can be **parent** of one or more other nodes, but **all nodes have only one parent**. \n", "The **root is the only exception as it does not have any parent**. \n", "Finally, some nodes do not have children and they are called **leaves**.\n", "\n", "An example of tree:\n", "\n", "\n", "![](images/tree.png)\n", "\n", "As seen in the lecture, trees can be defined recursively in the following way: *a tree is a root and zero or more subtrees, each of which is also a tree. The root of each subtree is connected to the root of the parent tree by an edge.*\n", "\n", "Graphically: \n", "\n", "![](images/recursiveTree.png)\n", "\n", "\n", "Some properties of nodes and trees are:\n", "\n", "1. The *depth* of a node N: the length of the path connecting the root to N counted as number of edges in the path.\n", "\n", "2. The *level* (n) of a tree: set of nodes at the same depth (n).\n", "\n", "3. *Height* : is the maximum depth of all leaves.\n", "\n", "4. *Width* : the maximum number of nodes in each level.\n", "\n", "The following tree:\n", "\n", "![](images/exampleTree.png)\n", "\n", "has four levels (0, 1, 2, 3), height equal to 3 and width equal to 4.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## ADT: Binary Tree\n", "\n", "**Binary trees** are trees where each node has at most two children: the **right child** and the **left child**.\n", "\n", "![](images/binaryPointers.png)\n", "\n", "The specifications of the binary tree ADT (from the lecture): \n", "\n", "![](images/binarytreeADT.png)\n", "\n", "When implementing a tree we could (similarly to what we did with linked lists) define a node object, and then a tree object that stores nodes, but we will use the more compact way which is to use the recursive definition of a tree.\n", "\n", "\n", "**Example:** Let's implement a binary tree using the recursive definition: \n", ">a binary tree is a root --with a value -- connected to two subtrees, respectively the right and left subtree." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Root (r)-> 2\n", "Root (l)-> 1\n", "\t1 (r)-> 5b\n", "\t1 (l)-> 5a\n", "\t\t5b (r)-> 5c\n", "\t2 (r)-> 6\n", "\t2 (l)-> 3\n", "\t\t3 (r)-> 5\n", "\t\t3 (l)-> 4\n", "\n", "Delete right branch of 2\n", "Root (r)-> 2\n", "Root (l)-> 1\n", "\t1 (r)-> 5b\n", "\t1 (l)-> 5a\n", "\t\t5b (r)-> 5c\n", "\t2 (l)-> 3\n", "\t\t3 (r)-> 5\n", "\t\t3 (l)-> 4\n", "\n", "Insert left branch of 5\n", "Root (r)-> 2\n", "Root (l)-> 1\n", "\t1 (r)-> 5b\n", "\t1 (l)-> 5a\n", "\t\t5b (r)-> 5c\n", "\t2 (l)-> 3\n", "\t\t3 (r)-> 5\n", "\t\t3 (l)-> 4\n", "\t\t\t5 (l)-> child of 5\n" ] } ], "source": [ "class BinaryTree:\n", " def __init__(self, value):\n", " self.__data = value\n", " self.__right = None\n", " self.__left = None\n", " self.__parent = None\n", "\n", " def getValue(self):\n", " return self.__data\n", " def setValue(self, newValue):\n", " self.__data = newValue\n", "\n", " def getParent(self):\n", " return self.__parent\n", " def setParent(self, tree):\n", " self.__parent = tree\n", "\n", " def getRight(self):\n", " return self.__right\n", " def getLeft(self):\n", " return self.__left\n", "\n", " def insertRight(self, tree):\n", " if self.__right == None:\n", " self.__right = tree\n", " tree.setParent(self)\n", "\n", " def insertLeft(self, tree):\n", " if self.__left == None:\n", " self.__left = tree\n", " tree.setParent(self)\n", "\n", " def deleteRight(self):\n", " self.__right = None\n", "\n", " def deleteLeft(self):\n", " self.__left = None\n", "\n", "def printTree(root):\n", " cur = root\n", " #each element is a node and a depth\n", " #depth is used to format prints (with tabs)\n", " nodes = [(cur,0)]\n", " tabs = \"\"\n", " lev = 0\n", " while len(nodes) >0:\n", " cur, lev = nodes.pop(-1)\n", " #print(\"{}{}\".format(\"\\t\"*lev, cur.getValue()))\n", " if cur.getRight() != None:\n", " print (\"{}{} (r)-> {}\".format(\"\\t\"*lev,\n", " cur.getValue(),\n", " cur.getRight().getValue()))\n", " nodes.append((cur.getRight(), lev+1))\n", " if cur.getLeft() != None:\n", " print (\"{}{} (l)-> {}\".format(\"\\t\"*lev,\n", " cur.getValue(),\n", " cur.getLeft().getValue()))\n", " nodes.append((cur.getLeft(), lev+1))\n", "\n", "if __name__ == \"__main__\":\n", " BT = BinaryTree(\"Root\")\n", " bt1 = BinaryTree(1)\n", " bt2 = BinaryTree(2)\n", " bt3 = BinaryTree(3)\n", " bt4 = BinaryTree(4)\n", " bt5 = BinaryTree(5)\n", " bt6 = BinaryTree(6)\n", " bt5a = BinaryTree(\"5a\")\n", " bt5b = BinaryTree(\"5b\")\n", " bt5c = BinaryTree(\"5c\")\n", "\n", " BT.insertLeft(bt1)\n", " BT.insertRight(bt2)\n", "\n", " bt2.insertLeft(bt3)\n", "\n", " bt3.insertLeft(bt4)\n", " bt3.insertRight(bt5)\n", " bt2.insertRight(bt6)\n", " bt1.insertRight(bt5b)\n", " bt1.insertLeft(bt5a)\n", " bt5b.insertRight(bt5c)\n", "\n", " printTree(BT)\n", "\n", " print(\"\\nDelete right branch of 2\")\n", " bt2.deleteRight()\n", " printTree(BT)\n", "\n", " print(\"\\nInsert left branch of 5\")\n", " newN = BinaryTree(\"child of 5\")\n", " bt5.insertLeft(newN)\n", " printTree(BT)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [BinaryTree.py](data_structures/BinaryTree.py)\n", "\n", "Note that in the code above, to delete the right or left subtree you just set the pointer to null. This destroys the whole subtree (more clever things can be done in some cases, especially with generic trees). " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise\n", "\n", "1. Modify the BinaryTree class adding a ```depth``` parameter counting, for each subtree, its depth (i.e. distance from the root of the tree). Note that you have to update properly the depth when inserting a new node. Add a ```getDepth``` and ```setDepth``` method too.\n", "\n", "a. Test the code printing the depth of all the nodes of the binary graph:\n", "\n", "![](images/bintree_2bis.png)\n", "\n", "that can be created with:\n", "\n", "```\n", "BT = BinaryTree(\"Root\")\n", "bt1 = BinaryTree(1)\n", "bt2 = BinaryTree(2)\n", "bt3 = BinaryTree(3)\n", "bt4 = BinaryTree(4)\n", "bt5 = BinaryTree(5)\n", "bt6 = BinaryTree(6)\n", "bt5a = BinaryTree(\"5a\")\n", "bt5b = BinaryTree(\"5b\")\n", "bt5c = BinaryTree(\"5c\")\n", "bt7 = BinaryTree(7)\n", "bt8 = BinaryTree(8)\n", "BT.insertLeft(bt1)\n", "BT.insertRight(bt2)\n", "bt2.insertLeft(bt3)\n", "bt3.insertLeft(bt4)\n", "bt3.insertRight(bt5)\n", "bt2.insertRight(bt6)\n", "bt1.insertRight(bt5b)\n", "bt1.insertLeft(bt5a)\n", "bt5b.insertRight(bt5c)\n", "bt4.insertRight(bt7)\n", "bt4.insertLeft(bt8)\n", "```\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Node Root has depth: 0\n", "Node 1 has depth: 1\n", "Node 2 has depth: 1\n", "Node 3 has depth: 2\n", "Node 4 has depth: 3\n", "Node 5 has depth: 3\n", "Node 5a has depth: 2\n", "Node 5b has depth: 2\n", "Node 5c has depth: 3\n", "Node 6 has depth: 2\n", "Node 7 has depth: 4\n", "Node 8 has depth: 4\n" ] } ], "source": [ "class BinaryTree:\n", " def __init__(self, value):\n", " self.__data = value\n", " self.__right = None\n", " self.__left = None\n", " self.__parent = None\n", " self.__depth = 0 # new param\n", "\n", " def getValue(self):\n", " return self.__data\n", " def setValue(self, newval):\n", " self.__data = newval\n", "\n", " def getParent(self):\n", " return self.__parent\n", " def setParent(self, tree):\n", " self.__parent = tree\n", "\n", " def getRight(self):\n", " return self.__right\n", " def getLeft(self):\n", " return self.__left\n", "\n", " # new method\n", " def getDepth(self):\n", " return self.__depth\n", " # new method\n", " def setDepth(self, newdepth):\n", " self.__depth = newdepth\n", "\n", "\n", " def insertRight(self, tree):\n", " if self.__right == None:\n", " self.__right = tree\n", " tree.setParent(self)\n", " tree.setDepth(self.getDepth() + 1)\n", "\n", " def insertLeft(self, tree):\n", " if self.__left == None:\n", " self.__left = tree\n", " tree.setParent(self)\n", " tree.setDepth(self.getDepth() + 1)\n", "\n", " def deleteRight(self):\n", " self.__right = None\n", "\n", " def deleteLeft(self):\n", " self.__left = None\n", "\n", "\n", "\n", "def printTree(root):\n", " cur = root\n", " #each element is a node and a depth\n", " #depth is used to format prints (with tabs)\n", " nodes = [(cur,0)]\n", " tabs = \"\"\n", " lev = 0\n", " while len(nodes) >0:\n", " cur, lev = nodes.pop(-1)\n", " #print(\"{}{}\".format(\"\\t\"*lev, cur.getValue()))\n", " if cur.getRight() != None:\n", " print (\"{}{} (r)-> {}\".format(\"\\t\"*lev,\n", " cur.getValue(),\n", " cur.getRight().getValue()))\n", " nodes.append((cur.getRight(), lev+1))\n", " if cur.getLeft() != None:\n", " print (\"{}{} (l)-> {}\".format(\"\\t\"*lev,\n", " cur.getValue(),\n", " cur.getLeft().getValue()))\n", " nodes.append((cur.getLeft(), lev+1))\n", "\n", "if __name__ == \"__main__\":\n", " BT = BinaryTree(\"Root\")\n", " bt1 = BinaryTree(1)\n", " bt2 = BinaryTree(2)\n", " bt3 = BinaryTree(3)\n", " bt4 = BinaryTree(4)\n", " bt5 = BinaryTree(5)\n", " bt6 = BinaryTree(6)\n", " bt5a = BinaryTree(\"5a\")\n", " bt5b = BinaryTree(\"5b\")\n", " bt5c = BinaryTree(\"5c\")\n", " bt7 = BinaryTree(7)\n", " bt8 = BinaryTree(8)\n", " BT.insertLeft(bt1)\n", " BT.insertRight(bt2)\n", " bt2.insertLeft(bt3)\n", " bt3.insertLeft(bt4)\n", " bt3.insertRight(bt5)\n", " bt2.insertRight(bt6)\n", " bt1.insertRight(bt5b)\n", " bt1.insertLeft(bt5a)\n", " bt5b.insertRight(bt5c)\n", " bt4.insertRight(bt7)\n", " bt4.insertLeft(bt8)\n", "\n", " nodeList = [BT,bt1,bt2,bt3,bt4, bt5, bt5a, bt5b,\n", " bt5c, bt6, bt7, bt8]\n", " for node in nodeList:\n", " if node != None:\n", " print(\"Node {} has depth: {}\".format(node.getValue(),\n", " node.getDepth()))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [BinaryTree2.py](data_structures/BinaryTree2.py)\n", "
\n", "\n", "## Tree visit\n", "\n", "Now we can see how to perform some *visits* of the trees, that is going through the nodes following the connections. \n", "In particular, there are two different types of visits: **depth first** and **breadth first** search.\n", "\n", "### Binary Tree visits: DFS\n", "\n", "Given a tree T, depth first search (DFS) visits all the subtrees of T going as deep as it can before going back and down another branch until all the tree is visited.\n", "\n", "DFS requires a stack and can be implemented recursively. What we do with the root during the visit defines 3 different types of visits:\n", "\n", "1. the root is visited before the visiting the subtree : **pre-order**;\n", "\n", "2. the root is visited after the left subtree but before the right subtree : **in-order**;\n", "\n", "3. the root is visited after the left and right subtrees : **post-order**. \n", "\n", "\n", "![](images/treevisit_DFS.png)\n", "\n", "Depth-first traversal (dotted path) of a binary tree:\n", "\n", "1. Pre-order (node visited at position red): F, B, A, D, C, E, G, I, H; \n", "\n", "2. In-order (node visited at position green): A, B, C, D, E, F, G, H, I;\n", "\n", "3. Post-order (node visited at position blue): A, C, E, D, B, H, I, G, F.\n", "\n", "\n", "**Example:** Let's implement the three versions of DFS and apply them to the binary tree seen above." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Root (r)-> 2\n", "Root (l)-> 1\n", "\t1 (r)-> 5b\n", "\t1 (l)-> 5a\n", "\t\t5b (r)-> 5c\n", "\t2 (r)-> 6\n", "\t2 (l)-> 3\n", "\t\t3 (r)-> 5\n", "\t\t3 (l)-> 4\n", "Pre-order DFS:\n", "Root\n", "1\n", "5a\n", "5b\n", "5c\n", "2\n", "3\n", "4\n", "5\n", "6\n", "\n", "In-order DFS:\n", "5a\n", "1\n", "5b\n", "5c\n", "Root\n", "4\n", "3\n", "5\n", "2\n", "6\n", "\n", "Post-order DFS:\n", "5a\n", "5c\n", "5b\n", "1\n", "4\n", "5\n", "3\n", "6\n", "2\n", "Root\n" ] } ], "source": [ "class BinaryTree:\n", " def __init__(self, value):\n", " self.__data = value\n", " self.__right = None\n", " self.__left = None\n", " self.__parent = None\n", "\n", " def getValue(self):\n", " return self.__data\n", " def setValue(self, newValue):\n", " self.__data = newValue\n", "\n", " def getParent(self):\n", " return self.__parent\n", " def setParent(self, tree):\n", " self.__parent = tree\n", "\n", " def getRight(self):\n", " return self.__right\n", " def getLeft(self):\n", " return self.__left\n", "\n", " def insertRight(self, tree):\n", " if self.__right == None:\n", " self.__right = tree\n", " tree.setParent(self)\n", " def insertLeft(self, tree):\n", " if self.__left == None:\n", " self.__left = tree\n", " tree.setParent(self)\n", "\n", " def deleteRight(self):\n", " self.__right = None\n", " def deleteLeft(self):\n", " self.__left = None\n", "\n", " def preOrderDFS(self):\n", " if self != None:\n", " r = self.getRight()\n", " l = self.getLeft()\n", " print(self.getValue()) # print before recursive calls!\n", " if l != None:\n", " l.preOrderDFS()\n", " if r != None:\n", " r.preOrderDFS()\n", "\n", " def inOrderDFS(self):\n", " if self != None:\n", " r = self.getRight()\n", " l = self.getLeft()\n", " if l != None:\n", " l.inOrderDFS()\n", " print(self.getValue()) # print in the between the recursive calls!\n", " if r != None:\n", " r.inOrderDFS()\n", "\n", " def postOrderDFS(self):\n", " if self != None:\n", " r = self.getRight()\n", " l = self.getLeft()\n", " if l != None:\n", " l.postOrderDFS()\n", " if r != None:\n", " r.postOrderDFS()\n", " print(self.getValue()) # print after the recursive calls!\n", "\n", "def printTree(root):\n", " cur = root\n", " #each element is a node and a depth\n", " #depth is used to format prints (with tabs)\n", " nodes = [(cur,0)]\n", " tabs = \"\"\n", " lev = 0\n", " while len(nodes) >0:\n", " cur, lev = nodes.pop(-1)\n", " #print(\"{}{}\".format(\"\\t\"*lev, cur.getValue()))\n", " if cur.getRight() != None:\n", " print (\"{}{} (r)-> {}\".format(\"\\t\"*lev,\n", " cur.getValue(),\n", " cur.getRight().getValue()))\n", " nodes.append((cur.getRight(), lev+1))\n", " if cur.getLeft() != None:\n", " print (\"{}{} (l)-> {}\".format(\"\\t\"*lev,\n", " cur.getValue(),\n", " cur.getLeft().getValue()))\n", " nodes.append((cur.getLeft(), lev+1))\n", "\n", "if __name__ == \"__main__\":\n", " BT = BinaryTree(\"Root\")\n", " bt1 = BinaryTree(1)\n", " bt2 = BinaryTree(2)\n", " bt3 = BinaryTree(3)\n", " bt4 = BinaryTree(4)\n", " bt5 = BinaryTree(5)\n", " bt6 = BinaryTree(6)\n", " bt5a = BinaryTree(\"5a\")\n", " bt5b = BinaryTree(\"5b\")\n", " bt5c = BinaryTree(\"5c\")\n", "\n", " BT.insertLeft(bt1)\n", " BT.insertRight(bt2)\n", " \n", " bt2.insertLeft(bt3)\n", " \n", " bt3.insertLeft(bt4)\n", " bt3.insertRight(bt5)\n", " bt2.insertRight(bt6)\n", " bt1.insertRight(bt5b)\n", " bt1.insertLeft(bt5a)\n", " bt5b.insertRight(bt5c)\n", "\n", " printTree(BT)\n", " \n", " print(\"Pre-order DFS:\")\n", " BT.preOrderDFS()\n", " print(\"\\nIn-order DFS:\")\n", " BT.inOrderDFS()\n", " print(\"\\nPost-order DFS:\")\n", " BT.postOrderDFS()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [BinaryTreeDFSVisits.py](data_structures/BinaryTreeDFSVisits.py)\n", "\n", "Compare the results above with the graph:\n", "\n", "![](images/bintree_2.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Binary Tree visits: BFS\n", "\n", "**Breadth first search** visits all the higher levels of a tree before going down. Basically, this search goes as wide as it can before going deep.\n", "\n", "This visit makes use of a queue: for each tree, it adds the left and right subtrees to the queue and recursively visits them in the order they have been pushed into the queue.\n", "\n", "As said, implementations of BFS make use of a FIFO queue. In Python, we can use the efficient ```deque``` data structure that is implemented in the ```collections``` module (remember to import it first with ```from collections import deque``` and use ```deque.append``` to add at the end and ```deque.popleft``` to remove from the beginning).\n", "\n", "**Example:** Let's implement a BFS method and apply it to binary tree seen above. " ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Root (r)-> 2\n", "Root (l)-> 1\n", "\t1 (r)-> 5b\n", "\t1 (l)-> 5a\n", "\t\t5b (r)-> 5c\n", "\t2 (r)-> 6\n", "\t2 (l)-> 3\n", "\t\t3 (r)-> 5\n", "\t\t3 (l)-> 4\n", "BFS:\n", "Root\n", "1\n", "2\n", "5a\n", "5b\n", "3\n", "6\n", "5c\n", "4\n", "5\n" ] } ], "source": [ "from collections import deque\n", "\n", "class BinaryTree:\n", " def __init__(self, value):\n", " self.__data = value\n", " self.__right = None\n", " self.__left = None\n", " self.__parent = None\n", "\n", " def getValue(self):\n", " return self.__data\n", " def setValue(self, newValue):\n", " self.__data = newValue\n", "\n", " def getParent(self):\n", " return self.__parent\n", " def setParent(self, tree):\n", " self.__parent = tree\n", "\n", " def getRight(self):\n", " return self.__right\n", " def getLeft(self):\n", " return self.__left\n", "\n", " def insertRight(self, tree):\n", " if self.__right == None:\n", " self.__right = tree\n", " tree.setParent(self)\n", " def insertLeft(self, tree):\n", " if self.__left == None:\n", " self.__left = tree\n", " tree.setParent(self)\n", "\n", " def deleteRight(self):\n", " self.__right = None\n", " def deleteLeft(self):\n", " self.__left = None\n", "\n", " def BFS(self):\n", " if self != None:\n", " level = deque()\n", " level.append(self)\n", "\n", " while len(level) > 0:\n", " #print(len(level))\n", " cur = level.popleft()\n", " print(cur.getValue())\n", " r = cur.getRight()\n", " l = cur.getLeft()\n", " if l != None:\n", " #print(\"from {} Appending: {}\".format(cur.getValue(),\n", " # l.getValue()))\n", " level.append(l)\n", " if r != None:\n", " level.append(r)\n", " #print(\"from {} Appending: {}\".format(cur.getValue(),\n", " # r.getValue()))\n", "\n", "def printTree(root):\n", " cur = root\n", " #each element is a node and a depth\n", " #depth is used to format prints (with tabs)\n", " nodes = [(cur,0)]\n", " tabs = \"\"\n", " lev = 0\n", " while len(nodes) >0:\n", " cur, lev = nodes.pop(-1)\n", " #print(\"{}{}\".format(\"\\t\"*lev, cur.getValue()))\n", " if cur.getRight() != None:\n", " print (\"{}{} (r)-> {}\".format(\"\\t\"*lev,\n", " cur.getValue(),\n", " cur.getRight().getValue()))\n", " nodes.append((cur.getRight(), lev+1))\n", " if cur.getLeft() != None:\n", " print (\"{}{} (l)-> {}\".format(\"\\t\"*lev,\n", " cur.getValue(),\n", " cur.getLeft().getValue()))\n", " nodes.append((cur.getLeft(), lev+1))\n", "\n", "if __name__ == \"__main__\":\n", " BT = BinaryTree(\"Root\")\n", " bt1 = BinaryTree(1)\n", " bt2 = BinaryTree(2)\n", " bt3 = BinaryTree(3)\n", " bt4 = BinaryTree(4)\n", " bt5 = BinaryTree(5)\n", " bt6 = BinaryTree(6)\n", " bt5a = BinaryTree(\"5a\")\n", " bt5b = BinaryTree(\"5b\")\n", " bt5c = BinaryTree(\"5c\")\n", "\n", " BT.insertLeft(bt1)\n", " BT.insertRight(bt2)\n", " bt2.insertLeft(bt3)\n", " bt3.insertLeft(bt4)\n", " bt3.insertRight(bt5)\n", " bt2.insertRight(bt6)\n", " bt1.insertRight(bt5b)\n", " bt1.insertLeft(bt5a)\n", " bt5b.insertRight(bt5c)\n", "\n", " printTree(BT)\n", " \n", " print(\"BFS:\")\n", " BT.BFS()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [BinaryTreeBFSVisit.py](data_structures/BinaryTreeBFSVisit.py)\n", "\n", "\n", "Compare the results above with the graph:\n", "\n", "![](images/bintree_2.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercises\n", "\n", "2. The width of a binary tree T is the largest number of nodes that belong to the same level. The minimal height of a binary tree T is the minimal distance between the root and its closest leaf in its subtree. This distance is counted in number of nodes.\n", "\n", "Given the BinaryTree defined above:\n", "\n", "a. Write a function ```getWidth(T)``` that given a tree T, returns the width of T. Hint: *get all nodes at each level and count them*. \n", "\n", "b. Write a function ```getMinHeight(T)``` that given a tree T, returns the minimal height of T (in number of nodes). Hint: *stop at first level with a leaf (similar to previous function)*.\n", "\n", "c. Write a function ```nodesAtLevel(T,k)``` that given a binary tree T and an integer k, returns the nodes at level k.\n", "\n", "Test the functions with the following binary graph:\n", "\n", "![](images/bintree_2tris.png)\n", "\n", "that can be created with:\n", "\n", "```python\n", "BT = BinaryTree(\"Root\")\n", "bt1 = BinaryTree(1)\n", "bt2 = BinaryTree(2)\n", "bt3 = BinaryTree(3)\n", "bt4 = BinaryTree(4)\n", "bt5 = BinaryTree(5)\n", "bt6 = BinaryTree(6)\n", "bt5a = BinaryTree(\"5a\")\n", "bt5b = BinaryTree(\"5b\")\n", "bt5c = BinaryTree(\"5c\")\n", "bt7 = BinaryTree(7)\n", "bt8 = BinaryTree(8)\n", "bt9 = BinaryTree(9)\n", "bt10 = BinaryTree(10)\n", "BT.insertLeft(bt1)\n", "BT.insertRight(bt2)\n", "bt2.insertLeft(bt3)\n", "bt3.insertLeft(bt4)\n", "bt3.insertRight(bt5)\n", "bt2.insertRight(bt6)\n", "bt1.insertRight(bt5b)\n", "bt1.insertLeft(bt5a)\n", "bt5b.insertRight(bt5c)\n", "bt4.insertRight(bt7)\n", "bt4.insertLeft(bt8)\n", "bt6.insertRight(bt10)\n", "bt6.insertLeft(bt9)\n", "```\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The width of BT is 5\n", "The minimum height of BT is 3\n", "Nodes at level 0: ['Root']\n", "Nodes at level 1: [1, 2]\n", "Nodes at level 2: ['5a', '5b', 3, 6]\n", "Nodes at level 3: ['5c', 4, 5, 9, 10]\n", "Nodes at level 4: [8, 7]\n", "Nodes at level 5: None\n", "The minimum height of BT is 3\n", "Deleting 5ca\n", "The minimum height of BT is 4\n", "Adding 5d as left child of 5c\n", "The minimum height of BT is 4\n" ] } ], "source": [ "class BinaryTree:\n", " def __init__(self, value):\n", " self.__data = value\n", " self.__right = None\n", " self.__left = None\n", " self.__parent = None\n", " self.__depth = 0 #new param\n", "\n", " # new method\n", " def getDepth(self):\n", " return self.__depth\n", " # new method\n", " def setDepth(self, newdepth):\n", " self.__depth = newdepth\n", "\n", " def getValue(self):\n", " return self.__data\n", " def setValue(self, newValue):\n", " self.__data = newValue\n", "\n", " def getParent(self):\n", " return self.__parent\n", " def setParent(self, tree):\n", " self.__parent = tree\n", "\n", " def getRight(self):\n", " return self.__right\n", " def getLeft(self):\n", " return self.__left\n", "\n", " def insertRight(self, tree):\n", " if self.__right == None:\n", " self.__right = tree\n", " tree.setParent(self)\n", " tree.setDepth(self.getDepth() + 1)\n", " def insertLeft(self, tree):\n", " if self.__left == None:\n", " self.__left = tree\n", " tree.setDepth(self.getDepth() + 1)\n", " tree.setParent(self)\n", "\n", " def deleteRight(self):\n", " self.__right = None\n", " def deleteLeft(self):\n", " self.__left = None\n", "\n", "def getWidth(tree):\n", " \"\"\"gets the width of the tree\"\"\"\n", " if tree == None:\n", " return 0\n", "\n", " level = [tree]\n", " res = 1\n", " while len(level) > 0:\n", " tmp = []\n", " for t in level:\n", " r = t.getRight()\n", " l = t.getLeft()\n", " if r != None:\n", " tmp.append(r)\n", " if l != None:\n", " tmp.append(l)\n", " res = max(res,len(tmp))\n", " level = tmp\n", "\n", " return res\n", "\n", "def getMinHeight(tree):\n", " \"\"\"gets the minimum height of the tree in nodes\"\"\"\n", " if tree == None:\n", " return 0\n", "\n", " level = [tree]\n", " res = 1\n", " while len(level) > 0:\n", " tmp = []\n", " for t in level:\n", " r = t.getRight()\n", " l = t.getLeft()\n", " if r == None and l == None:\n", " return res\n", " else:\n", " if r != None:\n", " tmp.append(r)\n", " if l != None:\n", " tmp.append(l)\n", " level = tmp\n", " res += 1\n", " return res\n", "\n", "def nodesAtLevel(tree,k):\n", " \"\"\"returns the nodes at level k\"\"\"\n", " if tree == None:\n", " return 0\n", "\n", " level = [tree]\n", " cnt = 0\n", " while cnt != k and len(level) > 0:\n", " tmp = []\n", " for t in level:\n", " r = t.getRight()\n", " l = t.getLeft()\n", " if l != None:\n", " tmp.append(l)\n", " if r != None:\n", " tmp.append(r)\n", "\n", " level = tmp\n", " cnt += 1\n", " if len(level) == 0:\n", " return None\n", " else:\n", " vals = [x.getValue() for x in level if x != None]\n", " return vals\n", "\n", "if __name__ == \"__main__\":\n", " BT = BinaryTree(\"Root\")\n", " bt1 = BinaryTree(1)\n", " bt2 = BinaryTree(2)\n", " bt3 = BinaryTree(3)\n", " bt4 = BinaryTree(4)\n", " bt5 = BinaryTree(5)\n", " bt6 = BinaryTree(6)\n", " bt5a = BinaryTree(\"5a\")\n", " bt5b = BinaryTree(\"5b\")\n", " bt5c = BinaryTree(\"5c\")\n", " bt7 = BinaryTree(7)\n", " bt8 = BinaryTree(8)\n", " bt9 = BinaryTree(9)\n", " bt10 = BinaryTree(10)\n", " BT.insertLeft(bt1)\n", " BT.insertRight(bt2)\n", " bt2.insertLeft(bt3)\n", " bt3.insertLeft(bt4)\n", " bt3.insertRight(bt5)\n", " bt2.insertRight(bt6)\n", " bt1.insertRight(bt5b)\n", " bt1.insertLeft(bt5a)\n", " bt5b.insertRight(bt5c)\n", " bt4.insertRight(bt7)\n", " bt4.insertLeft(bt8)\n", " bt6.insertRight(bt10)\n", " bt6.insertLeft(bt9)\n", "\n", " print(\"The width of BT is {}\".format(getWidth(BT)))\n", " print(\"The minimum height of BT is {}\".format(getMinHeight(BT)))\n", " for i in range(0,6):\n", " print(\"Nodes at level {}: {}\".format(i,nodesAtLevel(BT,i)))\n", " print(\"The minimum height of BT is {}\".format(getMinHeight(BT)))\n", " bt1.deleteLeft()\n", " print(\"Deleting 5ca\")\n", " print(\"The minimum height of BT is {}\".format(getMinHeight(BT)))\n", " bt5d = BinaryTree(\"5d\")\n", " bt5c.insertLeft(bt5d)\n", " print(\"Adding 5d as left child of 5c\")\n", " print(\"The minimum height of BT is {}\".format(getMinHeight(BT)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [BinaryTree3.py](data_structures/BinaryTree3.py)\n", "
\n", "\n", "3. Given the BinaryTree used so far, implement a ```getCommonAncestor(n1,n2)``` method that gets the common ancestor between the two nodes n1 and n2. \n", "\n", "![](images/bintree_2tris.png)\n", "\n", "For example, considering the graph above: \n", "\n", "```\n", "getCommonAncestor(7,5) = 3\n", "getCommonAncestor(7,10) = 2\n", "getCommonAncestor(8,5b) = Root\n", "``` \n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The CA between 7 and 5 is: 3\n", "The CA between 7 and 10 is: 2\n", "The CA between 7 and 8 is: 4\n", "The CA between 5b and 8 is: Root\n" ] } ], "source": [ "class BinaryTree:\n", " def __init__(self, value):\n", " self.__data = value\n", " self.__right = None\n", " self.__left = None\n", " self.__parent = None\n", " self.__depth = 0 #new param\n", " \n", " # new method\n", " def getDepth(self):\n", " return self.__depth\n", " # new method\n", " def setDepth(self, newdepth):\n", " self.__depth = newdepth\n", " \n", " def getValue(self):\n", " return self.__data\n", " def setValue(self, newValue):\n", " self.__data = newValue\n", " \n", " def getParent(self):\n", " return self.__parent\n", " def setParent(self, tree):\n", " self.__parent = tree\n", " \n", " def getRight(self):\n", " return self.__right\n", " def getLeft(self):\n", " return self.__left\n", " \n", " def insertRight(self, tree):\n", " if self.__right == None:\n", " self.__right = tree\n", " tree.setParent(self)\n", " #line modified\n", " tree.setDepth(self.getDepth() + 1) \n", " def insertLeft(self, tree):\n", " if self.__left == None:\n", " self.__left = tree\n", " #line modified\n", " tree.setDepth(self.getDepth() + 1)\n", " tree.setParent(self)\n", " \n", " def deleteRight(self):\n", " self.__right = None \n", " def deleteLeft(self):\n", " self.__left = None\n", " \n", "def getCommonAncestor(node1, node2):\n", " if node1 == node2:\n", " return node1\n", " \n", " if node1 == None or node2 == None:\n", " return None\n", " \n", " n1anc = set()\n", " n1anc.add(node1)\n", " \n", " anc = node1.getParent()\n", " while anc != None:\n", " n1anc.add(anc)\n", " anc = anc.getParent()\n", " \n", " anc = node2\n", " while anc != None:\n", " if anc in n1anc:\n", " return anc\n", " else:\n", " anc = anc.getParent()\n", " \n", "if __name__ == \"__main__\":\n", " BT = BinaryTree(\"Root\")\n", " bt1 = BinaryTree(1)\n", " bt2 = BinaryTree(2)\n", " bt3 = BinaryTree(3)\n", " bt4 = BinaryTree(4)\n", " bt5 = BinaryTree(5)\n", " bt6 = BinaryTree(6)\n", " bt5a = BinaryTree(\"5a\")\n", " bt5b = BinaryTree(\"5b\")\n", " bt5c = BinaryTree(\"5c\")\n", " bt7 = BinaryTree(7)\n", " bt8 = BinaryTree(8)\n", " bt9 = BinaryTree(9)\n", " bt10 = BinaryTree(10)\n", " BT.insertLeft(bt1)\n", " BT.insertRight(bt2)\n", " bt2.insertLeft(bt3)\n", " bt3.insertLeft(bt4)\n", " bt3.insertRight(bt5)\n", " bt2.insertRight(bt6)\n", " bt1.insertRight(bt5b)\n", " bt1.insertLeft(bt5a)\n", " bt5b.insertRight(bt5c)\n", " bt4.insertRight(bt7)\n", " bt4.insertLeft(bt8)\n", " bt6.insertRight(bt10)\n", " bt6.insertLeft(bt9)\n", " \n", " ca = getCommonAncestor(bt7,bt5)\n", " if ca != None:\n", " ca = ca.getValue()\n", " print(\"The CA between {} and {} is: {}\".format(bt7.getValue(),\n", " bt5.getValue(),\n", " ca))\n", " ca = getCommonAncestor(bt7,bt10)\n", " if ca != None:\n", " ca = ca.getValue()\n", " print(\"The CA between {} and {} is: {}\".format(bt7.getValue(),\n", " bt10.getValue(),\n", " ca))\n", " ca = getCommonAncestor(bt7,bt8)\n", " if ca != None:\n", " ca = ca.getValue()\n", " print(\"The CA between {} and {} is: {}\".format(bt7.getValue(),\n", " bt8.getValue(),\n", " ca))\n", " \n", " ca = getCommonAncestor(bt5b,bt8)\n", " if ca != None:\n", " ca = ca.getValue()\n", " print(\"The CA between {} and {} is: {}\".format(bt5b.getValue(),\n", " bt8.getValue(),\n", " ca))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [BinaryTree4.py](data_structures/BinaryTree4.py)\n", "
\n", "\n", "4. A Binary Search Tree is a binary tree with the following properties:\n", "\n", "- The *left* subtree of a node contains only nodes with values lower than that of the node.\n", "- The *right* subtree of a node contains only nodes with values greater than the node’s.\n", "- No duplicate nodes are allowed.\n", "\n", "\n", "Implement: \n", "\n", "1. a function ```BST = createBST(inList)``` that gets a list of integers (or strings) and returns a BinaryTree that is a Binary Search Tree;\n", "\n", "2. a search function ```searchBST(BST, element)``` that gets an integer (or string) and checks if it is present in the Binary Search Tree.\n", "\n", "3. modify the ```inOrderDFS(self)``` method to return a list of visited nodes using in-order depth first search. Test the method by printing the first 100 elements to show that they are actually sorted (this is a sorting algorithm indeed!); \n", "\n", "Test the code with the following ```intList```:\n", "\n", "```\n", "import random\n", "intList = []\n", "for i in range(1000):\n", " inList.append(random.randint(0,10000))\n", "```\n", "\n", "
Show/Hide Solution\n", "\n", "\n", "NOTE: This solution shows you how to plot a graph (makes use of pygraphviz, which is an off-topic for this course, go [here](https://pygraphviz.github.io) for details). You can see a sample output of the plot here [BST_test.png](images/BST_test.png)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "el 87 : present? True\n", "el 24 : present? False\n", "el 22 : present? False\n", "el 67 : present? False\n", "el 76 : present? False\n", "el 10 : present? False\n", "el 58 : present? False\n", "el 71 : present? False\n", "el 90 : present? False\n", "el 16 : present? False\n", "el 96 : present? False\n", "el 52 : present? False\n", "el 36 : present? False\n", "el 39 : present? False\n", "el 90 : present? False\n", "el 82 : present? False\n", "el 48 : present? False\n", "el 94 : present? False\n", "el 25 : present? False\n", "el 33 : present? False\n", "el 61 : present? False\n", "el 0 : present? False\n", "el 90 : present? False\n", "el 46 : present? False\n", "el 31 : present? False\n", "el 38 : present? False\n", "el 25 : present? False\n", "el 4 : present? False\n", "el 62 : present? False\n", "el 100 : present? False\n", "el 34 : present? False\n", "el 92 : present? False\n", "el 14 : present? False\n", "el 13 : present? False\n", "el 69 : present? True\n", "el 65 : present? False\n", "el 8 : present? False\n", "el 58 : present? False\n", "el 26 : present? False\n", "el 48 : present? False\n", "el 4 : present? False\n", "el 63 : present? False\n", "el 2 : present? True\n", "el 76 : present? False\n", "el 51 : present? False\n", "el 76 : present? False\n", "el 13 : present? False\n", "el 18 : present? False\n", "el 24 : present? False\n", "el 18 : present? False\n", "el 80 : present? False\n", "el 14 : present? False\n", "el 27 : present? False\n", "el 76 : present? False\n", "el 40 : present? True\n", "el 74 : present? False\n", "el 3 : present? False\n", "el 9 : present? False\n", "el 91 : present? False\n", "el 82 : present? False\n", "el 85 : present? False\n", "el 50 : present? False\n", "el 36 : present? False\n", "el 100 : present? False\n", "el 44 : present? False\n", "el 27 : present? False\n", "el 40 : present? True\n", "el 55 : present? False\n", "el 46 : present? False\n", "el 31 : present? False\n", "el 4 : present? False\n", "el 23 : present? False\n", "el 17 : present? False\n", "el 55 : present? False\n", "el 63 : present? False\n", "el 69 : present? True\n", "el 21 : present? False\n", "el 74 : present? False\n", "el 13 : present? False\n", "el 52 : present? False\n", "el 1 : present? False\n", "el 0 : present? False\n", "el 57 : present? False\n", "el 63 : present? False\n", "el 59 : present? False\n", "el 32 : present? True\n", "el 85 : present? False\n", "el 37 : present? False\n", "el 100 : present? False\n", "el 62 : present? False\n", "el 19 : present? False\n", "el 90 : present? False\n", "el 59 : present? False\n", "el 60 : present? False\n", "el 80 : present? False\n", "el 97 : present? False\n", "el 65 : present? False\n", "el 31 : present? False\n", "el 62 : present? False\n", "el 86 : present? False\n", "\n", "In order DFS (first 100 elements):\n", "[2, 32, 40, 41, 56, 69, 72, 83, 87, 88, 98, 108, 111, 126, 129, 142, 224, 231, 240, 257, 259, 260, 275, 278, 281, 283, 297, 298, 307, 319, 336, 340, 351, 376, 383, 393, 402, 408, 423, 428, 431, 440, 463, 498, 511, 517, 520, 525, 532, 558, 569, 595, 597, 600, 617, 626, 630, 637, 652, 659, 672, 715, 717, 736, 744, 747, 765, 779, 796, 798, 802, 813, 832, 837, 841, 855, 872, 896, 912, 916, 928, 942, 963, 973, 994, 1002, 1013, 1015, 1017, 1035, 1047, 1061, 1069, 1078, 1081, 1088, 1090, 1093, 1094, 1098]\n" ] } ], "source": [ "class BinarySearchTree:\n", " def __init__(self, value):\n", " self.__data = value\n", " self.__right = None\n", " self.__left = None\n", " self.__parent = None\n", " self.__depth = 0 #new param\n", " \n", " # new method\n", " def getDepth(self):\n", " return self.__depth \n", " # new method\n", " def setDepth(self, newdepth):\n", " self.__depth = newdepth\n", "\n", " def getValue(self):\n", " return self.__data\n", " def setValue(self, newValue):\n", " self.__data = newValue\n", " \n", " def getParent(self):\n", " return self.__parent\n", " def setParent(self, tree):\n", " self.__parent = tree\n", " \n", " def getRight(self):\n", " return self.__right\n", " def getLeft(self):\n", " return self.__left\n", " \n", " def insertRight(self, tree):\n", " if self.__right == None:\n", " self.__right = tree\n", " tree.setParent(self)\n", " #line modified\n", " tree.setDepth(self.getDepth() + 1) \n", " def insertLeft(self, tree):\n", " if self.__left == None:\n", " self.__left = tree\n", " #line modified\n", " tree.setDepth(self.getDepth() + 1)\n", " tree.setParent(self)\n", " \n", " def deleteRight(self):\n", " self.__right = None \n", " def deleteLeft(self):\n", " self.__left = None\n", " \n", " def inOrderDFS(self):\n", " ret = []\n", " if self != None:\n", " r = self.getRight()\n", " l = self.getLeft()\n", " if l != None:\n", " ret.extend(l.inOrderDFS())\n", " ret.append(self.getValue())\n", " \n", " if r != None:\n", " ret.extend(r.inOrderDFS())\n", " return ret\n", "\n", "def createBST(intList):\n", " BST = None\n", " if len(intList) > 0:\n", " BST = BinarySearchTree(intList[0])\n", " for el in intList[1:]:\n", " cur_el = BST\n", " alreadyPresent = False\n", " prev_el = None\n", " while cur_el != None:\n", " prev_el = cur_el\n", " cv = cur_el.getValue()\n", " if cv > el:\n", " cur_el = cur_el.getLeft()\n", " elif cv < el:\n", " cur_el = cur_el.getRight()\n", " else:\n", " # cv == el (el is already present)\n", " # not allowed by rule c, so skip it\n", " alreadyPresent = True\n", " #print(\"El {} already present\".format(el))\n", " break\n", " \n", " if not alreadyPresent:\n", " node = BinarySearchTree(el)\n", " node.setParent(prev_el)\n", " if prev_el.getValue() > el:\n", " prev_el.insertLeft(node)\n", " else:\n", " prev_el.insertRight(node)\n", " \n", " return BST\n", " \n", "def searchBST(BST, element):\n", " if BST == None or element == None:\n", " return False\n", " else:\n", " cur_el = BST\n", " while cur_el != None:\n", " if cur_el.getValue() == element:\n", " return True\n", " else:\n", " if cur_el.getValue()> element:\n", " cur_el = cur_el.getLeft()\n", " else:\n", " cur_el = cur_el.getRight()\n", " \n", " return False\n", "\n", "\n", "def printTree(root):\n", " cur = root\n", " #each element is a node and a depth\n", " #depth is used to format prints (with tabs)\n", " nodes = [(cur,0)]\n", " tabs = \"\"\n", " lev = 0\n", " while len(nodes) >0:\n", " cur, lev = nodes.pop(-1)\n", " #print(\"{}{}\".format(\"\\t\"*lev, cur.getValue()))\n", " if cur.getRight() != None:\n", " print (\"{}{} (r)-> {}\".format(\"\\t\"*lev, \n", " cur.getValue(), \n", " cur.getRight().getValue()))\n", " nodes.append((cur.getRight(), lev+1))\n", " if cur.getLeft() != None:\n", " print (\"{}{} (l)-> {}\".format(\"\\t\"*lev, \n", " cur.getValue(), \n", " cur.getLeft().getValue()))\n", " nodes.append((cur.getLeft(), lev+1))\n", "\n", "def plotGraph(tree): \n", " #uses pygraphviz \n", " G=pgv.AGraph(directed=True)\n", " \n", " levels = [tree]\n", " while len(levels) > 0:\n", " cur_n = levels.pop()\n", " if cur_n != None:\n", " G.add_node(cur_n.getValue(), color = 'black')\n", " r = cur_n.getRight()\n", " l = cur_n.getLeft()\n", " if l != None:\n", " G.add_node(l.getValue(), color = 'black')\n", " G.add_edge(cur_n.getValue(), l.getValue())\n", " levels.append(l)\n", " if r != None:\n", " G.add_node(r.getValue(), color = 'black')\n", " G.add_edge(cur_n.getValue(), r.getValue())\n", " levels.append(r)\n", " G.layout(prog='dot') # use dot\n", " #In the following, the path of the graph. Change\n", " #it to your liking\n", " G.draw('images/BST_test.png')\n", " \n", "if __name__ == \"__main__\":\n", " import random\n", " #import pygraphviz as pgv\n", " #import time \n", " inList = []\n", " for i in range(1000):\n", " inList.append(random.randint(0,10000))\n", " \n", " BST = createBST(inList)\n", " \n", " #printTree(BST)\n", " #plotGraph(BST)\n", " for i in range(100):\n", " v = random.randint(0,100)\n", " #s_t = time.time()\n", " ok = searchBST(BST, v)\n", " #e_t = time.time()\n", " okL = v in inList\n", " #e_t2 = time.time()\n", " print(\"el {} : present? {}\".format(v, ok))\n", " #print(\"Time BST:{:.6f} list:{:.6f}\".format(e_t - s_t,\n", " # e_t2 - e_t\n", " # ))\n", " assert(ok == okL)\n", " sorted = BST.inOrderDFS()\n", " print(\"\\nIn order DFS (first 100 elements):\")\n", " print(sorted[0:100])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [BinarySearchTree.py](data_structures/BinarySearchTree.py)\n", "
\n", "\n", "## ADT: Generic Tree\n", "\n", "Generic Trees are like binary trees, but **each node can have more than 2 children**. One possible implementation is that each node (that is a subtree in itself) has a **value**, a link to its **parent** and a **list of children**. \n", "\n", "Another implementation is that each node has a **value**, a link to its **parent**, a link to its **next sibling** and a link to its **first child**:\n", "\n", "![](images/genericTreePointers.png)\n", "\n", "We will be using this latter implementation of the tree.\n", "\n", "The **Generic Tree ADT** seen at lecture follows:\n", "\n", "![](images/genericTreeADT.png)\n", "\n", "Given the following generic tree:\n", "\n", "![](images/gentree_1.png)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise (implementation)\n", "5. Implement the ```GenericTree``` class representing the ADT seen above and create the tree in the picture above.\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "from Root adding child --> Fourth\n", "from Root adding child --> Third\n", "from Root adding child --> Second\n", "from Root adding child --> First\n", "from Second adding child --> Sixth\n", "from Second adding child --> Fifth\n", "from Fourth adding child --> Seventh\n", "from Sixth adding child --> Tenth\n", "from Sixth adding child --> Ninth\n", "from Sixth adding child --> Eighth\n", "Node Root:\n", "\t has parent: None\n", "\t has children: First,Second,Third,Fourth\n", "\t has next siblings: \n", "Node First:\n", "\t has parent: Root\n", "\t has children: \n", "\t has next siblings: Second,Third,Fourth\n", "Node Second:\n", "\t has parent: Root\n", "\t has children: Fifth,Sixth\n", "\t has next siblings: Third,Fourth\n", "Node Third:\n", "\t has parent: Root\n", "\t has children: \n", "\t has next siblings: Fourth\n", "Node Fourth:\n", "\t has parent: Root\n", "\t has children: Seventh,Eleventh\n", "\t has next siblings: \n", "Node Fifth:\n", "\t has parent: Second\n", "\t has children: \n", "\t has next siblings: Sixth\n", "Node Sixth:\n", "\t has parent: Second\n", "\t has children: Eighth,Ninth,Tenth\n", "\t has next siblings: \n", "Node Seventh:\n", "\t has parent: Fourth\n", "\t has children: \n", "\t has next siblings: Eleventh\n", "Node Eighth:\n", "\t has parent: Sixth\n", "\t has children: \n", "\t has next siblings: Ninth,Tenth\n", "Node Ninth:\n", "\t has parent: Sixth\n", "\t has children: \n", "\t has next siblings: Tenth\n", "Node Tenth:\n", "\t has parent: Sixth\n", "\t has children: \n", "\t has next siblings: \n", "Node Eleventh:\n", "\t has parent: Fourth\n", "\t has children: \n", "\t has next siblings: \n" ] } ], "source": [ "class GenericTree:\n", " def __init__(self, value):\n", " self.__data = value\n", " self.__parent = None\n", " self.__child = None\n", " self.__sibling = None\n", "\n", " def getValue(self):\n", " return self.__data\n", " def setValue(self,newvalue):\n", " self.__data = newvalue\n", "\n", " def getParent(self):\n", " return self.__parent\n", " def setParent(self, parent):\n", " self.__parent = parent\n", "\n", " def getLeftmostChild(self):\n", " return self.__child\n", "\n", " def getSibling(self):\n", " return self.__sibling\n", " def setSibling(self,sib):\n", " self.__sibling = sib\n", "\n", " def insertSibling(self,sib):\n", " if type(sib) != GenericTree:\n", " raise TypeError(\"parameter sib is not a GenericTree\")\n", " else:\n", " nextS = None\n", " if self.__sibling != None:\n", " nextS = self.__sibling\n", " self.__sibling = sib\n", " sib.setParent(self.getParent())\n", " sib.setSibling(nextS)\n", "\n", " def insertChild(self,child):\n", " if type(child) != GenericTree:\n", " raise TypeError(\"parameter child is not a GenericTree\")\n", " else:\n", " nextC = None\n", " print(\"from {} adding child --> {}\".format(self.getValue(),\n", " child.getValue()))\n", " if self.__child != None:\n", " nextC = self.__child\n", " child.setParent(self)\n", " child.setSibling(nextC)\n", " self.__child = child\n", "\n", " def deleteChild(self):\n", " if self.__child != None:\n", " #moves along the sibling structure of child\n", " self.__child = self.__child.getSibling()\n", "\n", " def deleteSibling(self):\n", " if self.__sibling != None:\n", " #moves along the sibling structure of the sibling\n", " self.__sibling = self.__sibling.getSibling()\n", "\n", "if __name__ == \"__main__\":\n", " g = GenericTree(\"Root\")\n", " g1 = GenericTree(\"First\")\n", " g2 = GenericTree(\"Second\")\n", " g3 = GenericTree(\"Third\")\n", " g4 = GenericTree(\"Fourth\")\n", " g5 = GenericTree(\"Fifth\")\n", " g6 = GenericTree(\"Sixth\")\n", " g7 = GenericTree(\"Seventh\")\n", " g8 = GenericTree(\"Eighth\")\n", " g9 = GenericTree(\"Ninth\")\n", " g10 = GenericTree(\"Tenth\")\n", " g11 = GenericTree(\"Eleventh\")\n", "\n", " #root\n", " g.insertChild(g4)\n", " g.insertChild(g3)\n", " g.insertChild(g2)\n", " g.insertChild(g1)\n", " #second\n", " g2.insertChild(g6)\n", " g2.insertChild(g5)\n", " #fourth\n", " g4.insertChild(g7)\n", " g7.insertSibling(g11)\n", " #sixth\n", " g6.insertChild(g10)\n", " g6.insertChild(g9)\n", " g6.insertChild(g8)\n", "\n", " #let's print some stuff\n", " nodes = [g,g1,g2,g3,g4,g5,g6,g7,g8,g9,g10,g11]\n", " for n in nodes:\n", " print(\"Node {}:\".format(n.getValue()))\n", " par = n.getParent()\n", " if par != None:\n", " par = par.getValue()\n", " print(\"\\t has parent: {}\".format(par))\n", " c = n.getLeftmostChild()\n", " children = []\n", " if c != None:\n", " children.append(c.getValue())\n", " nc = c.getSibling()\n", " while nc != None:\n", " children.append(nc.getValue())\n", " nc = nc.getSibling()\n", " print(\"\\t has children: {}\".format(\",\".join(children)))\n", " s = n.getSibling()\n", " sibs = []\n", " if s != None:\n", " sibs.append(s.getValue())\n", " ns = s.getSibling()\n", " while ns != None:\n", " sibs.append(ns.getValue())\n", " ns = ns.getSibling()\n", " print(\"\\t has next siblings: {}\".format(\",\".join(sibs)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that the sibling list is actually unidirectional therefore \"Second\" does not any way to know that it is on the same level of \"First\". \n", "\n", "Download the complete source file: [GenericTree.py](data_structures/GenericTree.py)\n", "
\n" ] } ], "metadata": { "celltoolbar": "Edit Metadata", "kernelspec": { "display_name": "3.10.14", "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.10.14" } }, "nbformat": 4, "nbformat_minor": 2 }