树是计算机中经常用到的一种数据结构,与列表不同,它是一种非线性的数据结构,以分层的方式来储存数据。像公司的组织架构,就可以理解成一棵树。
一棵树最上面的节点被称为根节点,在下图中,A
就是根节点。如果一个节点下面连接多个节点,该节点被称为父节点,它下面的节点被成为子节点,一个节点可以有0、1或多个子节点,没有子节点的节点被称为叶子节点。A
是 B
的父节点,B
是 A
的子节点。C
和 D
属于同一个父节点 B
,他们直接互相称之为兄弟,即互相为兄弟节点。C
、D
、F
、H
和 I
都是叶子节点。
二叉树是一种特殊的树,它的子节点个数不超过两个。上面的图就是一个二叉树。
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为 ,且结点总数是,则它就是满二叉树。[来自百度百科]。
我们发现,满二叉树的所有叶子节点都在最底层,而且除了叶子节点,其他的节点都有左右两个子节点。
看完满二叉树,来认识一下由其引出来的完全二叉树,可能光看字面意思不是很好理解。若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
对于大多数同学来说 ,满二叉树很好理解,但是到了完全二叉树可能就迷糊了,下面的图给出了几个完全二叉树和非完全二叉树的例子,相信你看了应该就明白是怎么回事了。
存储一棵二叉树,有两种方法,一种是基于指针或者引用的二叉链式存储,一种是基于数组的顺序存储。
先来看大家都比较熟悉、更加直观的链式存储结构。链式存储结构中,每一个结点包含三个关键属性:指向左子节点的指针,数据,指向右子节点的指针。
结构定义
class Node {public data: any;public left?: Node;public right?: Node;constructor({ data, left, right }) {this.data = data;this.left = left;this.right = right;}}
再来看基于数组的顺序存储,为了帮助大家更好地理解,这里拿了一张完全二叉树的图。使用顺序存储,完全二叉树是非常合适的,可以自上而下,从左到右来顺序存储 n 个结点的完全二叉树。
我们把根节点放到 ,那么根节点的左子节点存储在下标 的位置,右子节点存储在 的位置。依此类推,B 节点的左子节点存储在 的位置,右子节点存储在 的位置。
完全二叉树的这种存储结构,有以下特点:
非根节点的父节点对应数组下标为是
节点的左子节点的序号是 ,如果,则左子节点不存在
节点的右子节点的序号是,如果,则右子节点不存在
如果不是完全二叉树,用这种结构来存储会浪费比较多的空间,可以看下面的图。
因此,如果一棵树刚好是完全二叉树,采用顺序存储是最节省内存空间的,不需要额外再提供左右两个指针。
二叉树的常见的遍历方法有 3 种:前序遍历、中序遍历、和后序遍历,依据节点和它的左右子树的遍历顺序不同来划分。
前序遍历:对于二叉树中的任意节点,先访问该节点,再去访问当前节点的左子树,然后是右子树,若当前节点无左子树,则访问当前节点的右子树;
中序遍历:对于二叉树中的任意节点,先访问该节点的左子树,再去访问当前节点,然后是右子树;
后序遍历:对于二叉树中的任意节点,先访问该节点的左子树,再去访问当前节点的右子树,然后是当前节点;
二叉树是一种递归形式的数据结构,因此对于二叉树的 3 种遍历,我们就可以借助其自身的特性,通过递归实现。
// 前序遍历function preTraversal(node) {if (node === null) {return;}console.log(node.data);preTraversal(node.left);preTraversal(node.right);}// 中序遍历function inTraversal(node) {if (node === null) {return;}inTraversal(node.left);console.log(node.data);inTraversal(node.right);}// 后序遍历function postTraversal(node) {if (node === null) {return;}postTraversal(node.left);postTraversal(node.right);console.log(node.data);}
可以看到,使用递归实现二叉树的遍历十分简单。
二叉查找树(BST)是一种特殊的二叉树,较小的值保存在左子树中,较大的值保存在右子树中,这一特性使得 查找的效率很高。因此它又有另外一个名字,叫二叉排序树(Binary Sort Tree)。看了图是不是瞬间明白二叉查找树是个啥。
二叉查找树的查找
对于 BST 通常有以下 3 种类型的查找:
找给定值
找最小值
找最大值
根据二叉查找树的属性,查找最小值和最大值比较简单。因为较小的值总是在左子节点上,要找到最小值,只需要遍历左子树,直到找到最后一个节点。
function getMin() {let currentNode = this.tree;while (currentNode.left !== null) {currentNode = currentNode.left;}return currentNode.data;}
查找最大值也是同理,只需遍历右子树,直到找到最后一个节点即可。
function getMax() {let currentNode = this.tree;while (currentNode.right !== null) {currentNode = currentNode.right;}return currentNode.data;}
在 BST 上查找给定值,通过比较该值和当前节点上的值的大小,就能够确定向左还是向右遍历。
function find(data) {let node = this.tree;while (node !== null) {if (node.data === data) {return node;} else if (data < node.data) {node = node.left;} else {node = node.right;}}}
二叉查找树的插入
在二叉查找树中插入元素比较复杂,分为以下几种情况:
首先需要检查 BST 是否有根节点,如果没有,插入的节点就是根节点,就完事了
如果待插入的节点不是根节点,那么就需要遍历整棵树,找到合适的位置
如果要插入的数据大于当前节点,并且当前节点的右子树为空,就将新数据插入到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入位置。同理,如果要插入的数据小于当前节点,并且节点的左子树为空,就将新数据插入到左子节点的位置;如果不为空,就再递归遍历左子树,查找插入位置。
function insert(data) {const n = new Node(data);if (this.tree === null) {this.tree = n;return;}let node = this.tree;while (node !== null) {if (data > node.data) {if (node.right === null) {node.right = n;return;}node = node.right;} else {if (data < node.data) {if (ndoe.left === null) {node.left = n;return;}node = node.left;}}}}
二叉查找树的删除
在二叉查找树上删除节点的操作最复杂,牵一发而动全身,节点直接存在相互关联。如果删除的是没有子节点的节点,那就直接删掉就完事了。稍微麻烦的是删除节点只有一个子节点的情况,如果删除的节点包含两个子节点,那就是最麻烦的了。
如果没有子节点,直接把要删除的节点干掉就行
只有一个子节点只需要把更新父节点指向要删除节点的指针,指向要删除节点的子节点就可以了。比如图中删除节点的节点是 16,把 15 指向 13 的指针指向 20 即可。
现在来看最复杂的情况:
有两个子节点,我们需要查找右子树上的最小值,把它拿到待删除的节点上,然后再删除这个最小的节点。删除这个最小的节点,又回到了上面讲的两条规则,这个最小节点不可能有两个子节点,如果有左子节点,就不是最小节点了。
function remove(data) {let node = this.tree;let parentNode;while (node !== null && node.data != data) {parentNode = node;if (data > node.data) {node = node.right;} else {node = node.left;}}if (node === null) {return; // 没找着}// 我们采用非递归的方式,先处理要删除的节点有两个子节点的情况if (node.left !== null && node.right !== null) {// 查找右子树中最小节点let minNodeParent = node;let minNode = minNodeParent.right;while (minNodeParent.left !== null) {minNodeParent = minNode;minNode = minNode.left;}node.data = minNode.data;node = minNode; // 下面就变成删除 minNode 了parentNode = minNodeParent;}// 删除节点是叶子节点或者只有一个子节点let childNode = null;if (node.left !== null) {childNode = node.left;} else if (node.right !== null) {childNode = node.right;}if (parentNode === null) { // 父节点是 null,说明删除的是根节点this.tree = childNode;// 第二种情况,把父节点的指向删除节点的指针指向删除节点的子节点// 删除的是 node,把 parentNode 指向 node 的指针,指向 childNode} else if (parentNode.left === node) {parentNode.left = childNode;} else {parentNode.right = childNode;}}
本章节分为 4 个部分:
Part 1
最小栈
Shuffle an Array
将有序数组转换为二叉搜索树
Part 2
对称二叉树
二叉树的最大深度
验证二叉搜索树
Part 3
二叉树的层次遍历
二叉树的序列化与反序列化
Part 4
中序遍历二叉树
从前序与中序遍历序列构造二叉树
二叉搜索树中第 K 小的元素
Part 5
填充每个节点的下一个右侧节点指针
岛屿数量
二叉树的锯齿形层次遍历
阅读完本章节,你将有以下收获:
熟悉栈的数据结构,可以解决基本栈相关问题
掌握二叉树的概念
会用不同的方法去遍历二叉树,解决相关问题