什么是二叉树不做介绍，在排序前下面先定义了树节点和二叉树两个类，然后创建了一个二叉树实例用于后续遍历使用。
//树节点
class TreeNode {
constructor(val) {
this.value = val;
this.left = null;
this.right = null;
}
}
//简单构建了一个二叉树类
class Tree {
constructor(root) {
this.root = root;
}
addTreeNode(node) {
if (!this.root) this.root = node;
else this.compare(node, this.root);
}
compare(node, parent) {
if (node.value < parent.value) {
if (parent.left) this.compare(node, parent.left);
else parent.left = node;
} else if (node.value > parent.value) {
if (parent.right) this.compare(node, parent.right);
else parent.right = node;
} else {
console.log("error: add same value");
}
}
}
const tree = new Tree();
[5, 8, 1, 3, 2, 9, 7, 4, 6].forEach((v) => {
tree.addTreeNode(new TreeNode(v));
});
这时候二叉树的结构如下：
5 //第一层
/ \
1 8 //第二层
\ / \
3 7 9 //第三层
/ \ /
2 4 6 //第四层
前序遍历 （递归 非递归实现）
遍历顺序：访问根–>遍历左子树–>遍历右子树
预期结果： 5-1-3-2-4-8-7-6-9
//递归写法
function preorder(node) {
if (node) {
console.log(node.value);
preorder(node.left);
preorder(node.right);
}
}
preorder(tree.root);
//非递归写法
function preoder_non_recursive(node) {
var stack = [node];
while (stack.length) {
var cur = stack.pop();
console.log(cur.value);
if (cur.right) stack.push(cur.right);
if (cur.left) stack.push(cur.left);
}
}
preoder_non_recursive(tree.root);
中序遍历 （递归 非递归实现）
遍历顺序：遍历左子树–>访问根–>遍历右子树
预期结果： 1-2-3-4-5-6-7-8-9
//递归写法
function inorder(node) {
if (node) {
inorder(node.left);
console.log(node.value);
inorder(node.right);
}
}
inorder(tree.root);
//非递归写法
function inoder_non_recursive(node) {
var stack = [];
while (stack.length || node) {
if (node) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
console.log(node.value);
node = node.right;
}
}
}
inoder_non_recursive(tree.root);
中序非递归的执行顺序如下：
stack:[5] result:[]
stack:[5,1] result:[]
stack:[5] result:[1]
stack:[5,3] result:[1]
stack:[5,3,2] result:[1]
stack:[5,3] result:[1,2]
stack:[5] result:[1,2,3]
stack:[5,4] result:[1,2,3]
stack:[5] result:[1,2,3,4]
stack:[] result:[1,2,3,4,5]
stack:[8] result:[1,2,3,4,5]
stack:[8,7] result:[1,2,3,4,5]
stack:[8,7,6] result:[1,2,3,4,5]
stack:[8,7] result:[1,2,3,4,5,6]
stack:[8] result:[1,2,3,4,5,6,7]
stack:[] result:[1,2,3,4,5,6,7,8]
stack:[9] result:[1,2,3,4,5,6,7,8]
stack:[] result:[1,2,3,4,5,6,7,8,9]
后序遍历 （递归 非递归实现）
遍历顺序：遍历左子树–>遍历右子树–>访问根
预期结果： 2-4-3-1-6-7-9-8-5
//递归写法
function postorder(node) {
if (node) {
postorder(node.left);
postorder(node.right);
console.log(node.value);
}
}
postorder(tree.root);
//非递归写法
function postoder_non_recursive(node) {
var stack = [node];
while (stack.length) {
if (node.left && !node.visit) {
node.visit = "left";
stack.push(node.left);
node = node.left;
} else if (node.right && node.visit !== "right") {
node.visit = "right";
stack.push(node.right);
node = node.right;
} else {
node = stack.pop();
console.log(node.value);
delete node.visit;
node = stack[stack.length - 1];
}
}
}
postoder_non_recursive(tree.root);
后序非递归的执行顺序如下：
stack:[5] result:[]
stack:[5,1] result:[]
stack:[5,1,3] result:[]
stack:[5,1,3,2] result:[]
stack:[5,1,3] result:[2]
stack:[5,1,3,4] result:[2]
stack:[5,1,3] result:[2,4]
stack:[5,1] result:[2,4,3]
stack:[5] result:[2,4,3,1]
stack:[5,8] result:[2,4,3,1]
stack:[5,8,7] result:[2,4,3,1]
stack:[5,8,7,6] result:[2,4,3,1]
stack:[5,8,7] result:[2,4,3,1,6]
stack:[5,8] result:[2,4,3,1,6,7]
stack:[5,8,9] result:[2,4,3,1,6,7]
stack:[5,8] result:[2,4,3,1,6,7,9]
stack:[5] result:[2,4,3,1,6,7,9,8]
stack:[] result:[2,4,3,1,6,7,9,8,5]
层序遍历
遍历顺序：按照层一层层遍历
预期结果： 5-1-8-3-7-9-2-4-6
function levelOrder(node) {
var list = [node];
while (list.length) {
var cur = list.shift();
console.log(cur.value);
if (cur.left) list.push(cur.left);
if (cur.right) list.push(cur.right);
}
}
levelOrder(tree.root);
网友评论