代码随想录算法训练营 | 二叉树理论底子

二叉树理论底子

二叉树的种类

满二叉树

满二叉树的每个节点要么是叶子节点，要么拥有两个子节点，而且全部叶子节点都处于同一层。
如果一个满二叉树的高度为 h，那么它有2h-1个节点。

完全二叉树

完全二叉树除了末了一层之外，每一层都是完全填满的，而且末了一层的全部节点都从左往右以此分列，中心不答应出现空缺。
与满二叉树差别，完全二叉树答应末了一层不满，但节点必须只管靠左。
设层数为 h，每一层包罗1~2h-1个节点。

二叉搜刮树

二叉搜刮树是一个有序树。

• 对于恣意一个节点 N，左子树中全部节点的值都小于 N 的值。
  
• 对于恣意一个节点 N，右子树中全部节点的值都大于 N 的值。
  
• 左右子树自己也都是二叉搜刮树。
  

平衡二叉搜刮树

对于平衡二叉树中的每个节点，其左右子树的高度差不高出1，而且左右两个子树都是一棵平衡二叉树。（大概是一颗空树）
平衡二叉搜刮树（AVL树），既要满足二叉搜刮树的排序特性，又要满足平衡二叉树的平衡性。

二叉树存储方式

链式存储

链式存储使用指针，通过指针把分布在各个地点的节点串联一起：

次序存储

次序存储使用数组，常用于完全二叉树。
对于一个存储在数组 arr 中的二叉树节点，父节点、左子节点、右子节点的关系如下：

• 父节点索引：i
  
• 左子节点索引：2 * i + 1
  
• 右子节点索引：2 * i + 2
  

二叉树遍历方式

深度优先搜刮

沿着一个分支不绝遍历到叶子节点，然后回溯，继续遍历其他分支，分为前序遍历、中序遍历和后序遍历，一样平常借助栈使用递归法。
名字里的前中后指的是中心节点的遍历次序

• 前序遍历：根节点 → 左子树 → 右子树
  
• 中序遍历：左子树 → 根节点 → 右子树
  
• 后序遍历：左子树 → 右子树 → 根节点
  

广度优先搜刮

层序遍历，按层从左到右访问每一层的节点，通常使用队列实现。
二叉树的界说

链式存储界说如下：

1. public class TreeNode {
2.     int val;
3.     TreeNode left;
4.     TreeNode right;
6.     TreeNode() {}
7.     TreeNode(int val) { this.val = val; }
8.     TreeNode(int val, TreeNode left, TreeNode right) {
9.         this.val = val;
10.         this.left = left;
11.         this.right = right;
12.     }
13. }

复制代码

TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
[code][/code]