一起实现下二叉树的遍历算法。欢迎大家帮忙指出不当之处,或者进行深入的挖掘。大家一起进步。
二叉树的遍历算法有什么
二叉树呐,有三种遍历算法,1:中序遍历,2:先序遍历,3:后序遍历。在我们看具体实现之前,我们想下为什么要这样做?二叉树广泛应用于大量数据查找的业务中,可以实现更高效率的查找。
1:中序遍历,即先查找左节点,接着查找根节点,最后查找右节点。不论中序,先序,后序都是以根节点为依据的。下面上代码
functioninOrder(node){
if(!node===null&&nodeinstanceofBst)
inOrder(node.left)
console.log(node.data)
inOrder(node.right)
}
2:先序遍历:
functioninOrder(node){
if(!node===null&&nodeinstanceofBst)
console.log(node.data)
inOrder(node.left)
inOrder(node.right)
}
后序遍历类似,相信大家也能招到一定规律了。
二叉树的遍历概念
首先我们要知道前序遍历:中序遍历,后序遍历的概念:
前序遍历:从双亲节点开始,遍历左树,再遍历右树;
中序遍历:从左树开始,再遍历双亲节点,最后遍历右树;
后序遍历:从左树开始,再遍历右树,最后遍历双亲节点;
核心算法很简单:创建一个数组,将当前的节点递归,算法不同处只是在于数组加入node节点的次序不一样:
//前序算法
functionbeforeErgodic(node){
if(!!node){
arr.push(node);
beforeErgodic(node.firstElementChild);
beforeErgodic(node.lastElementChild);
}
}
//中序算法
functionmiddleErgodic(node){
if(!!node){
middleErgodic(node.firstElementChild);
arr.push(node);
middleErgodic(node.lastElementChild);
}
}
总之,二叉树的遍历算法给大家简单的介绍了一些,希望大家多看看。