binarySearchTree二叉搜索树整理

所有数据结构中,我之前最不熟悉的是二叉树题型,因为个人问题从来没有静心去研究过,十一正好有时间,在家里整理了二叉搜索树(下面简称二叉树)基本的概念,希望自己不熟悉的常见题型会越来越少,也希望自己所学能为自己所用。

二叉树

满二叉树

所有分支结点都存在左右子树,并且所有叶子结点都在同一层上,这样即满二叉树。

  • 叶子结点都在最底层
  • 同样深度,结点个数最多,叶子树最多

完全二叉树

一个n个结点的二叉树按层序排列,所有结点与同样深度的满二叉树中的位置相同,这就是完全二叉树。

  • 叶子结点只能在最下一层(这不是最后一层,是最下层
  • 最下层叶子结点一定集中在左侧连续位置(来自于层序遍历的属性)
  • 次下层叶子结点(如有,但不一定有)一定集中在右侧连续位置(来自于层序遍历的属性)
  • 同样的结点个数,完全二叉树深度最小(满二叉树也是满足的,满二叉树一定是完全二叉树,反之不成立)

基本性质

一般二叉树性质(通性)

  • 非空二叉树,第i层最多有pow(2,i-1)个节点个数
  • 深度为k的二叉树上,最多有pow(2,k)-1个节点个数
  • 在一棵二叉树中,除了叶子结点(度为0,也就是没有叶子结点的结点),只有可能度为2(n2)和1(n1)的结点了。
    1
    2
    假设T为结点的总个数,T=n2+n1+n0;连边数很好理解为T-1,T-1=2*n2+n1;所以,n0=n2+1。
    换句话说,0度结点个数=2度结点个数+1。

完全二叉树(特性)

  • n个结点的完全二叉树的深度为log(2,n)+1
    1
    k层满二叉树的节点个数pow(2,k)-1,所以完全二叉树中的结点个数N必定满足N<=pow(2,k)-1,因为完全二叉树有满二叉树的排列性质,N必定也大于pow(2,k-1)-1。pow(2,k-1)-1<N<=pow(2,k)-1,易得pow(2,k-1)<N<=pow(2,k),k-1<log(2,N)<=k,k为整数,所以k=[log(2,N)]+1

二叉树遍历

最核心的概念

  • 左树上所有结点的值均小于或者等于它的根结点的值
  • 右树上所有结点的值均大于或者等于它的根结点的值
  • 左右树也分别为二叉树

最大/最小值点查找

最大值必然在右子树上,最小值点必定在左子树上

删除结点

  • 找到当前结点哪个子树非空,所有的剩下的值都在非空的这个子树上
  • 判断当前结点是父结点哪个子树,左子树还是右子树
  • 父结点对应的(左/右)子树用当前结点的非空子树覆盖

注意,如果左右子树都非空的话,把递归查找,找到右子树中的子树中第一次出现左子树为None的时候,把此子树的值赋值给要删除的结点,再把此子树的父结点的左子树用此子树的右子树进行覆盖

1
2
n.element = next.element
pre.lchild = next.rchild

先序遍历

    '''
    1、访问根结点
    2、先序遍历左子树
    3、先序遍历右子树
    '''

中序遍历

    '''
    1、中序遍历左子树
    2、访问根结点
    3、中序遍历右子树
    '''

后序遍历

    '''
    1、后序遍历左子树
    2、后序遍历右子树
    3、访问根结点
    '''

三种遍历方式最核心的是什么时候打印根节点,这决定了遍历逻辑。

层次遍历

利用了队列先进先出的性质。

以上代码都依旧完善在我的GitHub中:搜索二叉树,大家可以参考一下。

欢迎大家关注我的个人bolg知乎,更多代码内容欢迎follow我的个人Github,如果有任何算法、代码、转行疑问都欢迎通过邮箱发消息给我。

打赏的大佬可以联系我,赠送超赞的算法资料