首页 > 代码库 > 二叉树的前序、中序、后序遍历
二叉树的前序、中序、后序遍历
一、先序遍历：
1) 递归实现
function preOrder(root){if(root!=null){ console.log(root); preOrder(root.leftChild); preOrder(root.rightChild); }
}
2) 非递归实现
function preOrder(root){ var arr=[]; var temp=[]; temp.push(root); while(temp!=null){ var a=temp.pop(); arr.push(a); temp.push(a.rightChild); temp.push(a.leftChild); } return arr;}
function preOrder(root){ var temp=[]; var result=[]; var node=root; while(node!=null||temp.length>0){ if(node!=null){ result.push(node); temp.push(node); node=node.leftChild; }else{ node=temp.pop(); node=node.rightChild(); } } return result;}
二、中序遍历
1) 递归
function inOrder(root){ if(root!=null){ inOrder(root.leftChild); console.log(root); inOrder(root.rightChild); }}
2) 非递归
function inOrder(root){ var arr=[]; var result=[]; var node=root; while(node!=null||arr.length>0){ if(node!=null){ arr.push(node); node=node.leftChild; }else{ node=arr.pop(); result.push(node); node=node.rightChild; } } return result;}
三、后序遍历
1) 递归
function postOrder(root){ if(root!=null){ postOrder(root.leftChild); postOrder(root.rightChild); console.log(root); }}
2) 非递归
function postOrder(root){ var temp1=[]; var temp2=[]; var result=[]; var node=root; while(node!=null||temp1.length>0){ if(node!=null){ temp1.push(node); temp2.push(node); node=node.rightChild; }else{ node=temp1.pop(); node=node.leftChild; } } while(temp2.length>0){ result.push(temp2.pop()); } return result;}
二叉树的前序、中序、后序遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。