Skip to content

Instantly share code, notes, and snippets.

@monjer

monjer/BTree.html

Last active December 18, 2015 14:28
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save monjer/5796995 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save monjer/5796995 to your computer and use it in GitHub Desktop.
Download ZIP
二叉树常用的几种遍历方式的Javascript简单实现,包括递归和非递归两种实现方式。
Raw
BTree.html
<! DOCTYPE html>
<html>
<head>
</head>
<body>
<script type="text/javascript">
function BTreeNode(data){
this.leftNode = null;
this.rightNode = null;
this.data = data ;
}
var root = new BTreeNode(1) ;
root.leftNode = new BTreeNode(2) ;
root.rightNode = new BTreeNode(3) ;
root.leftNode.leftNode = new BTreeNode(4) ;
root.leftNode.rightNode = new BTreeNode(5);
root.rightNode.leftNode = new BTreeNode(6) ;
root.rightNode.rightNode = new BTreeNode(7) ;
console.log('************ preOrderTraverse ************');
function preOrderTraverse(root){
var node = root;
var stack = [];
var print = '' ;
while(node || stack.length>0){
// 逐级遍历左侧根节点
while(node){
print += '->'+node.data ;
stack.push(node);
node = node.leftNode ;
}
if (stack.length > 0) {
node = stack.pop();
node = node.rightNode;
};
}
console.log(print);
}
// function preOrderTraverse(root){
// var node = root ;
// if (node) {
// console.log(node.data);
// preOrderTraverse(node.leftNode);
// preOrderTraverse(node.rightNode);
// }
// }
preOrderTraverse(root);
console.log('************ inOrderTraverse ************');
function inOrderTraverse(root){
var node = root ;
var stack = [] ;
var print ='';
while(node || stack.length>0){
// 找到最左侧的节点
while(node){
stack.push(node);
node = node.leftNode;
}
if (stack.length>0) {
node = stack.pop();
print +='->'+node.data ;
node = node.rightNode ;
};
}
console.log(print);
}
// function inOrderTraverse(root){
// var node = root ;
// if (node ) {
// inOrderTraverse(node.leftNode);
// console.log(node.data);
// inOrderTraverse(node.rightNode);
// }
// }
inOrderTraverse(root);
console.log('************ postOrderTraverse ************');
function postOrderTraverse(root){
var node = root ;
var stack = [] ;
var print = '' ;
stack.push(node);
var preAccessedNode = null ;
while(stack.length > 0){
node = stack[stack.length-1];
// 当前节点为空，或上一个访问到的节点时当前节点的子节点。
if ((!node.leftNode && !node.rightNode) || node.leftNode == preAccessedNode || node.rightNode == preAccessedNode) {
print += '->'+node.data ;
preAccessedNode = stack.pop();
}else{
//先添加右节点，保证遍历顺序
if(node.rightNode){
stack.push(node.rightNode);
}
if(node.leftNode){
stack.push(node.leftNode);
}
}
}
console.log(print);
}
// function postOrderTraverse(root){
// var node = root ;
// if (node) {
// postOrderTraverse(node.leftNode);
// postOrderTraverse(node.rightNode);
// console.log(node.data);
// }
// }
postOrderTraverse(root);
console.log('************ levelOrderTraverse ************');
function levelOrderTraverse(root){
var node = root ;
var stack = [] ;
var print = '' ;
stack.push(node);
while(stack.length > 0){
node = stack.shift();
print+='->'+node.data ;
if (node.leftNode) {
stack.push(node.leftNode);
}
if(node.rightNode){
stack.push(node.rightNode);
}
}
console.log(print);
}
levelOrderTraverse(root);
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment