p2-a-tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 定义问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当我们说“树形结构”的时候，那是从自然界的大树上得到的启发，从根开始不断展开的枝丫，代表了从单一到复杂的一层层展开，在现实世界充满了这样的事物：国家的行政区划（以及任何组织的架构）、电商网站的商品分类、论坛里的板块等等。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"assets/tree-graph.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 虽然自然界里树是根在下面而向上分支，但是我们在处理树形结构时，如图这样的从上向下分支更容易画也更容易看。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解决问题的第一步是先要清晰明确地定义问题，我们来尝试把我们对树的直觉印象书写成尽可能清晰明确的定义和表述。在一个树形结构里：\n",
    "* 树（*tree*）由节点（*node*）和连接节点的边（*edge*）组成；\n",
    "* 总有一个节点是分支的起点，它分出了所有其他的节点，这个节点叫根节点（*root node*）；\n",
    "* 一个节点分支出来的节点叫它的“子节点（*child nodes*）”，它是其子节点的“父节点（*parent node*）”；上图中节点 A 的父节点是根节点，子节点是 B 和 C，而节点 C 的父节点是 A，子节点是 D 和 E；节点 D 的父节点是 C，而它没有子节点；\n",
    "* 拥有共同父节点的两个节点互为“兄弟姐妹（*sibling nodes*）”；比如上图中 B 和 C，D 和 E；\n",
    "* 没有子节点的节点也叫“叶子节点（*leaf node*）”；比如上图中的 D 和 E；\n",
    "* 一个节点的父节点，以及父节点的父节点…直至根节点，都是这个节点的“祖先节点（*ancestor nodes*）”；比如上图中 E 的祖先节点包括 C、A 和 根节点；\n",
    "* 一个节点的所有子节点，以及所有子节点的子节点…直至叶子节点，都是这个节点的“后代节点（*descendant nodes*）”；\n",
    "* 一个节点 X 和它所有后代节点、以及这些节点之间的边，也组成一棵树，叫做原数的一棵（以 X 为根的）“子树（*sub-tree*）”；\n",
    "* 根节点没有父节点也没有祖先节点；\n",
    "* 除了根节点以外的任何节点，有且只有 1 个父节点，有至少 1 个祖先节点；\n",
    "* 任何节点都可以有 0、1 或者多个子节点，可以有  0、1 或者多个后代节点；\n",
    "* 一个节点和它的任一祖先或者后代节点之间，一定存在一条由边收尾连接组成的路径（*path*），比如上图中根节点是 E 的祖先，它们之间的路径是 `root -> A -> C -> E`；这个路径就像是两个节点之间的亲属关系链；\n",
    "* 两个节点之间 *path* 的长度，就是它由几条边组成，决定了这两个节点之间隔了多少“代”，也叫节点之间的“距离（*distance*）”；\n",
    "* 一个节点和根节点之间的 *distance* 经常有特别的含义，相当于该节点在树的“第几层级（*tier*）”；比如在行政区划里哪些是一级节点（省、直辖市、自治区）哪些是二级节点等；\n",
    "* 有些树里节点的子节点是有顺序的，叫做“有序树（*ordered tree*）”；如果我们不特别指出，那就是不考虑这种顺序概念。\n",
    "\n",
    "上面这种“把直觉规则化”的过程，对后面设计解决方案是至关重要的，大家可以自己尝试，多多体会。\n",
    "\n",
    "> 事实上在数学图论里有对树的[更严谨更数学化的定义](https://en.wikipedia.org/wiki/Tree_(graph_theory))，不过上面的表述对目前的我们来说基本够用了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 分析操作场景"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到树和我们前面讲的所有数据结构都不一样，没办法用一种“线性（*linear*）”结构来表达，如何在计算机中实现一个树形数据结构？面对这样的问题，我们应该如何思考呢？\n",
    "\n",
    "一个优秀的起点是问题解决的一半。设计数据结构的起点是：**思考我们会怎么操作和使用这个数据结构**。\n",
    "\n",
    "假定我们已经有个一个树形数据结构，我们可能会有这些操作场景（可以尝试用行政区划或者论坛版块等熟悉的实例来帮助思考）：\n",
    "* 查找和遍历：\n",
    "  * 给定一个 *node* 找出它的 *parent* ✪\n",
    "  * 给定一个 *node* 找出它所有的 *children* ✪\n",
    "  * 给定一个 *node* 找出它某个特定 *child*\n",
    "  * 给定一个 *node* 找出它所有的 *siblings*\n",
    "  * 给定一个 *node* 遍历其 *sub-tree* 即找出它的所有 *descendants* ✪\n",
    "  * 给定 *node* *A* 和 *B*，找到 *A* 和 *B* 之间的 *path* 和 *distance*\n",
    "  * 给定一个 *node* 确定它的 *tier*\n",
    "* 编辑\n",
    "  * 给一个 *node* 增加一个 *child* ✪\n",
    "  * 删除一个 *node* ✪ -> 新一步思考：这意味着什么？删除整个子树还是？\n",
    "  * 修改一个 *node* 的 *parent* ✪\n",
    "\n",
    "差不多就这些，其中标记了 ✪ 号的是感觉特别重要和基础的操作。\n",
    "\n",
    "通过形象化的图示、对基本概念的定义和表述、对可能操作场景的罗列，已经增加了很多我们对问题理解的深度和全面度，下来我们可以尝试做出一些初步设计判断了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 设计初步方案"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从前面的分析，我们可以有这么一些收获：\n",
    "* 树中节点之间的父子关系是核心和本质的内容；\n",
    "* 表达这种父子关系的关键是节点，节点应保存父节点和子节点相关信息；\n",
    "* 树的结构上带有显著的“递归”特点，可以有助于我们的设计。\n",
    "\n",
    "如果你不记得“递归（*recursion*，*recursive*）”是怎么回事了，可以温习[递归函数](p2-4-recursion.ipynb)一章。\n",
    "\n",
    "树也是递归的一个典型例子，因为一棵树可以看做由**根节点、根节点的子节点和以这些子节点为根的子树**合起来组成的，如果我们想实现对树进行操作的函数 `f()`，那么我们可以让这个函数接受一个树的根节点作为输入参数，这个函数大致上会是这个样子：\n",
    "\n",
    "```python\n",
    "def f(root):\n",
    "    # 对 root 做一些操作\n",
    "    # 然后取出 root 的所有子节点，对其中每个子节点调用 f() 本身\n",
    "    for node in root.children:\n",
    "        f(node)\n",
    "```\n",
    "\n",
    "也就是说，我们只要对某个节点做操作，然后获取这个节点的所有子节点，递归调用自己，就能对整个树做操作了。\n",
    "\n",
    "在树形数据结构中，“获取一个节点的所有子节点”是至关重要的操作。\n",
    "\n",
    "据此我们可以做出这么一个初步的设计："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, name='root', data=None, parents=None, children=None):\n",
    "        self.name = name\n",
    "        self,data = data\n",
    "        assert isinstance(parents, TreeNode)\n",
    "        self.parents = parents\n",
    "        self.children = []\n",
    "        if children != None:\n",
    "            for child in children:\n",
    "                self.add_child(child)\n",
    "                \n",
    "    def add_child(self, node):\n",
    "        assert isinstance(node, TreeNode)\n",
    "        node.prent = self\n",
    "        self.children.append(node)\n",
    "                "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们设计的核心数据结构是表示树节点的自定义类型 TreeNode，这个类型的对象有四个实例变量（属性）：\n",
    "* *name*：节点的名字，最好能唯一标识出一个节点\n",
    "* *data*：节点相关的任何数据，可以是任何数据类型\n",
    "* *parent*：节点的父节点，如果没有父节点就是 None\n",
    "* *children*：节点所有子节点组成的一个列表\n",
    "\n",
    "这里面 *parent* 和 *children* 里的元素都必须是 TreeNode 类型的对象，我们在处理这两个属性时要先确认这一点，在上面的代码中我们用 Python 的 `assert` 语句和 `isinstance()` 函数来实现：\n",
    "* `assert` 关键字后面的表达式必须返回 True，否则程序将抛出 `AssertionError` 异常后终止；\n",
    "* `isinstance(obj, type)` 之前我们就介绍过，它接受两个参数，第一个参数是一个对象，而第二个参数是一个类型，函数判断第一个参数是不是第二个参数指明的类型，如果是返回 `True`，否则返回 `False`。\n",
    "\n",
    "如上定义的 `TreeNode` 类，它实例化出来的对象 `node` 具备如下的能力：\n",
    "* 很容易取得其父节点 *parent*；\n",
    "* 很容易取得其所有子节点 *children*；\n",
    "* 已经实现了增加子节点的操作。\n",
    "\n",
    "最有意思的是，TreeNode 类型实际上也代表了树本身，因为一个节点加上它所有子节点，本来就是一棵树嘛！\n",
    "\n",
    "在这个类型定义的基础上，我们可以实现前一节列出的所有操作，你可以把这作为练习动手试一试。\n",
    "\n",
    "> 在实际项目中，我们并不需要定义树的数据结构，因为有优秀的第三方实现可用，比如 Python 非常棒的第三方库 [anytree](https://anytree.readthedocs.io/en/latest/#)，你可以试试，看和你自己实现的有什么区别。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 小结"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}