树型数据结构广泛存在于现实世界中,比如家族族谱、企业职能架构等,它是一类在计算机领域被广泛应用的非线性数据结构.
二叉树是树型数据中最常用的一类,本文从前端角度以js语法构建和操作二叉树的相关知识.
观察上图,二叉树的数据结构如图所示.
树中每一个圆圈代表一个节点,其中根部的节点A称为根节点
B和C是A的子节点.子节点的个数称为度,A节点的度为2,D节点的度数为1.度为0的节点称之为叶子节点,比如图中的 H、E、F、G 都属于叶子节点
B节点的高度为3.二叉树的基本概念介绍完毕后,我们接下来使用js实现一棵二叉树.
二叉树由一个个节点组成,每一个节点可以通过类生成(代码如下).
class Node {
constructor(value){
this.value = value;
this.left = this.right = null;
}
}
this.value存储着当前节点的值,this.left是左节点,this.right是右节点.
定义单个节点的目标已经实现了,那如何将这些节点组合起来形成一颗二叉树呢?
假设存在数组[0,1,2,3,4,5,6],请将该数组转换成一颗二叉树(数据存储的顺序如下图).
观察图中数据的排列顺序.首先从数组中从左往右一一取出数据,顺着二叉树的第0层开始,自顶而下一层一层放置,每一层又从左往右的顺序安放数据.
合成二叉树的关键在于每生成一个节点,需要知道该节点的父节点是谁,其次要知道该节点属于父节点的左侧还是右侧.
从图中我们可以总结出以下规律:
1再求对数的结果都相等.例如第0层元素0加1再求对数向下取整等于0.第二层的元素1和2都加1再求对数取整都等于1.因此数组中每个元素的索引值i使用公式Math.floor(Math.log2(i+1))就得到该元素在二叉树中所处的层数.2的n次方减1,其中n等于该元素所处的层数.1.2向下取整就能得到父级在自己层处于第几个位置.比如元素4减去3除以2取整为0.那么父级元素就位于第1层第0个位置.而5号元素同理计算后父级处于第1层的第1个位置.通过以上几点规律,每个元素通过自己的索引值最终能够求出父级的索引,那二叉树的构建水到渠成(代码如下).
class Btree {
constructor(array){
this.transform(array);
return this.root;
}
transform(array){
const list = [];
array.forEach((item,index)=>{
if(item == null){ // 非空处理
list.push(null);
return;
}
const node = new Node(item);
list.push(node);
if(!this.root){
this.root = node;
return;
}
// 得到当前节点所处的层数
const layer = Math.floor(Math.log2(index + 1));
// 当前节点所在层数的首元素的索引
const first_index = Math.pow(2,layer) - 1;
// 父节点在其层处于第几个位置
const parent_position = Math.floor((index - first_index)/2);
// 父节点的层数
const parent_layer = layer -1;
// 父节点所在层数的首元素的索引
const parent_first_index = Math.pow(2,parent_layer) - 1;
// 父节点的索引值
const parent_index = parent_first_index + parent_position;
// 父元素的节点
const parent_node = list[parent_index];
if(parent_node.left == null){
parent_node.left = node;
}else{
parent_node.right = node;
}
})
list.length = 0;
}
}
/*
输出结果
Node {
value: 0,
right: Node {
value: 2,
right: Node { value: 6, right: null, left: null },
left: Node { value: 5, right: null, left: null }
},
left: Node {
value: 1,
right: Node { value: 4, right: null, left: null },
left: Node { value: 3, right: null, left: null }
}
}
*/
console.log(new Btree([0,1,2,3,4,5,6]));
module.exports = {
Btree,
Node
};
观察上图中的二叉树,请编写函数maxDepth找出二叉树的最大深度?
二叉树的最大深度为根节点到最远叶子节点的最长路径上的节点数.
例如上图中1 - 2 - 4 - 8这条路径上的节点数是4,而其他从根节点到叶子节点路径上的最大节点数才为3个,因此该二叉树的最大深度为4.
从图中可分析规律,二叉树的最大深度一定等于根节点与左子树某个叶子节点或者是右子树某个叶子节点形成路径的节点数的值中较大的那一个.
比如图中根节点1的最大深度等于节点2或者节点3的最大深度中更大的那一个加1.
而节点2的最大深度等于节点4或者节点5的最大深度中更大的那一个加1.节点3的最大深度同理可得.
最后经过层层递归,一定会到达最下层的叶子节点.叶子节点没有下一级,最大深度为1,能够成为递归的结束条件.
const { Btree } = require("./Btree");
function maxDepth(node){
if(node == null){
return 0;
}
return Math.max(maxDepth(node.left),maxDepth(node.right)) + 1;
}
const root = new Btree([1,2,3,4,5,6,7,8])
console.log(maxDepth(root)); // 4
一棵二叉树的直径长度是任意两个结点路径长度中的最大值.这条路径可能穿过也可能不穿过根结点.
观察上图,8 - 4 - 2 - 1 - 3 - 6和8 - 4 - 2 - 1 - 3 - 7是两条最长的路径,路径长度等于节点之间的边数,因此该二叉树的直径长度为5.
现给出一棵二叉树，请编写函数DiameterOfBTree计算它的直径长度?
计算直径长度其实是计算最大深度的延伸.依照计算最大深度的方法,根节点1的最大深度等于左右子树最大深度的较大值加1.
那么如果将根节点1的左子树的最大深度和右子树的最大深度相加就得出了穿过1节点这条路径的直径.
穿过根节点的直径长度不一定是最大的直径长度,比如下图中6 - 4 - 2 - 5 - 8 - 9就比穿过根节点的直径大.
1
/ \
2 3
/ \
4 5
/ \ / \
6 7 8 9
/
10
同理节点2作为左子树的根节点,它的直径等于它的左子树的最大深度加上右子树的最大深度.
因此可以定义一个全局变量max存储直径长度的最大值.递归计算最大深度的过程中,每计算出一条直径长度就与max比较,如果值比max大就赋值给max.递归结束后,max便等于整颗二叉树最大的直径长度.
const { Btree } = require("./Btree");
function DiameterOfBTree(node){
let max = 0;
(function maxDepth(node){
if(node == null){
return 0;
}
const maxLeftDepth = maxDepth(node.left);
const maxRightDepth = maxDepth(node.right);
const diameter = maxLeftDepth + maxRightDepth;
if(diameter > max){
max = diameter;
}
return Math.max(maxLeftDepth,maxRightDepth) + 1;
})(node);
return max;
}
const root = new Btree([1,2,3,4,5,6,7,8])
console.log(DiameterOfBTree(root)); // 5
一颗二叉树每个节点的左右两个子树的高度差的绝对值不超过1,此二叉树为平衡二叉树.
例如下列二叉树为平衡二叉树.
10
/ \
2 12
/ \
1 5
下列二叉树为非平衡二叉树.
10
/ \
2 12
/ \
1 5
/ \
11 13
请编写函数isBalanced判断二叉树是否为平衡二叉树?
判断平衡的关键条件是同一颗子树上的左右两个节点高度差不能大于1.
因此可以从根节点出发,递归求解左右子树的高度差.只要有一个高度差大于1,最终返回的结果就为false.
const { Btree } = require("./Btree");
function isBalanced(node){
let result = true;
function handler(node){
if(!node){
return 0;
}
const left_height = handler(node.left) + 1; // 左子树高度加1
const right_height = handler(node.right) + 1; // 右子树高度加1
if(!result){
return;
}
if(Math.abs(left_height - right_height) > 1){ // 只要有一个高度差大于1,最终结果就为false
result = false;
}
return Math.max(left_height,right_height);
}
handler(node);
return result;
}
console.log(isBalanced(new Btree([3,9,20,null,null,15,7]))); // true
console.log(isBalanced(new Btree([1,2,2,3,3,null,null,4,4]))); // false
如果一个树的左子树与右子树镜像对称,那么这个树是对称二叉树.
例如,下列二叉树[1,2,2,3,4,4,3,5,6,7,8,8,7,6,5] 是对称的.
1
/ \
2 2
/ \ / \
3 4 4 3
/\ /\ /\ /\
5 6 7 8 8 7 6 5
请编写函数isSymmetric验证一颗二叉树是否为对称二叉树?
分析上述对称二叉树的结构特征,根节点1下的左右子节点的值相等.
左子树2节点的左节点的值等于右子树2节点的右节点的值.左子树2节点的右节点的值等于右子树2节点的左节点的值.
比较完了第二层,将左子树2节点的左节点与右子树2节点的右节点继续按上述流程递归比较.同理左子树2节点的右节点和右子树2节点的左节点也按上述流程递归比较.
那么判断每一层是否对称的规律总结如下.
A和B的值相等A节点的左节点的值等于B节点右节点的值,A节点的右节点的值等于B节点左节点的值function isSymmetric(root){
function hanlder(nodeA,nodeB){
//两个节点一个为空,另一个不为空说明是不对称的
if((nodeA == null && nodeB != null) || (nodeA != null && nodeB == null)){
return false;
}
//两个节点都为空,这两个空节点是对称的
if(nodeA == null && nodeB == null){
return true;
}
//两个节点的值不相等是不对称的
if(nodeA.value != nodeB.value){
return false;
}
return hanlder(nodeA.left,nodeB.right) && hanlder(nodeA.right,nodeB.left);
}
return hanlder(root.left,root.right);
}
const tree = new Btree([1,2,2,3,4,4,3,5,6,7,8,8,7,6,5]);
console.log(isSymmetric(tree)); // true
二叉搜索树定义如下:
例如下面数据结构就是一颗二叉搜索树,当前节点的值小于右节点的值,大于左节点的值.子树也遵循此规律.
10
/ \
2 12
/ \ / \
1 5 11 13
构建二叉搜索树的思路很简单.每插入一个新节点,从根节点开始判断,大于根节点的值放右边,小于放左边.再继续递归执行上述过程,直到子节点为空时将新节点插入.
const { Node } = require("./Btree");
class Bst {
constructor(list = []){
this.root = new Node(list.shift());
list.forEach((item)=>{
this.add(new Node(item));
})
return this.root;
}
add(node){
if(!this.root){
this.root = node;
return;
}
let current = this.root;
let parent;
let direction;
while(current){
parent = current;
if(node.value > current.value){ // 相等值不插入
current = current.right;
direction = "RIGHT"; // 右侧
}else if(node.value < current.value){
current = current.left;
direction = "LEFT"; // 左侧
}else{
direction = null;
break;
}
}
if(direction == "LEFT"){
parent.left = node;
}else if(direction == "RIGHT"){
parent.right = node;
}
}
}
/*
Node {
value: 6,
right: Node {
value: 7,
right: Node { value: 8, right: null, left: null },
left: null
},
left: Node {
value: 2,
right: Node { value: 3, right: null, left: null },
left: null
}
}
*/
console.log(new Bst([6,2,3,7,8]));
module.exports = {
Bst
}
如果数据结构是这样的形式[{name:"张三",score:90},{name:"李四",score:100},{name:"王五",score:80}],那该如何用二叉搜索树进行存储呢?
解决方法很简单,只需要在原来基础上增加一个compare方法,这样比较大小的方式可以让外部函数自定义实现(代码如下).
class Bstv2 {
compare(valueA,valueB){
if(this.compareFun){
return this.compareFun(valueA,valueB);
}
return valueA - valueB;
}
constructor(list = [],compareFun){
this.compareFun = compareFun;
this.root = new Node(list.shift());
list.forEach((item)=>{
this.add(new Node(item));
})
return this.root;
}
add(node){
if(!this.root){
this.root = node;
return;
}
let current = this.root;
let parent;
let direction;
while(current){
parent = current;
if(this.compare(node.value,current.value)){ // 相等值不插入
current = current.right;
direction = "RIGHT"; // 右侧
}else if(this.compare(current.value,node.value)){
current = current.left;
direction = "LEFT"; // 左侧
}else{
direction = null;
break;
}
}
if(direction == "LEFT"){
parent.left = node;
}else if(direction == "RIGHT"){
parent.right = node;
}
}
}
/*
Node {
value: { name: '张三', score: 90 },
right: Node { value: { name: '李四', score: 100 }, right: null, left: null },
left: Node { value: { name: '王五', score: 80 }, right: null, left: null }
}
*/
console.log(new Bstv2([{name:"张三",score:90},{name:"李四",score:100},{name:"王五",score:80}],function(valueA,valueB){
return valueA.score > valueB.score;
}));
观察下面二叉树的结构特征,大的值放右边,小的值放左边,这样的数据结构已经做了二分处理.
10
/ \
2 12
/ \ / \
1 5 11 13
二叉搜索树由于在构建时将数据做了二分化的处理,所以它在处理大数据的查询和排序占据优势.
为了学习二叉搜索树的查询和排序,先要了解常用的四种遍历方式.
以上面二叉树举例.前序遍历先访问节点10,再访问左节点2,后访问右节点12.
访问左节点2的过程中,又递归执行上面流程.先访问节点2,再访问左节点1,后访问右节点5.左子树访问完毕,开始访问右子树.同理节点12递归执行上述流程.
层序遍历的过程:先访问节点10,再访问第二层2和12,后访问第三层1、5、11和13.
下面用代码分别演示四种遍历方式.
const { Bst } = require("./Bst");
const root = new Bst([10,2,12,1,5,11,13]);
// 前序遍历
function preorderTraversal(node,callback){
if(!node){
return;
}
callback(node);
preorderTraversal(node.left,callback);
preorderTraversal(node.right,callback);
}
console.log(preorderTraversal(root,function(node){
console.log(node.value); // 10 2 1 5 12 11 13
}));
// 中序遍历
/**
从结果可以看出,中序遍历的结果等于从小到大排序后的结果.利用中序遍历,我们在一些大数据的场景能快速得到
排序后的序列.
*/
function midTraversal(node,callback){
if(!node){
return;
}
midTraversal(node.left,callback);
callback(node);
midTraversal(node.right,callback);
}
console.log(midTraversal(root,function(node){
console.log(node.value); // 1 2 5 10 11 12 13
}));
// 后续遍历
function postorderTraversal(node,callback){
if(!node){
return;
}
postorderTraversal(node.left,callback);
postorderTraversal(node.right,callback);
callback(node);
}
console.log(postorderTraversal(root,function(node){
console.log(node.value); // 1 5 2 11 13 12 10
}));
// 层序遍历
function postorderTraversal(node,callback){
const array = [node];
for(let i = 0;i<array.length;i++){
const item = array[i];
if(!item){
return;
}
callback(item);
array.push(item.left);
array.push(item.right);
}
}
console.log(postorderTraversal(root,function(node){
console.log(node.value); // 10 2 12 1 5 11 13
}));
从二叉搜索树中查询某元素,查到了返回true,没有查到返回false.
const { Bst } = require("./Bst");
const root = new Bst([10,2,12,1,5,11,13]);
function search(node,value){
if(!node){
return false;
}
else if(node.value == value){
return true;
} else if(value > node.value){
return search(node.right,value);
}else{
return search(node.left,value);
}
}
console.log(search(root,12)); // true
console.log(search(root,100)); // false
二叉搜索树类似结构如下.请编写函数reverse将其翻转?
10
/ \
2 12
/ \ / \
1 5 11 13
翻转后的二叉树结构如下:
10
/ \
12 2
/ \ / \
13 11 5 1
通过利用前面学习的遍历方式,翻转功能轻易实现.
const { Bst } = require("./Bst");
function reverse(root){
function preorderTraversal(node){
if(!node){
return;
}
const tmp = node.left; // 左右节点进行交换
node.left = node.right;
node.right = tmp;
preorderTraversal(node.left);
preorderTraversal(node.right);
}
preorderTraversal(root);
return root;
}
const root = new Bst([10,2,12,1,5,11,13]);
/*
Node {
value: 10,
right: Node {
value: 2,
right: Node { value: 1, right: null, left: null },
left: Node { value: 5, right: null, left: null }
},
left: Node {
value: 12,
right: Node { value: 11, right: null, left: null },
left: Node { value: 13, right: null, left: null }
}
}
*/
console.log(reverse(root));
判断一棵树是否是二叉搜索树?
二叉搜索树的判断标准是节点的值要大于左节点的值,小于右节点的值,不满足此条件返回false.
const { Bst } = require("./Bst");
function isBst(node){
if(!node){
return true;
}
if( (node.right && node.value >= node.right.value) || (node.left && node.value <= node.left.value)){
return false;
}
return isBst(node.left) && isBst(node.right);
}
const root = new Bst([10,2,12,1,5,11,13]);
console.log(isBst(root)); // true
console.log(isBst(reverse(root))); // false