摘要：一个二叉树的例子先实现三种遍历的递归算法以作比较。先序遍历递归算法中序遍历递归算法先遍历到最左边的节点，然后输出后序遍历看完上面的递归遍历，下面对比一下非递归的二叉树遍历。终止条件最后树遍历完了自然就结束后序遍历
二叉树的递归遍历很简单就可以实现，二叉树非递归遍历却想不出来？那你可以看看下面的例子。
一个二叉树的例子var root = {
val: 1,
left: {
val: 2,
left: {
val: 4,
},
right:{
val:5
}
},
right: {
val: 3,
left: {
val: 6
},
right: {
val: 7
}
}
}
先实现三种遍历的递归算法以作比较。
function DLR(root){
if(root!=null){
console.log(root.val);
DLR(root.left);
DLR(root.right);
}
}
DLR(root)//1,2,4,5,3,6,7
function LDR(root){
if(root!=null){
LDR(root.left);//先遍历到最左边的节点，然后输出
console.log(root.val);
LDR(root.right);
}
}
LDR(root)//4,2,5,1,6,3,7
function LRD(root){
if(node!=null){
LRD(root.left);
LRD(root.right);
console.log(root.val);
}
}
LRD(root)//4,5,2,6,7,3,1
看完上面的递归遍历，下面对比一下非递归的二叉树遍历。你会发现递归真心简单。
非递归前序遍历function DLR(root){
var arr=[],res=[];
if(root!=null){
arr.push(root);
}
while(arr.length!=0){
var temp=arr.pop();
res.push(temp.val);
//这里先放右边再放左边是因为取出来的顺序相反
if(temp.right!=null){
arr.push(temp.right);
}
if(temp.left!=null){
arr.push(temp.left);
}
}
return res;
}
DLR(root)//1,2,4,5,3,6,7
非递归中序遍历//先把左边的，全部放进arr再输出，处理右边的。
function LDR(root){
var arr=[],res=[];
while(true){
while(root!=null){
arr.push(root);
root=root.left;
}
//终止条件：最后树遍历完了自然就结束
if(arr.length==0){
break;
}
var temp=arr.pop();
res.push(temp.val);
root=temp.right;
}
return res;
}
LDR(root)//4,2,5,1,6,3,7
function LRD(root){
var arr=[],res=[];
arr.push(root);
while(arr.length!=0){
var p=arr.pop();
res.push(p.val);
if(p.left!=null){
arr.push(p.left);
}
if(p.right!=null){
arr.push(p.right);
}
}
return res.reverse();
}
LRD(root)//4,5,2,6,7,3,1
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/88416.html
摘要：平衡二叉树代码实现根节点插入节点树为空树不为空比较小于往左走大于往右走空树树非空自平衡树插入新节点向左走向左子树拆入新节点，且节点的值小于其左子节点时，应该进行旋转。 平衡二叉树JS代码实现 var Tree = function() { var Node = function(value) { this.value = value; this....
摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。 树的简介 栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...
摘要：貌似大部分语言中的递归都差不多，之所以在标题加是因为搜了下后感觉网上用来描述这概念的不多，简单地说递归就是函数调用自己的过程。 貌似大部分语言中的递归都差不多， 之所以在标题加JS是因为搜了下后感觉网上用js来描述这概念的不多， 简单地说递归就是函数调用自己的过程。下面的栗子可以很直观地展示递归的执行过程： function rec(x){ if(x!==1){ console....
摘要：本文讨论二叉树的遍历，对节点的访问通过打印节点的值体现出来。从二叉树的根节点出发，遍历可分为三个环节访问节点打印节点的值遍历节点的左子树遍历节点的右子树不同环节执行的先后顺序产生了不同的遍历方式。至于二叉树的非递归遍历，且听下回分解。 相关概念 「树的遍历」 指按照一定规则不重复地访问树中所有节点的过程。「访问」指针对节点的操作，如打印节点的值，更新节点的值等。 本文讨论二叉树的遍历，...
阅读 769·2021-09-06 15:02
阅读 2409·2019-08-30 15:43
阅读 2118·2019-08-30 11:26
阅读 2347·2019-08-26 12:12
阅读 3511·2019-08-23 18:24
阅读 3220·2019-08-23 18:16
阅读 660·2019-08-23 17:02
阅读 2217·2019-08-23 15:34
