树 是n个结点的有限集，n=0时为空树
在任意一棵非空树中：有且只有一个特定的根（root）的结点
子树互不相交

结点分类

树的结点包含一个数据元素及指向其子树的分支
结点拥有的子树数称为结点的 度（Degeree)
度为0的结点称为叶节点（Leaf)或终端结点
度不为0的结点称为非终端结点或分支结点
除根节点外，分支结点也称为内部结点，树的度是树内各结点的度的最大值
**

结点间的关系

结点的子树的根称为该结点的孩子（child)，该结点称为孩子的双亲（Parent),同一个双亲的孩子之间互称兄弟（sibliing),结点的祖先是从根到该结点所经分支的所有结点，以某节点为根的子树中的任一结点都称为该结点的子孙。

树的其他相关概念

结点的层次（Level)从根开始定义起，根为第一层，根的孩子为第二层，树中结点的最大层次称为树的深度（depth)或高度

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。**

森林（froest）是m(m>=0)棵互不相交的树的集合
对树中的每个结点来说，其子树的集合即为森林
**

二叉树

是n个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

特点：

  • 每个结点最多有两棵子树，所以二叉树中不存在度为大于2的结点
  • 左子树和右子树是有顺序的，次序不能颠倒
  • 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

特殊二叉树

  • 斜树：所有的结点都只有左子树叫做左斜树，所有结点都是只有右子树的的右斜树
  • 满二叉树：在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

特点：

  • 叶子只能出现在最下一层，出现在其他层就不可能达到平衡
  • 非叶子结点的度一定是2
  • 在同样的深度的二叉树中，满二叉树的结点个数最多，叶子数最多

完全二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这颗树称为完全二叉树。

