二叉树,二叉搜索树,AVL树,B树,B+树

二叉树树形结构,但是树中每个节点的分支最多只有两个,我们叫做二叉树 二叉搜索树(BST)!> 二叉搜索树又叫二叉排序树,或二叉查找树。它或者是一颗空树或者是具有下列性质的二叉树: 若它的左子树不为空,则左子树上的所有节点的值均小于它的根节点的值 若它的右子树不为空,则右子树上的所有节点的值均大于它的根节点的值 它的左右子树也分别是二叉排序树 平衡二叉树(AVL)!> 平衡二叉...

二叉树的三种遍历方式

基于递归的遍历

树形DP套路

步骤

  1. 以某个节点X为头结点的子树中,分析答案有哪些可能性,并且这种分析是以X的左子树,X的右子树,和X整棵树的角度来考虑可能性的
  2. 根据第一步分析的可能性,列出所需要的信息,例如在二叉树是否平衡中,左子树和右子树都需要知道各自是否平衡,以及高度这两个信息。
  3. 根据第二步信息汇总,定义自己的信息结构体
  4. 设计递归函数,递归函数是处理以X为头结点的情况相爱的答案,包括设计递归函数的base case,默认直接得到左树和右树所有的信息,以及把可能性左整合,并且返回第三步的信息结构这4个小步骤。