js遍历二叉树
javascript遍历二叉树
本文记录JavaScript对二叉树的一些常见遍历算法。
以下为一个二叉树的模拟结构：
var tree = {
value: 1,
left: {
value: 2,
left: {
value: 4
}
},
right: {
value: 3,
left: {
value: 5,
left: {
value: 7
},
right: {
value: 8
}
},
right: {
value: 6
}
}
};
对一个树的遍历分为先序遍历、中序遍历和后序遍历。若以以下表示顺序法： D：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树表示遍历顺序的话，
先序遍历：以从上到下，从左到右的顺序遍历；(DLR)
中序遍历：以从下到上，从左到右的顺序遍历；(LDR)
后序遍历：以从左到右，从下到上的顺序遍历；(LRD)
以上遍历均为 深度优先遍历 ，还有一种为 广度优先遍历。
广度优先遍历：是以树的层级为遍历的原则的，首选从上到下遍历层，遍历层时以从左到右的原则将个整层遍历完后才会遍历下一个层级。
以下为代码实现：
广度优先遍历：
首先将根节点归入队列。当队列不为空的时候，执行循环：取出队列的一个节点，如果该结点的左子树为非空，则将该结点的左子树入队列；如果该结点的右子树为非空，则将该结点的右子树入队列。
其实就是把节点以队列的形式存放，抛出先存放的节点，获取其子节点存入队列，这样便实现了以层的形式去遍历。
若不是二叉树而是树，则需要遍历该节点下的亲子节点存入队列，就可以实现对树的遍历
var levelOrderTraversal = function(node) {
if(!node) {
throw new Error('Empty Tree');
}
var que = [];
que.push(node);
while(que.length !== 0) {
node = que.shift();
console.log(node.value);
if(node.left) que.push(node.left);
if(node.right) que.push(node.right);
}
}
递归深度优先遍历
根据遍历时，所执行的输出顺序不同实现。
先序递归遍历：
var preOrder = function (node) {
if (node) {
console.log(node.value);
preOrder(node.left);
preOrder(node.right);
}
}
中序递归遍历
var inOrder = function (node) {
if (node) {
inOrder(node.left);
console.log(node.value);
inOrder(node.right);
}
}
后序递归遍历
var postOrder = function (node) {
if (node) {
postOrder(node.left);
postOrder(node.right);
console.log(node.value);
}
}
非递归深度优先遍历
非递归先序遍历：
这种方法与广度优先遍历很相似，只是将 队列 的方式改为了 栈 的形式，一个是先入先出，一个是后入先出原则。
var preOrderUnRecur = function(node) {
if(!node) {
throw new Error('Empty Tree');
}
var stack = [];
stack.push(node);
while(stack.length !== 0) {
node = stack.pop();
console.log(node.value);
if(node.right) stack.push(node.right);
if(node.left) stack.push(node.left);
}
}
非递归中序遍历：
var inOrderUnRecur = function(node) {
if(!node) {
throw new Error('Empty Tree');
}
var stack = [];
while(stack.length !== 0 || node) {
if(node) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
console.log(node.value);
node = node.right;
}
}
}
非递归后序遍历：
var posOrderUnRecur = function(node) {
if(!node) {
throw new Error('Empty Tree');
}
var stack = [];
stack.push(node);
var tmp = null;
while(stack.length !== 0) {
tmp = stack[stack.length - 1];
if(tmp.left && node !== tmp.left && node !== tmp.right) {
stack.push(tmp.left);
} else if(tmp.right && node !== tmp.right) {
stack.push(tmp.right);
} else {
console.log(stack.pop().value);
node = tmp;
}
}
}
另外一种方法:
var posOrderUnRecur = function(node) {
if(node) {
var s1 = [];
var s2 = [];
s1.push(node);
while(s1.length !== 0) {
node = s1.pop();
s2.push(node);
if(node.left) {
s1.push(node.left);
}
if(node.right) {
s1.push(node.right);
}
}
while(s2.length !== 0) {
console.log(s2.pop().value);
}
}
}
Morris遍历
这个方法即不用递归也不用栈实现三种深度遍历，空间复杂度为O(1)。
Morris先序:
var morrisPre = function(head) {
if(!head) {
return;
}
var cur1 = head;
var cur2 = null;
while(cur1) {
cur2 = cur1.left;
if(cur2) {
while(cur2.right && cur2.right != cur1) {
cur2 = cur2.right;
}
if(!cur2.right) {
cur2.right = cur1;
console.log(cur1.value);
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
}
} else {
console.log(cur1.value);
}
cur1 = cur1.right;
}
}
Morris中序:
var morrisIn = function(head) {
if(!head) {
return;
}
var cur1 = head;
var cur2 = null;
while(cur1) {
cur2 = cur1.left;
if(cur2) {
while(cur2.right && cur2.right !== cur1) {
cur2 = cur2.right;
}
if(!cur2.right) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
}
}
console.log(cur1.value);
cur1 = cur1.right;
}
}
Morris后序:
var morrisPost = function(head) {
if(!head) {
return;
}
var cur1 = head;
var cur2 = null;
while(cur1) {
cur2 = cur1.left;
if(cur2) {
while(cur2.right && cur2.right !== cur1) {
cur2 = cur2.right;
}
if(!cur2.right) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
printEdge(cur1.left);
}
}
cur1 = cur1.right;
}
printEdge(head);
}
var printEdge = function(head) {
var tail = reverseEdge(head);
var cur = tail;
while(cur) {
console.log(cur.value);
cur = cur.right;
}
reverseEdge(tail);
}
var reverseEdge = function(head) {
var pre = null;
var next = null;
while(head) {
next = head.right;
head.right = pre;
pre = head;
head = next;
}
return pre;
}