1，树
树是一种非常重要的非线性数据结构，直观的看，它是数据元素（在树中称为节点）按分支关系组织起来的结构，很像自然界中树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到了广泛应用，如在编译源程序时，可用树表示源程序的语法结构。又如在 数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可以用树来描述。
树（Tree）是元素的集合。树的定义是递归的，树是一种递归的数据结构。比如：目录结构。树是由n个结点组成的集合：如果n=0，那这就是一颗空树；如果 n>0，那么存在1个结点作为树的根节点，其他结点可以分为m个集合，每个集合本身又是一棵树。
- 1，树的根结点没有前驱结点，除根结点之外所有结点有且只有一个前驱结点。
- 2，树中所有结点可以有零个或者多个后继结点。
1.1 树的术语
- 根节点：树的第一个节点，没有父节点的节点
- 叶子节点：不带分叉的节点
- 树的深度（高度）：就是分了多少层
- 孩子节点，父节点：节点与节点之间的关系
如下图，我们分别解释：
1）B是K的祖先结点，K是B的子孙节点，E是K的双亲节点，K是E的孩子节点，K是L的兄弟节点。
2）树中一个结点的子节点个数为该节点的度，树中结点最大度数为树的度。
3）度大于0为节点结点，度等于0为叶子结点。
4）结点层次如图，结点深度时从根结点从顶往下累加，结点高度从低往上累加，树的高度（深度）是树的最大层数。
5）有序树：从左到右有次序，有关联。反之为无序树。
6）两结点之间的路径是两个结点之间所经过的结点序列构成的，路径长度是路径上所经过的边的个数。
7）森林是 m （m >=0）棵互不相交的集合。
上面观察实际上给了我们一种严格的定义树的方法：
- 1，树是元素的集合
- 2，该集合可以为空，这时树中没有元素，我们称树为空树（empty tree）
- 3，如果该集合不为空，那么该集合有一个根节点，以及0个或者多个子树。根节点与他的子树的根节点用一个边（edge）相连。
1.2 树的实现
树的示意图已经给出了树的一种内存实现方法：每个节点存储元素和多个指向子节点的指针。然而，子节点数目的是不确定的。一个父节点可能有大量的子节点，而另一个父节点可能只有一个子节点，而树的增删节点操作会让子节点的数目发生进一步的变换。这种不确定性就可能就可能带来大量的内存相关操作，并且容易造成内存的浪费。
一种经典的实现方法如下：
树的内存实现：拥有同一父节点的两个结点互为兄弟节点（sibling）。上图的实现方式中，每个节点包含一个指针指向第一个子节点，并且有另一个指针指向他的下一个兄弟节点。这样，我们就可以用统一的，确定的结构来表示每个节点。
1.3 树的实例——模拟文件系统
代码如下：
#_*_coding:utf-8_*_ class Node: def __init__(self, name, type='dir'): self.name = name self.type = type # 'dir' or ; 'file' self.children = [] self.parent = None # 链式存储 def __repr__(self): return self.name class FileSystemTree: def __init__(self): self.root = Node("/") # 首先我们创建一个根目录 self.now = self.root def mkdir(self, name): # 创建一个文件目录，所以我们必须保证name是以 /结尾，如果没有，我们就加 if name[-1] != '/': name += '/' node = Node(name) # 创建一个文件目录 self.now.children.append(node) node.parent = self.now def ls(self): # 展示当前文件夹下的文件 return self.now.children def cd(self, name): # 切换到指定目录 注意：支持绝对路径和相对路径 # 相对路径是从now的路径下开始，而绝对路径是从root路径下开始找 if name[-1] != '/': name += '/' if name == '../': self.now = self.now.parent return for child in self.now.children: if child.name == name: # 如果传入的目录名等于孩子的目录名，我们直接切换 self.now = child return raise ValueError("invalid dir") tree = FileSystemTree() tree.mkdir('var/') tree.mkdir('bin/') tree.mkdir('usr/') print(tree.ls()) # [var/, bin/, usr/] tree.cd('bin/') print(tree.ls()) # [] print(tree.root.children) # [var/, bin/, usr/]
2，二叉树
2.1 二叉树的定义
二叉树的链式存储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。
二叉树是一种特殊的树，它具有以下特点：
1）至多只有两棵子树，二叉树有左右之分，次序不能颠倒，也是递归形式定义。
2）或者为空二叉树，即 n=0
3）或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。
4）每个节点至多有两个节点，即每个节点的度最多为2
5）二叉树中所有节点的形态有5种：空节点，无左右子树的节点，只有左子树的节点，只有右子树的节点和具有左右子树的节点
二叉树的定义如下：
class BiTreeNode: def __init__(self, data): self.data = data self.lchild = None # 左孩子 self.rchild = None # 右孩子 a = BiTreeNode("A") b = BiTreeNode("B") c = BiTreeNode("C") d = BiTreeNode("D") e = BiTreeNode("E") f = BiTreeNode("F") g = BiTreeNode("G") e.lchild = a e.rchild = g a.rchild = c c.lchild = b c.rchild = d g.rchild = f root = e print(root.lchild.rchild.data)
二叉树的节点定义：
class BiTreeNode: def __init__(self, data): self.data = data self.lchild = None # 左孩子 self.rchild = None # 右孩子
2.2 二叉树与度为2的有序树的区别：
1）度为2的树至少有3个结点，而二叉树可以为空。
2）左右次数。
2.3 二叉树的存储方式
二叉树的存储结构分为链式存储结构和顺序存储结构（列表）
二叉树的顺序存储方式
思考：父节点和左孩子节点的编号下标有什么关系？
0-1 1-3 2-5 3-7 4-9 i ----> 2i+1
父节点和右孩子节点的编号下标有有什么关系？
0-2 1-4 2-6 3-8 4-10 i -----> 2i+2
二叉树的链式存储
结构采用链式存储二叉树中的数据元素，用链建立二叉树中结点之间的关系。二叉树最常用的链式存储结构是二叉链，每个节点包含三个域，分别是数据元素域 data，左孩子链域 LChild 和 右孩子链域 rChild。与单链表带头结点和不带头节点的两种情况相似，二叉链存储结构的二叉树也有带头结点和不带头节点两种。
2.4 二叉树的遍历
那么如何遍历一颗二叉树呢？其实有两种通用的遍历树策略：
深度优先搜索（DFS）
在这个策略中，我们采用深度作为优先级，以便从根开始一直到达某个确定的叶子，然后再返回根到达另一个分支。
深度优先搜索策略又可以根据根节点，左孩子和右孩子的相对顺序被细分为先序遍历，中序遍历和后序遍历。
宽度优先搜索（BFS）
我们按照高度顺序一层一层的访问整棵树，高层次的节点将会被低层次的节点先被访问到。
下图中的顶点按照访问的顺序编号，按照1-2-3-4-5 的顺序来比较不同的策略：
下面学习二叉树的遍历方式，以下图的二叉树为例，我们分别学习前序遍历，中序遍历，后序遍历，层次遍历。
前序遍历
思想：先访问根节点，再先序遍历左子树，然后再序遍历右子树。总的来说是 根——左——右
前序遍历如图所示：
代码如下：
# 二叉树的前序遍历 def pre_order(root): if root: print(root.data) # 先打印根节点 pre_order(root.lchild) pre_order(root.rchild) # pre_order(root) ''' E A C B D G F '''
中序遍历
思想：先中序访问左子树，再序访问根节点，最后中序遍历右子树。总的来说是 左——根——右
中序遍历如图所示：
代码如图所示：
# 中序遍历 def in_order(root): if root: in_order(root.lchild) print(root.data) in_order(root.rchild) # in_order(root) ''' A B C D E G F '''
后序遍历
思想：先后续访问左子树，然后后续访问右子树，最后访问根，总的来说是 左——右——根
后序遍历如图所示：
代码如下：
# 后序遍历 def post_order(root): if root: post_order(root.lchild) post_order(root.rchild) print(root.data) post_order(root) ''' B D C A F G E '''
层次遍历（宽度优先遍历）
思想：利用队列，依次将根，左子树，右子树存入队列，按照队列的先进先出规则来实现层次遍历。
代码如下：
from collections import deque def level_order(root): queue = deque() queue.append(root) while len(queue) > 0: # 只要队不空 node = queue.popleft() print(node.data) if node.lchild: queue.append(node.lchild) if node.rchild: queue.append(node.rchild) level_order(root) ''' E A G C F B D '''
3 几个特殊的二叉树
3.1 满二叉树
满二叉树作为一种特殊的二叉树，它是指：除了叶子节点，所有节点都有两个孩子（左子树和右子树），并且所有叶子节点深度都一样。
其特点有：
- 1）叶子节点只能出现在最下面一层
- 2）非叶子节点度一定是2
- 3）在同样深度的二叉树中，满二叉树的节点个数最多，节点个数为：2h-1，其h为树的深度。
3.2 完全二叉树
完全二叉树是由满二叉树引申而来，假设二叉树深度为 h，那么除了第h层外，之前的每一层（1~h-1）的节点数都达到最大，即没有空的位置，而且第K层的子节点也都集中在左子树上（顺序）。
其具有以下特点：
- 1）叶子节点可以出现在最后一层或倒数第二层
- 2）最后一层的叶子节点一定集中在左部连续位置
- 3）完全二叉树严格按层序编号（可利用数组或列表实现，满二叉树同理）
- 4）若一个节点为叶子节点，那么编号比其大的节点均为叶子节点
3.3 二叉排序树
一颗二叉树或者空二叉树，如：左子树上所有关键字均小于根结点的关键字，右子树上的所有结点的关键字均大于根结点的关键字，左子树和右子树各是一颗二叉排序树。
3.4 平衡二叉树
树上任何一结点的左子树和右子树的深度只差不超过1 。
4， 二叉搜索树（BST）
4.1 二叉搜索树的定义
二叉搜索树(Binary Search Tree)，又名二叉排序树(Binary Sort Tree)。
由于二叉树的子节点数目确定，所以可以直接采用下图方式在内存中实现。每个节点有一个左子节点（left children）和右子节点（right children）。左子节点是左子树的根节点，右子节点是右子树的根节点。
如果我们给二叉树加一个额外的条件，就可以得到一种被称为二叉搜索树（binary search tree）的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。
二叉搜索树是一颗二叉树且满足性质：设x是二叉树的一个节点。如果 y 是 x 左子树的一个节点，那么 y.key <= x.key；如果y 是x 的右子树的一个节点，那么 y.key >= x.key。
4.2 二叉搜索树的性质
- 1）若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值
- 2）若右子树不为空，则右子树上所有节点的值均大于或等于它的跟节点的值
- 3）左右子树也分别为二叉搜索树
二叉搜索树，注意树中元素的大小。二叉搜索树可以方便的实现搜索算法。在搜索元素 x 的时候，我们可以将 x 和根节点比较：
- 1，如果 x 等于根节点，那么找到 x ,停止搜索（终止条件）
- 2，如果 x 小于根节点，那么搜索左子树
- 3，如果 x 大于根节点，那么搜索右子树
二叉搜索树所需要进行的操作次数最多与树的深度相等。n个结点的二叉搜索树的深度最多为 n ，最少为 log(n).
4.3 二叉搜索树的插入操作
从根节点开始，若插入的值比根节点的值小，则将其插入根节点的左子树；若比根节点的值大，则将其插入根节点的右子树。该操作可以使用递归进行实现。
代码如下：
class BiTreeNode: def __init__(self, data): self.data = data self.lchild = None # 左孩子 self.rchild = None # 右孩子 self.parent = None class BST: def __init__(self, li=None): self.root = None if li: for val in li: self.insert_no_rec(val) def insert(self, node, val): if not node: node = BiTreeNode(val) elif val < node.data: node.lchild = self.insert(node.lchild, val) node.lchild.parent = node elif val > node.data: node.rchild = self.insert(node.rchild, val) node.rchild.parent = node return node def insert_no_rec(self, val): p = self.root if not p: # 空树 self.root = BiTreeNode(val) return while True: if val < p.data: if p.lchild: p = p.lchild else: # 左孩子不存在 p.lchild = BiTreeNode(val) p.lchild.parent = p return elif val > p.data: if p.rchild: p = p.rchild else: p.rchild = BiTreeNode(val) p.rchild.parent = p return else: return
python常用算法（5）——树，二叉树与AVL树（二）https://developer.aliyun.com/article/1542699
