1. 什么是树

树结构是一种包括节点(nodes)和边(edges)的拥有层级关系的一种结构

2. 树中的概念

根节点(root): 树的最上层的节点，任何非空的树都有一个节点
路径(path): 从起始节点到终止节点经历过的边
父亲(parent)：除了根节点，每个节点的上一层边连接的节点就是它的父亲(节点)
孩子(children): 每个节点由边指向的下一层节点
兄弟(siblings): 同一个父亲并且处在同一层的节点
叶子节点(leaf node): 没有孩子的节点成为叶子节点

tree

图中根节点为T；
T到K的路径TCRK；
XC的父节点是T，BG的父节点是X，KM的父节点是R；
T的子节点是XC，C的子节点是JR, R的子节点KM；
兄弟节点如B和G、J和R、K和M、
叶节点：BZJKM

3. 二叉树

每个父节点最多只有两个子节点的树，上图的树就是二叉树。
与二叉树相关的概念:
节点深度(depth), 树的高度(height), 树的宽度(width), 树的 size

binary_tree

4.特殊结构的二叉树

perfect binary tree

full binary tree

complete binary tree

5. 二叉树的表示

在构建二叉树的时候，再次说明一下二叉树的根，节点，叶，分支等概念。
tree0

一棵树可以看成一个根节点和一系列的分支组成的结构。每一个分支又是一棵树，称之为子树。没有分支的树称为叶。
在构建一个树时，我们需要构建两部分，第一部分是根节点，第二部分是分支。在构造分支时，我们要保证每一个分支都是树的结构。所以要定义一个构造函数tree()，一个分支函数branches()，一个判断分支是否是树的函数is_tree(). 除此之外，我们还可以定义一个label()函数用于获取根节点的值，一个is_leaf()判断一个分支是不是叶节点。

定义一个树的构造函数：

>>> def tree(root_label, branches=[]):for branch in branches:assert is_tree(branch), 'branches must be trees'  # 保证每一个分支都是一个子树return [root_label] + list(branches)

定义一个函数获取根节点的值：

>>> def label(tree):return tree[0]

定义一个函数获取所有的分支：

>>> def branches(tree):return tree[1:]

定义一个is_tree()函数判断分支是否为树：
满足两个条件就是树：

树的类型是list
长度不为0

>>> def is_tree(tree):if type(tree) != list or len(tree) < 1:return Falsefor branch in branches(tree):if not is_tree(branch):return Falsereturn True

下面这个函数用于判断这棵树是否还有分支，也就判断他是否是叶节点：

>>> def is_leaf(tree):return not branches(tree)

一个完整的示例：

def tree(root_label, branches=[]):for branch in branches:assert is_tree(branch), 'branches must be trees'return [root_label] + list(branches)
def label(tree):return tree[0]
def branches(tree):return tree[1:]def is_tree(tree):if type(tree) != list or len(tree) < 1:return Falsefor branch in branches(tree):if not is_tree(branch):return Falsereturn Truedef is_leaf(tree):return not branches(tree)t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
label(t)
branches(t)
label(branches(t)[1])
is_leaf(t)
is_leaf(branches(t)[0])

结果：


>>> t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
>>> t
[3, [1], [2, [1], [1]]]
>>> label(t)
3
>>> branches(t)
[[1], [2, [1], [1]]]
>>> label(branches(t)[1])
2
>>> is_leaf(t)
False
>>> is_leaf(branches(t)[0])
True