树、二叉树、二叉搜索树

树

特点

• 仅有唯一一个根节点，没有节点则为空树
• 除根节点外，每个节点都有并仅有唯一一个父节点
• 节点间不能形成闭环

深度和高度

• 节点的深度：从根节点到该节点所经历的边的个数，如节点 B 的高度为 2
• 节点的高度 ：节点到叶节点的最长路径，如节点 B 的深度为 1
• 树的高度：根节点的高度

二叉树

特点

• 最多仅有两个子节点的树

class 代码

public class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int val) {
      this.val = val;
      this.left = null;
      this.right = null;
  }
}

前中后序遍历

• 前序遍历：根左右

• 中序遍历：左根右

• 后序遍历：左右根

• 递归代码

  void dfs(TreeNode root) {
  		if (root==null) return;
  		dfs(root.left);
  		System.out.println(root.val);
  		dfs(root.right);
  }

• 逆推树：通过前（后）序找根节点，通过中序找左右节点

  前序遍历：FCADBEHGM 中序遍历：ACBDFHEMG

  1. 根据前序知 F 是根节点，根据中序知 ACBD 是左子树，HEMG 是右子树
  2. 根据前序知 C 是左子树的根节点，根据中序知 A 是 C 的左节点，BD 是 C 的右子树
  3. 根据前序知 D 是右子树的根节点，根据中序知 B 是 D 的左节点
  4. 根节点的右子树同理

  

  中序遍历：ACBDFHEMG 后序遍历：ABDCHMGEF

  1. 根据后序的最后一个值知 F 是根节点，根据中序知 ACBD 是左子树，HEMG 是右子树

  2. 根据后序找 ACBD 的顺序，得 ABDC，C 是最后一个节点，知其为左子树的根节点

  3. 根据中序知 A 是 C 的左节点，BD 是 C 的右子树

  4. 根据后序知 D 是根节点，根据中序知 B 是 D 的左节点

  5. 根节点的右子树同理

  6. 得到的树同上

二叉搜索树

别称

• 有序二叉树
• 排序二叉树

特点

• 左子树上所有结点的值均小于它的根结点的值
• 右子树上所有结点的值均大于它的根结点的值
• 左、右子树也分别为二叉查找树
• 中序遍历：升序排列

时间复杂度

插入、删除、查询均为 O(logn)

图解

• 查询 32

• 插入 45

• 删除 65