理论基础
二叉树种类
满二叉树
如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
如图所示：
image.png
这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。
完全二叉树
除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。满二叉树一定是完全二叉树。
image.png
二叉搜索树
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
-
它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树
image.png
平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
image.png
存储方式
链式存储
通过指针把分布在各个地址的节点串联一起。一般用这个。
image.png
线性存储
顺序存储的元素在内存是连续分布的
image.png
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
遍历方式
节点类型
- 根节点：树的最顶端的节点。（根节点只有一个）
- 子节点：除根节点之外，并且本身下面还连接有节点的节点。
- 叶子结点：自己下面不再连接有节点的节点（即末端），称为叶子节点（又称为终端结点）。度为0
根节点、子节点、叶子节点是什么？-CSDN博客
二叉树主要有两种遍历方式：
1、深度优先遍历：先往深走，遇到叶子节点再往回走。
2、广度优先遍历：一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式。
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：
- 深度优先遍历，一般可用栈
** 前序遍历（递归法，迭代法）
** 中序遍历（递归法，迭代法）
** 后序遍历（递归法，迭代法） - 广度优先遍历，一般用队列
** 层次遍历（迭代法）
这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
image.png
二叉树定义
class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
self.left = left
self.right = right
144. 二叉树的前序遍历 - 力扣（LeetCode）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def PreOrder(self, root: TreeNode, res):
if root is None:
return
res.append(root.val)
self.PreOrder(root.left, res)
self.PreOrder(root.right, res)
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.PreOrder(root, res)
return res
145. 二叉树的后序遍历 - 力扣（LeetCode）
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def PostOredr(self, root: TreeNode, res):
if root is None:
return
self.PostOredr(root.left, res)
self.PostOredr(root.right, res)
res.append(root.val)
return res
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.PostOredr(root,res)
return res
94. 二叉树的中序遍历 - 力扣（LeetCode）
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def InOredr(self, root:TreeNode, res):
if root is None:
return []
self.InOredr(root.left, res)
res.append(root.val)
self.InOredr(root.right, res)
return res
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.InOredr(root, res)
return res