二叉树性质

  • 在二叉树的第i层上至多有 2 ^ i-1 个结点
  • 深度为k 的二叉树至多有2^k-1个结点
  • 对任何一棵二叉树，如果其终端结点数为n0,度为2的结点数n2，则n0=n2+1(终端结点数就是叶子节点数）
  • 具有n个结点的完全二叉树的深度为[log2n+1] [x] 为不大于x的最大整数

遍历二叉树

  1. 前序遍历 **（根左右）**

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树
顺序：ABDGHCEIF
**

2.中序遍历 **(左根右）
规则是若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。顺序：GDHBAEICF

  1. 后续遍历：**(左右根）**

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根节点。
遍历顺序：GHDBIEFCA

4.层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问，遍历顺序：ABCDEFGHI

问题：
为什么要研究遍历的方法，因为计算机只有循环、判断等方式来处理，只会处理线性序列，我们提到的上述方法都是将树和中的结点变成某种意义的线性序列，方便程序的实现。

遍历算法

  • 深度优先搜索（DFS）

    • 在这个策略中，我们采用深度作为优先级，以便从跟开始一直到达某个确定的叶子，然后再返回根到达另一个分支，深度优先搜索策略又可以根据根结点、左孩子和右孩子的相对顺序被细分为前序遍历、中序遍历和后序遍历

  • 广度优先搜索（BFS)

    • 我们按照高度顺序一层一层的访问整棵树，高层次的结点将会被低层次的结点优先访问到。

方法1:迭代

  1. 1.先定义树的存储结构
  2. class Treenode（object）：
  3.     def __init__(self,x):
  4.         self.val = x
  5.         self.left = None
  6.         self.right = None
  8. 2.从根节点开始，每次迭代弹出当前栈顶元素，并将其孩子结点压入栈中，先压右右孩子再压左孩子
  9. 这个算法中，输出的结果会按Top->Bottom 和 Left -> Right ,符合前序遍历的顺序
  11. class Solutin(object):
  12.     def preorderTraversal(self,root):
  13.         if root is None:
  14.             return []
  16.         stack,output = [root, ],[]
  18.         while stack:
  19.             root = stack.pop()
  20.             if root is not None:
  21.                 output.append(root.val)
  22.                 if root.right is not None:
  23.                     stack.append(root.right)
  24.                 if root.left id not None:
  25.                     stack.append(root.left)
  26.     return output

实现连接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/python3-er-cha-shu-suo-you-bian-li-mo-ban-ji-zhi-s/

二叉树遍历总结：
1.递归：直接递归版本，针对不同的题目通用递归版本（包括前序、中序、后序）
2.迭代：最常用版本（常用主要包括前序和层序，即DFS 和 BFS、【前中后】序遍历通用版本（一个栈的空间）、【前中后层】序通用版本（双倍栈（队列）的空间）
3.莫里斯遍历：利用线索二叉树的特性进行遍历
4.N叉树的前序遍历

  1. class TreeNode:
  2.     def __init__(self,x):
  3.         self.val = x
  4.         self.left = None
  5.         self.right = None
  7.     #递归
  8.     #时间复杂度：O(n),n为节点数，访问每个结点恰好一次
  9.     #空间复杂度：空间复杂度：o(h),h为树的高度，最坏情况下需要空间O(n),平均情况为o(logn)
  11.     #递归1：二叉树遍历最易理解和实现版本
  12.     class Solution:
  13.         def preorderTraversal(self,root:TreeNode) ->List[int]:
  14.             if not root:
  15.                 return []
  16.             #前序递归
  17.             return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
  18.         #中序递归
  19.             return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
  20.         #后序递归
  21.             return self.postorderTraversal(root.val) + self.postorderTraversal(root.right) + [root.val]
  24.         #递归2：通用模板，可以适应不同的题目，添加参数、增加返回条件、修改进入递归条件、自定义返回值
  26.         class Solution:
  27.             def preorderTraversal(self,root:TreeNode) ->List[int]:
  28.                 def dfs(cur):
  29.                     if not cur:
  30.                         return 
  31.                     #前序递归
  32.                     res.append(cur.val)
  33.                     dfs(cur.left)
  34.                     dfs(cur.right)
  35.                     #中序遍历
  36.                     dfs(cur.left)
  37.                     res.append(cur.val)
  38.                     dfs(cur.right)
  40.                     #后序递归
  41.                     dfs(cur.left)
  42.                     dfs(cur.right)
  43.                     res.append(cur.val)
  44.                 res = []
  45.                 dfs(root)
  46.                 return res
  47.             # 迭代
  48.             # 时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。
  49.             # 空间复杂度：O(h)，h为树的高度。取决于树的结构，最坏情况存储整棵树，即O(n)

详细的分析：
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/che-di-chi-tou-er-cha-shu-de-qian-zhong-hou-xu-di-/

递归三要素：

  • 确定递归函数的参数和返回值
  • 确定终止条件（防止栈溢出）

  • 确定单层递归的逻辑（确定每一层递归需要处理的信息） ```python

    迭代

    时间复杂度：O(n)，n为节点数，访问每个节点恰好一次。

    空间复杂度：O(h)，h为树的高度。取决于树的结构，最坏情况存储整棵树，即O(n)

    迭代1：前序遍历最常用模板（后序同样可以用）

    class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]:

    1.   if not root:
    2.       return []        
    3.   res = []
    4.   stack = [root]
    5.   # # 前序迭代模板：最常用的二叉树DFS迭代遍历模板
    6.   while stack:
    7.       cur = stack.pop()
    8.       res.append(cur.val)
    9.       if cur.right:
    10.           stack.append(cur.right)
    11.       if cur.left:
    12.           stack.append(cur.left)
    13.   return res
    15.   # # 后序迭代，相同模板：将前序迭代进栈顺序稍作修改，最后得到的结果反转
    16.   # while stack:
    17.   #     cur = stack.pop()
    18.   #     if cur.left:
    19.   #         stack.append(cur.left)
    20.   #     if cur.right:
    21.   #         stack.append(cur.right)
    22.   #     res.append(cur.val)
    23.   # return res[::-1]

    迭代1：层序遍历最常用模板

    class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]:

    1.   if not root:
    2.       return []
    3.   cur, res = [root], []
    4.   while cur:
    5.       lay, layval = [], []
    6.       for node in cur:
    7.           layval.append(node.val)
    8.           if node.left: lay.append(node.left)
    9.           if node.right: lay.append(node.right)
    10.       cur = lay
    11.       res.append(layval)
    12.   return res

迭代2：前、中、后序遍历通用模板（只需一个栈的空间）

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res = [] stack = [] cur = root

  1.     # 中序，模板：先用指针找到每颗子树的最左下角，然后进行进出栈操作
  2.     while stack or cur:
  3.         while cur:
  4.             stack.append(cur)
  5.             cur = cur.left
  6.         cur = stack.pop()
  7.         res.append(cur.val)
  8.         cur = cur.right
  9.     return res
  11.     # # 前序，相同模板
  12.     # while stack or cur:
  13.     #     while cur:
  14.     #         res.append(cur.val)
  15.     #         stack.append(cur)
  16.     #         cur = cur.left
  17.     #     cur = stack.pop()
  18.     #     cur = cur.right
  19.     # return res
  21.     # # 后序，相同模板
  22.     # while stack or cur:
  23.     #     while cur:
  24.     #         res.append(cur.val)
  25.     #         stack.append(cur)
  26.     #         cur = cur.right
  27.     #     cur = stack.pop()
  28.     #     cur = cur.left
  29.     # return res[::-1]

迭代3：标记法迭代（需要双倍的空间来存储访问状态）：

前、中、后、层序通用模板，只需改变进栈顺序或即可实现前后中序遍历，

而层序遍历则使用队列先进先出。0表示当前未访问，1表示已访问。

class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: res = [] stack = [(0, root)] while stack: flag, cur = stack.pop() if not cur: continue if flag == 0:

  1.             # 前序，标记法
  2.             stack.append((0, cur.right))
  3.             stack.append((0, cur.left))
  4.             stack.append((1, cur))
  6.             # # 后序，标记法
  7.             # stack.append((1, cur))
  8.             # stack.append((0, cur.right))
  9.             # stack.append((0, cur.left))
  11.             # # 中序，标记法
  12.             # stack.append((0, cur.right))
  13.             # stack.append((1, cur))
  14.             # stack.append((0, cur.left))  
  15.         else:
  16.             res.append(cur.val)  
  17.     return res
  19.     # # 层序，标记法
  20.     # res = []
  21.     # queue = [(0, root)]
  22.     # while queue:
  23.     #     flag, cur = queue.pop(0)  # 注意是队列，先进先出
  24.     #     if not cur: continue
  25.     #     if flag == 0:
  26.               # 层序遍历这三个的顺序无所谓，因为是队列，只弹出队首元素
  27.     #         queue.append((1, cur))
  28.     #         queue.append((0, cur.left))
  29.     #         queue.append((0, cur.right))
  30.     #     else:
  31.     #         res.append(cur.val)
  32.     # return res

```

二叉排序树

又称为二叉查找树，它或者是一棵空树，或者具有下列性质：

  • 若它的左子树不空，则左子树上所有的结点的值均小于它的根结点的值
  • 若它的右子树不空，则右子树上所有的结点的值均大于它的根结点的值
  • 它的左右子树也分别为二叉排序树

构造一棵二叉排序树的目的并不是为了排序，而是为了提高查找和插入删除关键字的速度

平衡二叉树(AVL树）

是一种二叉排序树，其中每个节点的左子树和右子树的高度差至多为1
平衡因子（BF) :二叉树上结点的左子树深度减去右子树深度的值
只能是1，-1，0
只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡子树
**

平衡二叉树实现原理

平二叉树构建的基本思想就是子在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡树，在保持二叉排序树的前提下，调整最小不平衡子树中各节点之间的链接关系，进行相应的旋转，使之称为新的平衡子树。

平衡因子 > 0 右旋
平衡因子 < 0 左旋

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

  1. 3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

  1.    1<br />      / \<br />     2   2<br />    / \<br />   3   3<br />  / \<br /> 4   4<br />返回 false 。

多路查找树

其中每一个结点的孩子树可以多于两个，且每一个结点处可以存储多个元素

2-3 树 2-3-4树 B树 B+树

2-3树

其中的每一个结点都具有两个孩子（2结点）或三个孩子（3结点）

一个2结点包含一个元素和两个孩子（或没有孩子）
一个3结点包含一小一大两个元素和三个孩子（或没有孩子）