专栏首页M不作声再也不用怕面试问二叉树了

再也不用怕面试问二叉树了

二叉树

二叉树是一种非常重要的数据结构。在算法题中经常会使用到,在面试中的占比也是非常大的。

先来说说树的定义。

树是由n(n>=1)个有限节点组成的一个由层级关系的集合。有以下特点:

  • 每个节点有零个或多个子节点;
  • 没有父节点的节点称为根节点;
  • 每个非根节点有且只有一个父节点;
  • 除根节点外,每个子节点可以分为多个不相交的子树。

简单来说,二叉树的就是每个节点最多有两个子节点的树

在二叉树中,又有两种特殊形态:满二叉树完全二叉树

满二叉树简单的来说就是,除最后一层无子节点外,所有节点都有两个子节点的树。

完全二叉树简单的说就是,深度为h、(1~h-1)层的节点数都达最大个数且第h层所有的节点都连续集中在树的左边的树。

二叉搜索树

二叉搜索树的定义为二叉搜索树中的每个节点的值都比它左子树上的大,比它右子树上的小

这种存储方式非常适合数据搜索,这是一种类似于折半查找的搜索方式,时间复杂度为O(logN)。

对二叉树有插入和删除节点操作。

插入节点比较简单,对比当前节点和插入节点的值,再从左或从右向下递归即可。

删除节点分为三种情况。

  • 删除的节点没有子节点,也就是叶子节点;
  • 删除的节点只有左子树或右子树;
  • 删除的节点既有左子树又有右子树。

对于第一种情况,直接删除即可。第二种情况也相对简单,删除节点后直接用子树替换该节点。

主要是第三种情况比较复杂,这时候又出现两个概念,叫前驱节点后继节点

中序遍历中,某个节点之前的节点叫做前驱节点,之后的叫做后继节点。

在删除节点时,如果该节点既有左子树又有右子树,使用该节点的最小后继节点代替该节点即可。

然后讲树的遍历。树的遍历分为深度优先和广度优先两种,其中深度优先又分为先序遍历、中序遍历、后序遍历,广度优先主要是层次遍历

常问的就是三种遍历的递归遍历和非递归遍历。先简单的说三种遍历方式的遍历顺序:

先序遍历:根、左、右;

中序遍历:左、根、右;

后续遍历:左、右、根。

二叉树的遍历

先序遍历的结果为:ABDECF。中序遍历的结果为:DBEAFC。后序遍历的结果为:DEBFCA。

层次遍历的结果为:ABCDEF。

递归遍历很简单,代码实现如下:

// 先序遍历
preTraversal() {
  this._pre(this.root)
}
_pre(node) {
  if (node) {
    console.log(node.value)
    this._pre(node.left)
    this._pre(node.right)
  }
}

// 中序遍历
midTraversal() {
  this._mid(this.root)
}
_mid(node) {
  if (node) {
    this._mid(node.left)
    console.log(node.value)
    this._mid(node.right)
  }
}

// 后序遍历
backTraversal() {
  this._back(this.root)
}
_back(node) {
  if (node) {
    this._back(node.left)
    this._back(node.right)
    console.log(node.value)
  }
}

非递归遍历需要使用到这种数据结构,每出栈一个节点就对其记录。

非递归先序遍历思路如下。先序遍历先访问左子树,而栈遵循的是先进后出的原则。所以顺序应该先入栈右节点后入栈左节点。大致顺序为,将根节点入栈,访问该根节点是否有子节点,如果有两个子节点,先入栈右节点,再入栈子节点,此时左节点在栈顶。访问该节点是否有子节点,重复上述操作(网上偷个图)。

先序非递归

非递归中序遍历思路。先将根节点入栈,然后一直访问左节点并入栈,直到为空。然后每出栈一个节点后,都对其访问,如果存在右节点则将其入栈,再向左访问子节点,并将其一一入栈,重复上述操作。

非递归后序遍历思路。将根节点入栈,并且一直向左访问子节点,一一入栈,直到为空。然后在出栈前对节点进行访问,如果有右节点,将其入栈,再一直向左访问子节点,重复上述操作。

中序和后序的区别就在于在根节点出栈前后访问入栈子节点

前边说二叉树的时间复杂度为O(logN),这是指一般情况下,或者说是平均复杂度。**在极端情况下,二叉树可能会退化成链表,**链表查找的事件复杂度为O(logN)明显性能差了很多,所以为了解决这个问题,出现了平衡二叉树。

平衡二叉树

AVL是自平衡二叉搜索树,在AVL中任何节点的两个子树高度差最大为1。当增加或删除之后导致树不在平衡时,需要通过一次或多次旋转再平衡这个树。

简单的讲,左旋就是将自己变为右孩子的左孩子右旋就是将自己变为左孩子的右孩子,两个互为逆操作。

图片的旋转

图左,将Q变为P的右节点,之后再将P原来的右节点变为Q的左节点。

图右,将P变为Q的左节点,之后在将Q原来的左节点变为P的右节点。

这样,在旋转之后中序遍历的结果不变。

前缀树

前缀树是一种有序树,用于保存关联数组,其中的键通常为字符串。

前缀树

可以用于找字符串的最长公共前缀。

- END -

本文分享自微信公众号 - 大前端合集(fe-stack),作者:M不作声

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树的实现、遍历及面试题

    如图就是一个树结构,最上边的叫「根节点」,最下边的叫「叶子节点」。根节点有多个子节点,叶子节点没有子节点。二叉树就是,每个节点最多有两个子节点的树。

    不作声
  • 自平衡二叉树实现及时间复杂度分析

    我们在遍历二叉树时,先一直往左遍历,于是我们发现,当一棵树的每个节点都只有一个子节点时,他就变成了一个链表,然后链表就说啊:

    不作声
  • 数据结构与算法

    树的遍历分为深度优先搜索和广度优先搜索。深度优先搜索有先序遍历、中序遍历、和后序遍历三种方式。广度优先搜索是层次遍历。

    不作声
  • js版本的(广、深)度优先搜索0. 前言1.队列、栈2.BFS1.1 矩阵形式的图的遍历1.2 树的BFS举例3.DFS

    广度优先搜索(BFS)和深度优先搜索(DFS),大家可能在oj上见过,各种求路径、最短路径、最优方法、组合等等。于是,我们不妨动手试一下js版本怎么玩。

    lhyt
  • 图论与图学习(二):图算法

    本文是其中第二篇,介绍了图算法。更多文章和对应代码可访问:https://github.com/maelfabien/Machine_Learning_Tuto...

    机器之心
  • 【算法专栏】二叉树的下一个节点

    给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

    ConardLi
  • PaperReading-图嵌入之node2vec

    不同于图像、自然语言这种欧式空间的数据,网络结构的数据——图,通常无法通过CNN或者RNN来处理,这就需要我们寻找其他的方法来处理图数据。图数据其实非常常见,例...

    beyondGuo
  • 什么是一致性Hash算法?

    可以将传入的 Key 按照 index=hash(key)%N 这样来计算出需要存放的节点。其中 hash 函数是一个将字符串转换为正整数的哈希映射方法,N 就...

    Java3y
  • JavaScript 技术篇-js只获取本节点text文本,不包含子节点

    innerText 和 textContent 都是获取所有节点的 firstChild.nodeValue 是获取本节点的text文本,不包含子节点的。

    小蓝枣
  • Zookeeper Shell

    本文主要讲解使用Zookeeper自带的客户端zkCli.sh来进行一些Zookeeper的一些基本操作,如创建删除节点等。

    shysh95

扫码关注云+社区

领取腾讯云代金券