{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Tutorial 1: General Trees"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"42 2\n",
"3\n"
]
}
],
"source": [
"from functools import reduce\n",
"\n",
"class Tree:\n",
" def __init__(self, key, children=[]):\n",
" self.key = key\n",
" self.children = children\n",
" \n",
" @property\n",
" def nbchildren(self):\n",
" return len(self.children)\n",
" \n",
" @property\n",
" def size(self):\n",
" return reduce(lambda accu, elt : accu + elt.size,\n",
" self.children, 1)\n",
" \n",
" @property\n",
" def height(self):\n",
" return 1 + reduce(lambda accu, elt : max(accu, elt.height),\n",
" self.children, -1)\n",
"\n",
"t = Tree(42, [Tree(1), Tree(2)])\n",
"print(t.key, t.nbchildren)\n",
"print(t.size)\n",
"\n",
"class TreeAsBin:\n",
" def __init__(self, key=None, child=None, sibling=None):\n",
" self.key = key\n",
" self.child = child\n",
" self.sibling = sibling\n",
" \n",
" @property\n",
" def nbchildren(self):\n",
" r = 0\n",
" child = self.child\n",
" while child:\n",
" r += 1\n",
" child = child.sibling\n",
" return r\n",
" \n",
" @property\n",
" def children(self):\n",
" l = []\n",
" child = self.child\n",
" while child:\n",
" l.append(child)\n",
" child = child.sibling\n",
" return l"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from algopy import tree, bintree, treeasbin\n",
"import graphviz\n",
"t = tree.loadtree('files/treetuto-1.tree')\n",
"graphviz.Source(tree.dot(t))"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"11\n",
"3\n"
]
}
],
"source": [
"def size(t):\n",
" s = 1\n",
" for child in t.children:\n",
" s += size(child)\n",
" return s\n",
"\n",
"print(size(t))\n",
"\n",
"def height(t):\n",
" h = -1\n",
" for child in t.children:\n",
" h = max(h, height(child))\n",
" return h + 1\n",
"print(height(t))"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"11 11\n",
"3 3\n"
]
}
],
"source": [
"def size_bin(t):\n",
" s = 1\n",
" child = t.child\n",
" while child:\n",
" s += size_bin(child)\n",
" child = child.sibling\n",
" return s\n",
"\n",
"def size_bin2(t):\n",
" if not t:\n",
" return 0\n",
" return 1 + size_bin2(t.child) + size_bin2(t.sibling)\n",
"\n",
"tbin = treeasbin.tutoEx1()\n",
"print(size_bin(tbin), size_bin2(tbin))\n",
"\n",
"def height_bin(t):\n",
" h = -1\n",
" child = t.child\n",
" while child:\n",
" h = max(h, height_bin(child))\n",
" child = child.sibling\n",
" return h + 1\n",
"\n",
"def height_bin2(t):\n",
" if not t:\n",
" return -1\n",
" return max(1 + height_bin2(t.child), height_bin2(t.sibling))\n",
"\n",
"print(height_bin(tbin), height_bin2(tbin))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15\n",
"15\n",
"15\n"
]
}
],
"source": [
"def epl(t, d=0):\n",
" if not t.children:\n",
" return d\n",
" r = 0\n",
" for child in t.children:\n",
" r += epl(child, d + 1)\n",
" return r\n",
"\n",
"print(epl(t))\n",
"\n",
"def epl_bin(t, d=0):\n",
" if not t.child:\n",
" return d\n",
" r = 0\n",
" child = t.child\n",
" while child:\n",
" r += epl_bin(child, d + 1)\n",
" child = child.sibling\n",
" return r\n",
"\n",
"print(epl_bin(tbin))\n",
"\n",
"def epl_bin2(t, d=0):\n",
" r = d\n",
" if t.child:\n",
" r = epl_bin2(t.child, d + 1)\n",
" if t.sibling:\n",
" r += epl_bin2(t.sibling, d)\n",
" return r\n",
"\n",
"print(epl_bin2(tbin))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## DFS principle:\n",
"\n",
"DFS on a node T is recursive function:\n",
"* if T is a leaf: perform leaf operation and leave\n",
"* Otherwise:\n",
" * perform pre-order operation\n",
" * for each child of T:\n",
" * recursive call on the child\n",
" * do in-between operation\n",
" * perform post-order operation and leave\n",
" \n",
"**Between or after**\n",
"\n",
"Between: 1, 2, 3, 4\n",
"\n",
"After: 1, 2, 3, 4,\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"graphviz.Source(tree.dot(t))"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(15, 3, -6, 10, 8, 11, 0, 4, 2, 5, 9)"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"15, 3, -6, 10, 8, 11, 0, 4, 2, 5, 9\n"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(-6, 10, 3, 0, 4, 11, 2, 5, 8, 9, 15)"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"-6, 10, 3, 0, 4, 11, 2, 5, 8, 9, 15"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n",
"\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print('15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 ')\n",
"print()\n",
"graphviz.Source(tree.dot(t))"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n",
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n",
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n",
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n"
]
}
],
"source": [
"def depth(t):\n",
" # Pre-order op\n",
" print(t.key, end=' ')\n",
" if not t.children:\n",
" # leaf case\n",
" return\n",
" depth(t.children[0])\n",
" for child in t.children[1:]:\n",
" print('|', end=' ') # between children\n",
" depth(child)\n",
" # post-order op\n",
" print(t.key, end=' ')\n",
"\n",
"print('15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 ')\n",
"depth(t)\n",
"print()\n",
"\n",
"def depth_bin(t):\n",
" print(t.key, end=' ')\n",
" if not t.child:\n",
" # leaf case\n",
" return\n",
" depth_bin(t.child)\n",
" child = t.child.sibling\n",
" while child:\n",
" print('|', end=' ') # between children\n",
" depth_bin(child)\n",
" child = child.sibling\n",
" # post-order op\n",
" print(t.key, end=' ')\n",
"\n",
"depth_bin(tbin)\n",
"print()\n",
"\n",
"def depth_bin2(t):\n",
" print(t.key, end=' ')\n",
" if t.child:\n",
" depth_bin2(t.child)\n",
" print(t.key, end=' ')\n",
" if t.sibling:\n",
" print('|', end=' ')\n",
" depth_bin2(t.sibling)\n",
"\n",
"depth_bin2(tbin)\n",
"print()"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"graphviz.Source(tree.dot(t))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## BFS\n",
"\n",
"\n",
"\n",
"15\n",
"3 8 9\n",
"-6 10 11 2 5\n",
"0 4\n",
"\n",
"2.2 question 3"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n",
"1\n",
"2\n",
"3\n",
"4\n",
"5\n",
"6\n",
"7\n",
"8\n",
"9\n"
]
}
],
"source": [
"from algopy.queue import Queue\n",
"q = Queue()\n",
"for i in range(10):\n",
" q.enqueue(i)\n",
"while not q.isempty():\n",
" print(q.dequeue())"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def width(t):\n",
" w, wcur = 0, 0\n",
" q = Queue()\n",
" q.enqueue(t)\n",
" q.enqueue(None)\n",
" while not q.isempty():\n",
" cur = q.dequeue()\n",
" if not cur:\n",
" w = max(w, wcur)\n",
" wcur = 0\n",
" if not q.isempty():\n",
" q.enqueue(None)\n",
" else:\n",
" wcur += 1\n",
" for child in cur.children:\n",
" q.enqueue(child)\n",
" return w\n",
"\n",
"width(t)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def width_bin(t):\n",
" w, wcur = 0, 0\n",
" q = Queue()\n",
" q.enqueue(t)\n",
" q.enqueue(None)\n",
" while not q.isempty():\n",
" cur = q.dequeue()\n",
" if not cur:\n",
" w = max(w, wcur)\n",
" wcur = 0\n",
" if not q.isempty():\n",
" q.enqueue(None)\n",
" else:\n",
" wcur += 1\n",
" child = cur.child\n",
" while child:\n",
" q.enqueue(child)\n",
" child = child.sibling\n",
" return w\n",
"\n",
"width_bin(tbin)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"\n",
"\n",
"from collections import deque\n",
"def width2(t):\n",
" w = 1\n",
" curq, nextq = deque([t]), deque()\n",
" while curq:\n",
" cur = curq.popleft()\n",
" for c in cur.children:\n",
" nextq.append(c)\n",
" if not curq:\n",
" w = max(w, len(nextq))\n",
" curq, nextq = nextq, curq\n",
" return w"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3.1 Equality"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def same(t, b):\n",
" if t.key == b.key:\n",
" bc = b.child\n",
" for tc in t.children:\n",
" if not bc or not same(tc, bc):\n",
" return False\n",
" bc = bc.sibling\n",
" return bc == None\n",
" return False\n",
"\n",
"def same_bfs(t, b):\n",
" qt = deque([t])\n",
" qb = deque([b])\n",
" while qt and qb:\n",
" ct, cb = qt.popleft(), qb.popleft()\n",
" if ct.key != cb.key:\n",
" return False\n",
" chb = cb.child\n",
" for cht in ct.children:\n",
" if not chb:\n",
" return False\n",
" qt.append(cht)\n",
" qb.append(chb)\n",
" chb = chb.sibling\n",
" if chb:\n",
" return False\n",
" return not (qt or qb)\n",
"\n",
"same(t, tbin)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3.2 Average arity"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def __avg_arity(t):\n",
" nc, ni = t.nbchildren, (t.nbchildren > 0)\n",
" for child in t.children:\n",
" c, i = __avg_arity(child)\n",
" nc, ni = nc + c, ni + i\n",
" return nc, ni\n",
"\n",
"def avg_arity(t):\n",
" children, internal = __avg_arity(t)\n",
" return children / internal if internal else 0\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2.125\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t2 = tree.loadtree('files/treetuto-2.tree')\n",
"print(avg_arity(t2))\n",
"graphviz.Source(tree.dot(t2))"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2.5"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __avg_arity_bin(t):\n",
" nc, ni = 0, (t.child != None)\n",
" child = t.child\n",
" while child:\n",
" c, i = __avg_arity_bin(child)\n",
" nc, ni = 1 + nc + c, ni + i\n",
" child = child.sibling\n",
" return nc, ni\n",
"\n",
"def avg_arity_bin(t):\n",
" children, internal = __avg_arity_bin(t)\n",
" return children / internal if internal else 0\n",
"\n",
"\n",
"avg_arity_bin(tbin)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2.5"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __avg_arity_bin2(t):\n",
" if not t:\n",
" return 0,0\n",
" a, b = __avg_arity_bin2(t.child)\n",
" c, d = __avg_arity_bin2(t.sibling)\n",
" return a + c + 1, b + d + (t.child != None)\n",
"\n",
"def __avg_arity_bin2(t):\n",
" a, b = __avg_arity_bin2(t.child) if t.child else (0,-1)\n",
" c, d = __avg_arity_bin2(t.sibling) if t.sibling else (0,0)\n",
" return a + c + 1, b + d + 1\n",
"\n",
"def avg_arity_bin2(t):\n",
" size, internal = __avg_arity_bin2(t)\n",
" return (size - 1) / internal if internal else 0\n",
"\n",
"avg_arity_bin2(tbin)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6]\n",
"2 -> 0\n",
"2 -> 1\n",
"10 -> 2\n",
"6 -> 3\n",
"2 -> 4\n",
"10 -> 5\n",
"7 -> 6\n",
"8 -> 7\n",
"10 -> 8\n",
"2 -> 9\n",
"-1 -> 10\n",
"6 -> 11\n"
]
}
],
"source": [
"parents = [ 2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6 ]\n",
"print(parents)\n",
"for i in range(len(parents)):\n",
" print(parents[i], '->', i)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"t3 = tree.loadtree('files/treetuto-3.tree')\n",
"#graphviz.Source(tree.dot(t3))"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6]"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __serialize(t, parents):\n",
" for child in t.children:\n",
" parents[child.key] = t.key\n",
" __serialize(child, parents)\n",
"\n",
"def serialze(t, size):\n",
" parents = [-1] * size\n",
" __serialize(t, parents)\n",
" return parents\n",
"\n",
"from algopy import tree_to_bin\n",
"tb3 = tree_to_bin.tree2bin(t3)\n",
"\n",
"serialze(t3, size(t3))\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6]"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __serialize_bin(t, parents):\n",
" if t.child:\n",
" parents[t.child.key] = t.key\n",
" __serialize_bin(t.child, parents)\n",
" if t.sibling:\n",
" parents[t.sibling.key] = parents[t.key]\n",
" __serialize_bin(t.sibling, parents)\n",
"\n",
"def __serialize_bin(t, parents, p=-1):\n",
" parents[t.key] = p\n",
" if t.child:\n",
" __serialize_bin(t.child, parents, t.key)\n",
" if t.sibling:\n",
" __serialize_bin(t.sibling, parents, p)\n",
"\n",
"def serialze_bin(t, size):\n",
" parents = [-1] * size\n",
" __serialize_bin(t, parents)\n",
" return parents\n",
"\n",
"serialze_bin(tb3, size_bin(tb3))\n"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 2, 3] [1, 2, 3]\n",
"[1, 2, 3, 42, 27972] [1, 2, 3]\n"
]
}
],
"source": [
"def foo(l):\n",
" l += [42, 27972]\n",
"\n",
"def bar(l):\n",
" l = []\n",
" \n",
"l1 = [1,2,3]\n",
"l2 = [1,2,3]\n",
"\n",
"print(l1, l2)\n",
"\n",
"foo(l1)\n",
"bar(l2)\n",
"\n",
"print(l1, l2)"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6]"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __serialize_bin(t, parents, p=-1):\n",
" if t.key >= len(parents):\n",
" parents += [-1] * (t.key - len(parents) + 1)\n",
" parents[t.key] = p\n",
" if t.child:\n",
" __serialize_bin(t.child, parents, t.key)\n",
" if t.sibling:\n",
" __serialize_bin(t.sibling, parents, p)\n",
"\n",
"def serialze_bin(t):\n",
" parents = [-1] * (t.key + 1)\n",
" __serialize_bin(t, parents)\n",
" return parents\n",
"\n",
"serialze_bin(tb3)"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6]"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def serialize_bfs(t):\n",
" q = Queue()\n",
" q.enqueue(t)\n",
" parents = [-1] * (t.key + 1)\n",
" while not q.isempty():\n",
" cur = q.dequeue()\n",
" for child in cur.children:\n",
" if child.key >= len(parents):\n",
" parents += [-1] * (child.key - len(parents) + 1)\n",
" parents[child.key] = cur.key\n",
" q.enqueue(child)\n",
" return parents\n",
"\n",
"serialize_bfs(t3)"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# 3.4.1\n",
"def bin2tree(b):\n",
" t = tree.Tree(b.key)\n",
" child = b.child\n",
" while child:\n",
" t.children.append(bin2tree(child))\n",
" child = child.sibling\n",
" return t\n",
"\n",
"def bin2tree2(b, p=None):\n",
" t = tree.Tree(b.key)\n",
" if p:\n",
" p.children.append(t)\n",
" if b.child:\n",
" bin2tree2(b.child, t)\n",
" if b.sibling:\n",
" bin2tree2(b.sibling, p)\n",
" return t\n",
"\n",
"def bin2tree3(b, p=None):\n",
" t = tree.Tree(b.key)\n",
" if b.child:\n",
" t.children.append(bin2tree3(b.child, t))\n",
" if b.sibling:\n",
" p.children.append(bin2tree3(b.sibling, p))\n",
" t.children.reverse()\n",
" return t\n",
"\n",
"\n",
"tbin = treeasbin.tutoEx1()\n",
"graphviz.Source(tree.dot(bin2tree3(tbin)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# m-way search tree\n",
"# b tree\n",
"# b+ tree"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def tree2bin(t):\n",
" b = treeasbin.TreeAsBin(t.key)\n",
" for i in range(t.nbchildren - 1, -1, -1):\n",
" c = tree2bin(t.children[i])\n",
" c.sibling = b.child\n",
" b.child = c\n",
" return b\n",
"\n",
"graphviz.Source(tree.dot(bin2tree(tree2bin(t))))"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __tree2bin2(p, pos=0):\n",
" if pos >= p.nbchildren:\n",
" return None\n",
" b = treeasbin.TreeAsBin(p.children[pos].key)\n",
" b.child = __tree2bin2(p.children[pos], 0)\n",
" b.sibling = __tree2bin2(p, pos+1)\n",
" return b\n",
"\n",
"def tree2bin2(t):\n",
" return treeasbin.TreeAsBin(t.key, child=__tree2bin2(t))\n",
"\n",
"graphviz.Source(tree.dot(bin2tree(tree2bin2(t))))"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))'"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tlin = '(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))'\n",
"tlin"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"graphviz.Source(tree.dot(tree.loadtree(\"files/treetuto-4.tree\")))"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))\n",
"(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))\n"
]
}
],
"source": [
"def tree2list(t):\n",
" s = '(' + str(t.key)\n",
" for child in t.children:\n",
" s += tree2list(child)\n",
" return s + ')'\n",
"\n",
"print(tree2list(t))\n",
"print(tlin)\n"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))\n"
]
}
],
"source": [
"def bin2list(t):\n",
" s = ''\n",
" if t:\n",
" s = '(' + str(t.key)\n",
" s += bin2list(t.child)\n",
" s += ')'\n",
" s += bin2list(t.sibling)\n",
" return s\n",
"\n",
"print(bin2list(tbin))"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def list2tree(s, pos=0, type=int):\n",
" if pos < len(s) and s[pos] == '(':\n",
" pos += 1\n",
" w = ''\n",
" while s[pos] not in '()':\n",
" w += s[pos]\n",
" pos += 1\n",
" t = tree.Tree(type(w))\n",
" while s[pos] != ')':\n",
" c, pos = list2tree(s, pos, type)\n",
" t.children.append(c)\n",
" pos += 1\n",
" return t, pos\n",
" return None\n",
"\n",
"graphviz.Source(tree.dot(list2tree(tlin)[0]))"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def list2bin(s, pos=0, type=int):\n",
" t = None\n",
" if pos < len(s) and s[pos] == '(':\n",
" pos += 1\n",
" w = ''\n",
" while s[pos] not in '()':\n",
" w += s[pos]\n",
" pos += 1\n",
" t = treeasbin.TreeAsBin(type(w))\n",
" t.child, pos = list2bin(s, pos, type)\n",
" pos += 1\n",
" t.sibling, pos = list2bin(s, pos, type)\n",
" return t, pos\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __bin2dot(t):\n",
" child = t.child\n",
" s = ''\n",
" while child:\n",
" s += ' ' + str(t.key) + ' -- ' + str(child.key) + ';\\n'\n",
" s += __bin2dot(child)\n",
" child = child.sibling\n",
" return s\n",
"\n",
"def bin2dot(t):\n",
" s = 'graph {\\n'\n",
" s += __bin2dot(t)\n",
" return s + '}\\n'\n",
"\n",
"graphviz.Source(bin2dot(tbin))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.6.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}