内容简介:前两天接到了蚂蚁金服的面试电话,面试官很直接,上来就抛出了三道算法题。。。其中有一道关于二叉树实现中序遍历的,当时没回答好,所以特意学习了一把二叉树的知识,行文记录总结。节点: 树中的每个元素称为一个节点,
前两天接到了蚂蚁金服的面试电话,面试官很直接,上来就抛出了三道算法题。。。
其中有一道关于二叉树实现中序遍历的,当时没回答好,所以特意学习了一把二叉树的知识,行文记录总结。
二叉树&二叉查找树
树相关术语:
节点: 树中的每个元素称为一个节点,
根节点: 位于整棵树顶点的节点,它没有父节点, 如上图 5
子节点: 其他节点的后代
叶子节点: 没有子节点的元素称为叶子节点, 如上图 3 8 24
二叉树:二叉树就是一种数据结构, 它的组织关系就像是自然界中的树一样。官方语言的定义是:是一个有限元素的集合,该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。
二叉查找树: 二叉查找树也叫二叉搜索树(BST),它只允许我们在左节点存储比父节点更小的值,右节点存储比父节点更大的值,上图展示的就是一颗二叉查找树。
代码实现
首先创建一个类来表示二叉查找树,它的内部应该有一个Node类,用来创建节点
function BinarySearchTree () { var Node = function(key) { this.key = key, this.left = null, this.right = null } var root = null } 复制代码
它还应该有一些方法:
- insert(key) 插入一个新的键
- inOrderTraverse() 对树进行中序遍历,并打印结果
- preOrderTraverse() 对树进行先序遍历,并打印结果
- postOrderTraverse() 对树进行后序遍历,并打印结果
- search(key) 查找树中的键,如果存在返回true,不存在返回fasle
- findMin() 返回树中的最小值
- findMax() 返回树中的最大值
- remove(key) 删除树中的某个键
向树中插入一个键
向树中插入一个新的键,首页应该创建一个用来表示新节点的Node类实例,因此需要new一下Node类并传入需要插入的key值,它会自动初始化为左右节点为null的一个新节点
然后,需要做一些判断,先判断树是否为空,若为空,新插入的节点就作为根节点,如不为空,调用一个辅助方法insertNode()方法,将根节点和新节点传入
this.insert = function(key) { var newNode = new Node(key) if(root === null) { root = newNode } else { insertNode(root, newNode) } } 复制代码
定义一下insertNode() 方法,这个方法会通过递归得调用自身,来找到新添加节点的合适位置
var insertNode = function(node, newNode) { if (newNode.key <= node.key) { if (node.left === null) { node.left = newNode }else { insertNode(node.left, newNode) } }else { if (node.right === null) { node.right = newNode }else { insertNode(node.right, newNode) } } } 复制代码
完成中序遍历方法
要实现中序遍历,我们需要一个inOrderTraverseNode(node)方法,它可以递归调用自身来遍历每个节点
this.inOrderTraverse = function() { inOrderTraverseNode(root) } 复制代码
这个方法会打印每个节点的key值,它需要一个递归终止条件————检查传入的node是否为null,如果不为空,就继续递归调用自身检查node的left、right节点 实现起来也很简单:
var inOrderTraverseNode = function(node) { if (node !== null) { inOrderTraverseNode(node.left) console.log(node.key) inOrderTraverseNode(node.right) } } 复制代码
先序遍历、后序遍历
有了中序遍历的方法,只需要稍作改动,就可以实现先序遍历和后序遍历了 上代码:
这样就可以对整棵树进行中序遍历了
// 实现先序遍历 this.preOrderTraverse = function() { preOrderTraverseNode(root) } var preOrderTraverseNode = function(node) { if (node !== null) { console.log(node.key) preOrderTraverseNode(node.left) preOrderTraverseNode(node.right) } } // 实现后序遍历 this.postOrderTraverse = function() { postOrderTraverseNode(root) } var postOrderTraverseNode = function(node) { if (node !== null) { postOrderTraverseNode(node.left) postOrderTraverseNode(node.right) console.log(node.key) } } 复制代码
发现了吧,其实就是内部语句更换了前后位置,这也刚好符合三种遍历规则:先序遍历(根-左-右)、中序遍历(左-根-右)、中序遍历(左-右-根)
先来做个测试吧
现在的完整代码如下:
function BinarySearchTree () { var Node = function(key) { this.key = key, this.left = null, this.right = null } var root = null //插入节点 this.insert = function(key) { var newNode = new Node(key) 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(node.left, newNode) } }else { if (node.right === null) { node.right = newNode }else { insertNode(node.right, newNode) } } } //实现中序遍历 this.inOrderTraverse = function() { inOrderTraverseNode(root) } var inOrderTraverseNode = function(node) { if (node !== null) { inOrderTraverseNode(node.left) console.log(node.key) inOrderTraverseNode(node.right) } } // 实现先序遍历 this.preOrderTraverse = function() { preOrderTraverseNode(root) } var preOrderTraverseNode = function(node) { if (node !== null) { console.log(node.key) preOrderTraverseNode(node.left) preOrderTraverseNode(node.right) } } // 实现后序遍历 this.postOrderTraverse = function() { postOrderTraverseNode(root) } var postOrderTraverseNode = function(node) { if (node !== null) { postOrderTraverseNode(node.left) postOrderTraverseNode(node.right) console.log(node.key) } } } 复制代码
竟然已经完成了添加新节点和遍历的方式,我们来测试一下吧:
定义一个数组,里面有一些元素
var arr = [9,6,3,8,12,15]
我们将arr中的每个元素依此插入到二叉搜索树中,然后打印结果
var tree = new BinarySearchTree() arr.map(item => { tree.insert(item) }) tree.inOrderTraverse() tree.preOrderTraverse() tree.postOrderTraverse() 复制代码
运行代码后,我们先来看看插入节点后整颗树的情况:
输出结果
中序遍历: 3 6 8 9 12 15
先序遍历: 9 6 3 8 12 15
后序遍历: 3 8 6 15 12 9
很明显,结果是符合预期的,所以,我们用上面的JavaScript代码,实现了对树的节点插入,和三种遍历方法,同时,很明显可以看到,在二叉查找树树种,最左侧的节点的值是最小的,而最右侧的节点的值是最大的,所以二叉查找树可以很方便的拿到其中的最大值和最小值
查找最小、最大值
怎么做呢?其实只需要将根节点传入minNode/或maxNode方法,然后通过循环判断node为左侧(minNode)/右侧(maxNode)的节点为null
实现代码:
// 查找最小值 this.findMin = function() { return minNode(root) } var minNode = function(node) { if (node) { while (node && node.left !== null) { node = node.left } return node.key } return null } // 查找最大值 this.findMax = function() { return maxNode(root) } var maxNode = function (node) { if(node) { while (node && node.right !== null) { node =node.right } return node.key } return null } 复制代码
所搜特定值
this.search = function(key) { return searchNode(root, key) } 复制代码
同样,实现它需要定义一个辅助方法,这个方法首先会检验node的合法性,如果为null,直接退出,并返回fasle。如果传入的key比当前传入node的key值小,它会继续递归查找node的左侧节点,反之,查找右侧节点。如果找到相等节点,直接退出,并返回true
var searchNode = function(node, key) { if (node === null) { return false } if (key < node.key) { return searchNode(node.left, key) }else if (key > node.key) { return searchNode(node.right, key) }else { return true } } 复制代码
移除节点
移除节点的实现情况比较复杂,它会有三种不同的情况:
-
需要移除的节点是一个叶子节点
-
需要移除的节点包含一个子节点
-
需要移除的节点包含两个子节点
和实现搜索指定节点一元,要移除某个节点,必须先找到它所在的位置,因此移除方法的实现中部分代码和上面相同:
// 移除节点 this.remove = function(key) { removeNode(root,key) } var removeNode = function(node, key) { if (node === 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{ //需要移除的节点是一个叶子节点 if (node.left === null && node.right === null) { node = null return node } //需要移除的节点包含一个子节点 if (node.letf === 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, axu.key) return node } } var findMinNode = function(node) { if (node) { while (node && node.left !== null) { node = node.left } return node } return null } 复制代码
其中,移除包含两个子节点的节点是最复杂的情况,它包含左侧节点和右侧节点,对它进行移除主要需要三个步骤:
- 需要找到它右侧子树中的最小节点来代替它的位置
- 将它右侧子树中的最小节点移除
- 将更新后的节点的引用指向原节点的父节点
有点绕儿,但必须这样,因为删除元素后的二叉搜索树必须保持它的 排序 性质
测试删除节点
tree.remove(8) tree.inOrderTraverse() 复制代码
打印结果:
3 6 9 12 15
8 这个节点被成功删除了,但是对二叉查找树进行中序遍历依然是保持排序性质的
到这里,一个简单的二叉查找树就基本上完成了,我们为它实现了,添加、查找、删除以及先中后三种遍历方法
存在的问题
但是实际上这样的二叉查找树是存在一些问题的,当我们不断的添加更大/更小的元素的时候,会出现如下情况:
tree.insert(16) tree.insert(17) tree.insert(18) 复制代码
来看看现在整颗树的情况:
很容易发现,它是不平衡的,这又会引出平衡树的概念,要解决这个问题,还需要更复杂的实现,例如:AVL树,红黑树 哎,之后再慢慢去学习吧
关于实现二叉排序树,我也找到慕课网的一系列的视频: Javascript实现二叉树算法 , 内容和上述实现基本一致
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 数据结构和算法(Golang实现)(27)查找算法-二叉查找树
- Java实现二分查找算法
- 二叉查找数 golang实现
- 二维数组中的查找如何实现?看图!
- 【PHP 实现数据结构】二叉查找树
- 如何用 Go 编码实现查找 DNS 记录
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。