遍历二叉树的九种算法-阿里云开发者社区

很久未更新博客了，翻出以前的一个算法集，做了些修改，发到这里，以飨读者。

　　算法是关于二叉树遍历的内容。二叉树遍历传统上一般有四种算法：1、递归前序遍历，2、递归中序遍历，3、递归后序遍历，４、非递归层次遍历（队列辅助）。这四种算法都是大学教课书《数据结构》上的内容，前三种都非常简单，最后一种略略复杂一点儿，这里就不赘述了，只给出javascript的源程序。

　　另外五种分别是：1、非递归前序遍历（单栈辅助），2、非递归中序遍历（单栈辅助），3、非递归后序遍历（单栈辅助），4、非递归后序遍历（双栈辅助），5、递归层次遍历。这五种算法中算法3、4不容易理解，可在Visual Studio中单步执行，并跟踪栈的状态。而算法5则非常精巧，层次遍历一般多选用队列辅助的算法，算法5的时间、空间效率并不比依靠队列辅助的层次遍历算法更低，但对学习递归思想非常有帮助，故这次翻出旧作时，一并加上了。

　　算法使用javascript编写，使用了javascript的自定义对象和为已有对象添加自定义方法的功能。下面是完整的HTML文件（单文件），直接保存后就可以运行了。

<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Algorithm Of Traversing Binary Tree - 梦辽软件</title>
<style type="text/css">
P{
font-family:宋体;
font-size:9pt;
}
</style>
</head>
<body>
二叉树遍历算法
白宇 - 梦辽软件工作室 - 博讯网络有限责任公司
2011.05.27
2013.04.13（增加递归层次遍历）
二叉树示意图：
<pre> 1
/ \
/ \
/ \
/ \
/ \
2 3
/ \ \
/ \ \
/ \ \
/ \ \
4 5 6
\ / / \
\ / / \
7 8 9 10
/ / / \ \
11 12 13 14 15</pre>
<script type="text/javascript">
function BTNode(value){ //自定义对象的构造函数
this.value=value;
this.left=null;
this.right=null;
}
//为Array对象添加自定义方法
Array.prototype.isEmpty=function(){return this.length==0;}; //用数组模拟栈或队，判空方法
//=============================================================
function show(value){ //显示二叉树的节点
document.write(value+" ");
}
function buildTree(){ //生成一颗如上图所示的二叉树
var root=new BTNode(1);
root.left=new BTNode(2);
root.right=new BTNode(3);
root.left.left=new BTNode(4);
root.left.right=new BTNode(5);
root.right.right=new BTNode(6);
root.left.left.right=new BTNode(7);
root.left.right.left=new BTNode(8);
root.right.right.left=new BTNode(9);
root.right.right.right=new BTNode(10);
root.left.left.right.left=new BTNode(11);
root.left.right.left.left=new BTNode(12);
root.right.right.left.left=new BTNode(13);
root.right.right.left.right=new BTNode(14);
root.right.right.right.right=new BTNode(15);
return root;
}
function preorder(root){ //递归前序遍历
if(root==null) return;
show(root.value); //显示根节点
preorder(root.left); //前序遍历左子树
preorder(root.right); //前序遍历右子树
}
function inorder(root){ //递归中序遍历
if(root==null) return;
inorder(root.left);
show(root.value);
inorder(root.right);
}
function postorder(root){ //递归后序遍历
if(root==null) return;
postorder(root.left);
postorder(root.right);
show(root.value);
}
function getDepth(root){ //递归层次遍历 - 获取二叉树深度
if(root==null) return 0;
var leftDepth=getDepth(root.left);
var rightDepth=getDepth(root.right);
return Math.max(leftDepth, rightDepth)+1; //返回+1表示加当前层
}
function showNodeOfLevel(root, level){ //递归层次遍历 - 遍历某一层节点
if(root==null||level<0) return;
if(level==0) show(root.value);
showNodeOfLevel(root.left, level-1);
showNodeOfLevel(root.right, level-1);
}
function levelorder(root){ //递归层次遍历
var depth=getDepth(root);
for(var i=0;i<depth;i++)
showNodeOfLevel(root, i)
}
function iterativePreorder(root){ //非递归前序遍历
var stack=[]; //模拟栈
stack.push(root);
do{
if((root=stack.pop())!=null){ //出栈
show(root.value);
stack.push(root.right); //右子节点入栈
stack.push(root.left); //左子节点入栈
}
}while(!stack.isEmpty());
}
function iterativeInorder(root){ //非递归中序遍历
var stack=[];
while(true){
for(;root!=null;rootroot=root.left) //将当前节点左子树的全部节点逐一入栈
stack.push(root);
if(stack.isEmpty()) break;
root=stack.pop();
show(root.value);
rootroot=root.right; //遍历右子树
}
}
function iterativeSingleStackPostorder(root){ //非递归后序遍历（单栈）
var stack=[],flag=root; //flag标识已经遍历过的节点
while(root!=null){ //逐一处理每个节点的左右子树
for(;root.left!=null;rootroot=root.left)
stack.push(root); //左子树的节点逐一入栈
while(root.right==null||root.right==flag){ //需判断上次遍历的节点是否是当前节点的右节点
show(root.value);
flag=root;
if(stack.isEmpty()) return;
root=stack.pop();
}
stack.push(root); //可能是重新将该节点入栈
rootroot=root.right; //转向右子树
}
}
function iterativeDoubleStackPostorder(root){ //非递归后序遍历（双栈）
var stack=[],result=[];
if(root!=null) stack.push(root);
while(!stack.isEmpty()){ //按照根左右顺序逐一入栈、出栈、二次入栈
result.push(root=stack.pop());
if(root.left!=null) stack.push(root.left);
if(root.right!=null) stack.push(root.right);
}
while(!result.isEmpty())
show(result.pop().value);
}
function iterativeLevelorder(root){ //非递归层次遍历
var queue=[]; //模拟队列
queue.unshift(root); //插入根节点到队列最前面
do{
if((root=queue.pop())!=null){ //从队列最后面取节点
show(root.value);
queue.unshift(root.left); //左子节点入队
queue.unshift(root.right); //右子节点入队
}
}while(!queue.isEmpty());
}
var root=buildTree();
document.write("递归前序遍历：");
preorder(root);
document.write("递归中序遍历：");
inorder(root);
document.write("递归后序遍历：");
postorder(root);
document.write("递归层次遍历：");
levelorder(root);
document.write("非递归前序遍历（单栈）：");
iterativePreorder(root);
document.write("非递归中序遍历（单栈）：");
iterativeInorder(root);
document.write("非递归后序遍历（单栈）：");
iterativeSingleStackPostorder(root);
document.write("非递归后序遍历（双栈）：");
iterativeDoubleStackPostorder(root);
document.write("非递归层次遍历（队列）：");
iterativeLevelorder(root);
document.write("");
</script>
</body>
</html>

运行截图：

本文转自 BlackAlpha 51CTO博客，原文链接：http://blog.51cto.com/mengliao/1178079，如需转载请自行联系原作者

遍历二叉树的九种算法

热门文章

最新文章

相关课程

相关电子书

相关实验场景