每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021
加油!欢迎关注加我vx:xiaoda0423
,欢迎点赞、收藏和评论
时间:3 月 1 日 ~ 3 月 13 日
如果这篇文章有帮助到你,给个❤️关注,❤️点赞,❤️鼓励一下作者,接收好挑战了吗?文章公众号首发,关注 程序员哆啦A梦 第一时间获取最新的文章
❤️笔芯❤️~
栈,队列,链表,集合,字典和散列表
树是一种分层数据的抽象模型,最常见的树的例子是家谱或是公司的组织架构图。
二叉树和二叉搜索树
二叉搜索树数据结构
创建
BinarySearchTree
类
function BinarySearchTree() {
var Node = function(key){
// 声明一个Node类来表示树中的每个节点
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
}
insert(key)
,向树中插入一个新的键search(key)
,在树中查找一个键,如果节点存在,则返回true;如果不存在,则返回falseinOrderTraverse
,通过中序遍历方式遍历所有节点preOrderTraverse
,通过先序遍历方式遍历所有节点postOrderTraverse
,通过后序遍历方式遍历所有节点min
,返回树中最小的值/键max
,返回树中最大的值/键remove(key)
,从树中移除某个键向树中插入一个键
示例:
// 向树插入一个新键的算法
// 要向树中插入一个新的节点
this.insert = function(key){
var newNode = new Node(key); //创建用来表示新节点的Node类实例
// 只需要向构造函数传递我们想用来插入树的节点值,它的左指针和右指针的值会由构造函数自动设置为null
if (root === null){ //第二步要验证这个插入操作是否为一种特殊情况。
//这个特殊情况就是我们要插入的节点是树的第一个节点
root = newNode;
} else {
insertNode(root,newNode); //将节点加在非根节点的其他位置
}
};
// 将节点加在非根节点的其他位置
var insertNode = function(node, newNode){
// 传入树的根节点和要插入的节点
if (newNode.key < node.key){ //如果新节点的键小于当前节点的键
if (node.left === null){ //需要检查当前节点的左侧子节点
// 如果它没有左侧子节点
node.left = newNode; //就在那里插入新的节点
} else {
// 如果有左侧子节点,需要通过递归调用insertNode方法
insertNode(node.left, newNode); //继续找到树的下一层
// 下次将要比较的节点将会是当前节点的左侧子节点
}
} else {
if (node.right === null){
//如果节点的键比当前节点的键大,同时当前节点没有右侧子节点
node.right = newNode; //就在那里插入新的节点
} else {
insertNode(node.right, newNode);
//如果有右侧子节点,同样需要递归调用insertNode方法,但是要用来和新节点比较的节点将会是右侧子节点
}
}
};
示例:
var tree = new BinarySearchTree();
tree.insert(11);
树的遍历,遍历一棵树是指访问树的每个节点并对它们进行某种操作的过程(中序遍历的一种应用就是对树进行排序操作)
访问树的所有节点有三种方式:中序、先序和后序。
BST
所有节点的遍历方式(就是以从最小到最大的顺序访 问所有节点)// 中序遍历的一种应用就是对树进行排序操作
this.inOrderTraverse = function(callback){
// 接收一个回调函数作为参数
// 回调函数用来定义我们对遍历到的每个节点进行的操作
inOrderTraverseNode(root, callback); //接收一个节点和对应的回调函数作为参数
};
var inOrderTraverseNode = function (node, callback) {
if (node !== null) {
//要通过中序遍历的方法遍历一棵树,首先要检查以参数形式传入的节点是否为null
inOrderTraverseNode(node.left, callback); //递归调用相同的函数来访问左侧子节点
callback(node.key); //接着对这个节点进行一些操作
inOrderTraverseNode(node.right, callback); //然后再访问右侧子节点
}
};
function printNode(value){ //需要创建一个回调函数
console.log(value);
}
tree.inOrderTraverse(printNode);
//调用inOrderTraverse方法并将回调函数作为参数传入
示例:
this.preOrderTraverse = function(callback){
preOrderTraverseNode(root, callback);
};
preOrderTraverseNode方法的实现如下:
var preOrderTraverseNode = function (node, callback) {
if (node !== null) {
callback(node.key); //先序遍历和中序遍历的不同点是,先序遍历会先访问节点本身
preOrderTraverseNode(node.left, callback);
//然后再访问它的左侧子节点
preOrderTraverseNode(node.right, callback); //最后是右侧子节点
}
};
示例:
this.postOrderTraverse = function(callback){
postOrderTraverseNode(root, callback);
};
postOrderTraverseNode方法的实现如下:
var postOrderTraverseNode = function (node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback); //后序遍历会先访问左侧子节点
postOrderTraverseNode(node.right, callback); //然后是右侧子节点
callback(node.key); //最后是父节点本身
}
};
搜索树中的值
有三种执行的搜索类型:搜索最小值,搜索最大值,搜索特定的值
示例:
// 寻找树的最小键的方法
this.min = function() {
return minNode(root); //调用了minNode方法
// 传入树的根节点
};
var minNode = function (node) {
// 允许我们从树中任意一个节点开始寻找最小的键
if (node){
while (node && node.left !== null) { //遍历树的左边
node = node.left; //遍历树的左边
}
return node.key;
}
return null; //直到找到树的最下层
};
// 实现max方法
this.max = function() {
return maxNode(root);
};
var maxNode = function (node) {
if (node){
while (node && node.right !== null) { //沿着树的右边进行遍历
node = node.right; // 直到找到最右端的节点
}
return node.key;
}
return null;
};
搜索一个特定的值
// find、search或get方法来查找数据结构中的一个特定的值
this.search = function(key){
return searchNode(root, key);
//searchNode方法可以用来寻找一棵树或它的任意子树中的一个特定的值
};
var searchNode = function(node, key){
if (node === null){
//先要验证作为参数传入的node是否合法(不是null)。
//如果是null的话,说明要找的键没有找到,返回false。
return false;
}
if (key < node.key){ //如果要找的键比当前的节点小
return searchNode(node.left, key);
//那么继续在左侧的子树上搜索
} else if (key > node.key){
//如果要找的键比当前的节点大,那么就从右侧子节点开始继续搜索
return searchNode(node.right, key);
} else {
return true; //否则就说明要找的键和当前节点的键相等
// 就返回true来表示找到了这个键
}
};
移除一个节点
示例:
this.remove = function(key){
root = removeNode(root, key); //传入root和要移除的键作为参数
// root被赋值为removeNode方法的返回值
};
// removeNode方法的实现
var removeNode = function(node, key){
if (node === null){
//如果正在检测的节点是null,那么说明键不存在于树中,所以返回null
return null;
}
if (key < node.key) {
//如果要找的键比当前节点的值小
node.left = removeNode(node.left, key);
//就沿着树的左边找到下一个节点
return node; //
} else if (key > node.key){
//如果要找的键比当前节点的值大
node.right = removeNode(node.right, key);
//那么就沿着树的右边找到下一个节点
return node; //
} else { //键等于node.key
//第一种情况——一个叶节点 移除一个叶节点
if (node.left === null && node.right === null){
//第一种情况是该节点是一个没有左侧或右侧子节点的叶节点
// 给这个节点赋予null值来移除它
// 还需要处理指针
node = null; // 需要通过返回null来将对应的父节点指针赋予null值
return node; // 值已经是null了,父节点指向它的指针也会接收到这个值
// 要在函数中返回节点的值的原因
}
//第二种情况——一个只有一个子节点的节点
// 移除有一个左侧或右侧子节点的节点
if (node.left === null){ //如果这个节点没有左侧子节点
node = node.right; //也就是说它有一个右侧子节点
// 把对它的引用改为对它右侧子节点的引用
return node; //并返回更新后的节点
} else if (node.right === null){
//如果这个节点没有右侧子节点
node = node.left; //把对它的引用改为对它左侧子节点的引用
return node; //并返回更新后的值
}
//第三种情况——一个有两个子节点的节点
// 移除有两个子节点的节点
var aux = findMinNode(node.right); //
node.key = aux.key; //
node.right = removeNode(node.right, aux.key); //
return node; //
}
};
要移除有两个子节点的节点,需要执行四个步骤
// 找到了要找的键(键和node.key相等)
var findMinNode = function(node){
while (node && node.left !== null) {
node = node.left;
}
return node; // 在findMinNode中返回了节点
};
自平衡树
BST
存在一个问题:树的一条分支会有很多层,而其他的分支却只有几层的情况。
Adelson-Velskii-Landi 树(AVL 树)
AVL
树是一种自平衡二叉搜索树(任何一个节点左右两侧子树的高度之差最多为1)AVL
树的不同之处在于我们需要检验它的平衡因子,如果有需要,则将其逻辑应用于树的自平衡(hr)
和左子树高度(hl)
的差值,该值(hr-hl)
应为0、1或1
AVL
树-这就是平衡因子的概念。// 计算节点高度
var heightNode = function(node) {
if (node === null) {
return -1;
} else {
return Math.max(heightNode(node.left),
heightNode(node.right)) + 1;
}
};
// 替换insertNode方法的行
if ((heightNode(node.left) - heightNode(node.right)) > 1) {
// 旋转
}
向右子树插入新节点时,应用同样的逻辑
// 替换insertNode方法的行
if ((heightNode(node.right) - heightNode(node.left)) > 1) {
// 旋转
}
AVL
旋转:可以执行单旋转或双旋转两种平衡操作示例:
var insertNode = function(node, element) {
if (node === null) {
node = new Node(element);
} else if (element < node.key) {
node.left = insertNode(node.left, element);
if (node.left !== null) {
// 确认是否需要平衡
}
} else if (element > node.key) {
node.right = insertNode(node.right, element);
if (node.right !== null) {
// 确认是否需要平衡
}
}
return node;
};
一、题目描述
给定一个二叉树,检查它是否是镜像对称的。
image.png
二、思路分析
如果同时满足下面的条件,两个树互为镜像:
我们将根节点的左子树记做 left
,右子树记做 right
。比较 left
是否等于 right
,不等的话直接返回就可以了。
如果相当,比较 left
的左节点和 right
的右节点,再比较 left
的右节点和 right
的左节点。
终止条件:
left 和 right
不等,或者 left 和 right
都为空left,left
和 right.right
,递归比较 left,right 和 right.left
image.png
image.png
image.png
三、答案代码
var isSymmetric = function(root) {
if(!root) return true;
var stack = [root.left,root.right];
while(stack.length){
var p = stack.pop();
var q = stack.pop();
if (p === q) continue;
if (p && q && p.val === q.val) {
stack.push(p.left, q.right, p.right, q.left);
} else {
return false;
}
}
return true;
};
四、总结
对称二叉树,树