Final Project for DS by Huanze Tang.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from linked_stack import LinkedStack\n",
    "from linked_queue import LinkedQueue\n",
    "from tree import Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基于单链表的栈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedStack():\n",
    "    \n",
    "    class _Node():\n",
    "        __slots__='_elem','_next' #slots : 槽\n",
    "        \n",
    "        def __init__(self,elem,next):\n",
    "            self._elem=elem\n",
    "            self._next=next\n",
    "            \n",
    "    def __init__(self):\n",
    "        '''create an empty linked list'''\n",
    "        self._head=None\n",
    "        self._size=0\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return len(self)==0 #self._size==0 or self._head==None\n",
    "    \n",
    "    def push(self,e):\n",
    "        new=self._Node(e,self._head)\n",
    "        self._head=new\n",
    "        self._size+=1\n",
    "        \n",
    "    def pop(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty!')\n",
    "        result=self._head._elem\n",
    "        self._head=self._head._next\n",
    "        self._size-=1\n",
    "        return result\n",
    "    \n",
    "    def top(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty!')\n",
    "        return self._head._elem\n",
    "    \n",
    "    def __repr__(self):\n",
    "        data=[]\n",
    "        walk=self._head\n",
    "        while walk._next is not None:\n",
    "            data.append(walk._elem)\n",
    "            walk=walk._next\n",
    "        data.append(walk._elem)\n",
    "        return f'{data}'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基于单链表的队列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedQueue():\n",
    "    \n",
    "    class _Node():\n",
    "        __slots__='_elem','_next'\n",
    "        \n",
    "        def __init__(self,elem,next):\n",
    "            self._elem=elem\n",
    "            self._next=next\n",
    "            \n",
    "    def __init__(self):\n",
    "        self._head=None\n",
    "        self._tail=None\n",
    "        self._size=0\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return len(self)==0\n",
    "    \n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty!')\n",
    "        result=self._head._elem\n",
    "        self._head=self._head._next\n",
    "        self._size-=1\n",
    "        if self.is_empty():\n",
    "            self._tail=None\n",
    "        return result\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty('Stack is empty!')\n",
    "        return self._head._elem\n",
    "    \n",
    "    def enqueue(self,e):\n",
    "        new=self._Node(e,None)\n",
    "        if self.is_empty():\n",
    "            self._head=new\n",
    "        else:\n",
    "            self._tail._next=new\n",
    "        self._tail=new\n",
    "        self._size+=1\n",
    "            \n",
    "    def __repr__(self):\n",
    "        data=[]\n",
    "        walk=self._head\n",
    "        while walk._next is not None:\n",
    "            data.append(walk._elem)\n",
    "            walk=walk._next\n",
    "        data.append(walk._elem)\n",
    "        return f'{data}'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 树的抽象数据类型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree():\n",
    "    class Position():\n",
    "        def elem(self):\n",
    "            raise NotImplementedError('must be implemented by subclass')\n",
    "            \n",
    "        def __eq__(self):\n",
    "            raise NotImplementedError('must be implemented by subclass')\n",
    "            \n",
    "        def __ne__(self):\n",
    "            raise NotImplementedError('must be implemented by subclass')\n",
    "            \n",
    "    def root(self):\n",
    "        raise NotImplementedError('must be implemented by subclass')\n",
    "        \n",
    "    def parent(self,p):\n",
    "        raise NotImplementedError('must be implemented by subclass')\n",
    "        \n",
    "    def num_children(self,p):\n",
    "        raise NotImplementedError('must be implemented by subclass')\n",
    "        \n",
    "    def children(self,p):\n",
    "        raise NotImplementedError('must be implemented by subclass')\n",
    "        \n",
    "    def __len__(self):\n",
    "        raise NotImplementedError('must be implemented by subclass')\n",
    "        \n",
    "    def is_empty(self):\n",
    "        return len(self)==0\n",
    "    \n",
    "    def is_root(self,p):\n",
    "        return self.root()==p\n",
    "    \n",
    "    def is_leaf(self,p):\n",
    "        return self.num_children(p)==0\n",
    "    \n",
    "    def depth(self,p):\n",
    "        if self.is_root(p):\n",
    "            return 0\n",
    "        else:\n",
    "            return 1+self.depth(self.parent(p))\n",
    "        \n",
    "    def _height1(self,p):\n",
    "        return max(self.depth(p) for p in self.positions() if self.is_root(p))\n",
    "    \n",
    "    def _height2(self,p):\n",
    "        if self.is_leaf(p):\n",
    "            return 0\n",
    "        else:\n",
    "            return 1+max(self._height2(c) for c in self.children(p))\n",
    "        \n",
    "    def height(self,p=None):\n",
    "        if p is None:\n",
    "            p=self.root()\n",
    "        return self._height2(p)\n",
    "    \n",
    "    def _subtree_preorder(self,p):\n",
    "        yield p\n",
    "        for c in self.children(p):\n",
    "            for other in self._subtree_preorder(c):\n",
    "                yield other\n",
    "                \n",
    "    def preorder(self):\n",
    "        if not self.is_empty():\n",
    "            for p in self._subtree_preorder(self.root()):\n",
    "                yield p\n",
    "                \n",
    "    def _subtree_postorder(self,p):\n",
    "        for c in self.children(p):\n",
    "            for other in self._subtree_postorder(c):\n",
    "                yield other\n",
    "        yield p\n",
    "        \n",
    "    def postorder(self):\n",
    "        if not self.is_empty():\n",
    "            for p in self._subtree_postorder(self.root()):\n",
    "                yield p\n",
    "                \n",
    "    def breadthfirst(self):\n",
    "        if not self.is_empty():\n",
    "            Q=LinkedQueue()\n",
    "            Q.enqueue(self.root())\n",
    "            while not Q.is_empty():\n",
    "                p=Q.dequeue()\n",
    "                yield p\n",
    "                for c in self.children(p):\n",
    "                    Q.enqueue(c)\n",
    "                    \n",
    "    def positions(self,mode='preorder'):\n",
    "        if mode=='preorder':\n",
    "            return self.preorder()\n",
    "        elif mode=='postorder':\n",
    "            return self.postorder()\n",
    "        elif mode=='breadthfirst':\n",
    "            return self.breadthfirst()\n",
    "        else:\n",
    "            raise ValueError('Invalid mode!')\n",
    "            \n",
    "    def __iter__(self,mode='preorder'):\n",
    "        for p in self.positions(mode):\n",
    "            yield p.elem()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 基于树的抽象数据类型的一般树的链式结构实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedGeneralTree(Tree):\n",
    "    class _Node():\n",
    "        __slots__='_element','_parent','_children'\n",
    "        \n",
    "        def __init__(self,element,parent=None,children=[]):\n",
    "            self._element=element\n",
    "            self._parent=parent\n",
    "            self._children=children\n",
    "            \n",
    "    class Position(Tree.Position):\n",
    "        def __init__(self,container,node):\n",
    "            self._container=container\n",
    "            self._node=node\n",
    "            \n",
    "        def elem(self):\n",
    "            return self._node._element\n",
    "        \n",
    "        def __eq__(self,other):\n",
    "            return type(self) is type(other) and self._node==other._node\n",
    "        \n",
    "    def _validate(self,p):\n",
    "        if not isinstance(p,self.Position):\n",
    "            raise TypeError('p must be proper position type!')\n",
    "        if p._container is not self:\n",
    "            raise ValueError('p does not belong to this container!')\n",
    "        if p._node._parent is p._node:\n",
    "            raise ValueError('p is not valid!')\n",
    "        return p._node\n",
    "    \n",
    "    def _make_position(self,node):\n",
    "        return self.Position(self,node) if node is not None else None\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._root=None\n",
    "        self._size=0\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def root(self):\n",
    "        return self._make_position(self._root)\n",
    "    \n",
    "    def parent(self,p):\n",
    "        node=self._validate(p)\n",
    "        return self._make_position(node._parent)\n",
    "    \n",
    "    def children(self,p):\n",
    "        node=self._validate(p)\n",
    "        children=[]\n",
    "        for x in node._children:\n",
    "            children.append(self._make_position(x))\n",
    "        return children\n",
    "            \n",
    "    def num_children(self,p):\n",
    "        node=self._validate(p)\n",
    "        return len(node._children)\n",
    "    \n",
    "    def add_root(self,e):\n",
    "        if self.root() is not None:\n",
    "            raise ValueError('root has already exists!')\n",
    "        self._size=1\n",
    "        self._root=self._Node(e)\n",
    "        return self._make_position(self._root)\n",
    "    \n",
    "    def add_children(self,p,L):\n",
    "        node=self._validate(p)\n",
    "        if not node.is_leaf():\n",
    "            raise ValueError('p is not a leaf!')\n",
    "        self._size+=len(L)\n",
    "        children=[]\n",
    "        for i in range(len(L)):\n",
    "            node._child=self._Node(L[i],node)\n",
    "            children.append(self._make_position(node._child))\n",
    "        node._children=children\n",
    "        return children\n",
    "    \n",
    "    def attach_subtrees(self,p,subtrees):\n",
    "        node=self._validate(p)\n",
    "        if not self.is_leaf(p):\n",
    "            raise ValueError('p is not a leaf!')\n",
    "        node._children=[]\n",
    "        for i in range(len(subtrees)):\n",
    "            if not type(self) is type(subtrees[i]):\n",
    "                raise TypeError('tree types must match!')\n",
    "            self._size+=len(subtrees[i])\n",
    "            if not subtrees[i].is_empty():\n",
    "                subtrees[i]._root._parent=node\n",
    "                node._children.append(subtrees[i]._root)\n",
    "                subtrees[i]._root=None\n",
    "                subtrees[i]._size=0\n",
    "            \n",
    "    def replace(self,p,e):\n",
    "        node=self._validate(p)\n",
    "        old_value=node._element\n",
    "        node._element=e\n",
    "        return old_value\n",
    "    \n",
    "    def delete(self,p):\n",
    "        node=self._validate(p)\n",
    "        if self.num_children(p)>1:\n",
    "            raise ValueError('Position has over one children!')\n",
    "        children=list(self.children(node))\n",
    "        for child in children:\n",
    "            if child is not None:\n",
    "                child._parent=node._parent\n",
    "            if node is self._root:\n",
    "                self._root=child\n",
    "            else:\n",
    "                parent=node._parent\n",
    "                parent._children1=[child if x==node else x for x in parent._children]\n",
    "                parent._children=parent._children1\n",
    "        self._size-=1\n",
    "        node._parent=node\n",
    "        return node._element\n",
    "    \n",
    "## preorder,postorder,levelorder has already been written in superclass -- Tree\n",
    "    \n",
    "    def _subtree_preorder(self,p):\n",
    "        yield p\n",
    "        for c in self.children(p):\n",
    "            for other in self._subtree_preorder(c):\n",
    "                yield other\n",
    "                \n",
    "    def preorder(self):\n",
    "        if not self.is_empty():\n",
    "            for p in self._subtree_preorder(self.root()):\n",
    "                yield p\n",
    "                \n",
    "    def _subtree_postorder(self,p):\n",
    "        for c in self.children(p):\n",
    "            for other in self._subtree_postorder(c):\n",
    "                yield other\n",
    "        yield p\n",
    "        \n",
    "    def postorder(self):\n",
    "        if not self.is_empty():\n",
    "            for p in self._subtree_postorder(self.root()):\n",
    "                yield p\n",
    "                \n",
    "    def levelorder(self):\n",
    "        if not self.is_empty():\n",
    "            Q=LinkedQueue()\n",
    "            Q.enqueue(self.root())\n",
    "            while not Q.is_empty():\n",
    "                p=Q.dequeue()\n",
    "                yield p\n",
    "                for c in self.children(p):\n",
    "                    Q.enqueue(c)\n",
    "    \n",
    "    def reverse_levelorder(self):\n",
    "        if not self.is_empty():\n",
    "            Q=LinkedQueue()\n",
    "            S=LinkedStack()\n",
    "            Q.enqueue(self.root())\n",
    "            while not Q.is_empty():\n",
    "                s=Q.dequeue()\n",
    "                S.push(s)\n",
    "                for c in self.children(s):\n",
    "                    Q.enqueue(c)\n",
    "            while not S.is_empty():\n",
    "                a=S.pop()\n",
    "                yield a\n",
    "                    \n",
    "    def k_distance(self,k):\n",
    "        if self.is_empty():\n",
    "            raise ValueError('there is no root!')\n",
    "        if k>self.height() or k<0:\n",
    "            raise ValueError('k is not suitable for the height of the root!')\n",
    "        else:\n",
    "            Q=LinkedQueue()\n",
    "            Q.enqueue(self.root())\n",
    "            n=0\n",
    "            while n<k:\n",
    "                for i in range(len(Q)):\n",
    "                    q=Q.dequeue()\n",
    "                    for c in self.children(q):\n",
    "                        Q.enqueue(c)\n",
    "                n+=1\n",
    "            while not Q.is_empty():\n",
    "                x=Q.dequeue()\n",
    "                yield x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 测试阶段"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一般链式结构树的构造"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "t1=LinkedGeneralTree()\n",
    "t1.add_root('G')\n",
    "t2=LinkedGeneralTree()\n",
    "t2.add_root('H')\n",
    "t3=LinkedGeneralTree()\n",
    "t3.add_root('E')\n",
    "t3.attach_subtrees(t3.root(),[t1,t2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "t4=LinkedGeneralTree()\n",
    "t4.add_root('D')\n",
    "t5=LinkedGeneralTree()\n",
    "t5.add_root('F')\n",
    "t6=LinkedGeneralTree()\n",
    "t6.add_root('B')\n",
    "t6.attach_subtrees(t6.root(),[t4,t3,t5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "t7=LinkedGeneralTree()\n",
    "t7.add_root('C')\n",
    "t8=LinkedGeneralTree()\n",
    "t8.add_root('A')\n",
    "t8.attach_subtrees(t8.root(),[t6,t7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class '__main__.LinkedGeneralTree.Position'>\n"
     ]
    }
   ],
   "source": [
    "print(type(t8.root()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "前序遍历的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "L1=t8.preorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A\n",
      "B\n",
      "D\n",
      "E\n",
      "G\n",
      "H\n",
      "F\n",
      "C\n"
     ]
    }
   ],
   "source": [
    "# 前序遍历的实现\n",
    "for k in range(len(t8)):\n",
    "    print(next(L1).elem())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "后续遍历的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "L2=t8.postorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "D\n",
      "G\n",
      "H\n",
      "E\n",
      "F\n",
      "B\n",
      "C\n",
      "A\n"
     ]
    }
   ],
   "source": [
    "#后序遍历的实现\n",
    "for k in range(len(t8)):\n",
    "    print(next(L2).elem())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "层序遍历的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "L3=t8.levelorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A\n",
      "B\n",
      "C\n",
      "D\n",
      "E\n",
      "F\n",
      "G\n",
      "H\n"
     ]
    }
   ],
   "source": [
    "#层序遍历的实现\n",
    "for k in range(len(t8)):\n",
    "    print(next(L3).elem())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "逆层序遍历的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "L4=t8.reverse_levelorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H\n",
      "G\n",
      "F\n",
      "E\n",
      "D\n",
      "C\n",
      "B\n",
      "A\n"
     ]
    }
   ],
   "source": [
    "#逆层序遍历的实现\n",
    "for k in range(len(t8)):\n",
    "    print(next(L4).elem())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "到根节点的距离为k的节点位置的迭代"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A\n"
     ]
    }
   ],
   "source": [
    "# k_distance的检验\n",
    "y0=t8.k_distance(0)\n",
    "for x in y0:\n",
    "    print(x.elem())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B\n",
      "C\n"
     ]
    }
   ],
   "source": [
    "y1=t8.k_distance(1)\n",
    "for x in y1:\n",
    "    print(x.elem())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "D\n",
      "E\n",
      "F\n"
     ]
    }
   ],
   "source": [
    "y2=t8.k_distance(2)\n",
    "for x in y2:\n",
    "    print(x.elem())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "G\n",
      "H\n"
     ]
    }
   ],
   "source": [
    "y3=t8.k_distance(3)\n",
    "for x in y3:\n",
    "    print(x.elem())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t8.num_children(t8.root())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t8.num_children(t8.children(t8.root())[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}