二叉搜索树的创建
定义Node为节点类，Tree为二叉树，设置方法insert用于增加树上的结点，根据节点和树上已有结点的权值大小确定插入位置。
/* 结点 */
function Node(val, left, right) {
this.val = val;
this.left = null;
this.right = null;
}
/* 树 */
function Tree() {
this.root = null;
}
/* 结点插入二叉树 */
Tree.prototype.insert = function (val) {
/* 创建新节点 */
let newNode = new Node(val, null, null);
/* 树根为空直接赋值 */
if (!this.root) {
this.root = newNode;
} else {
let cur = this.root;
/* 找到位置才能退出循环 */
while (true) {
if (newNode.val > cur.val) {
/* 右子树为空，直接将新节点作为右孩子 */
if (!cur.right) {
cur.right = newNode;
break;
} else {
cur = cur.right;
}
}
if (newNode.val < cur.val) {
if (!cur.left) {
cur.left = newNode;
break;
} else {
cur = cur.left;
}
}
}
}
}
let tree = new Tree();
let arr = [4, 6, 5, 2, 3, 1];
arr.forEach(v => tree.insert(v));
递归方式实现三种遍历
递归调用，选择对应时机输出即可，缺点是太耗性能.
var orderTraversal = function (root) {
let res = [];
function order(rt) {
if (rt) {
res.push(rt.val);//前序
order(rt.left);
// res.push(rt.val);//中序
order(rt.right);
// res.push(rt.val);//后序
}
}
order(root);
return res;
}
前序遍历
实现： 弹出栈顶元素node，将栈顶元素的右结点right，左结点left放到栈里面，然后取出栈顶元素left作为父结点重复该操作，只有left下的所有结点全部输出完，right才会进行输出，从而实现根->左->右的输出顺序。
leetcode：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
每次循环stack变化:
[4]--------->4出栈,6和2进栈
[6,2]------->2出栈,3和1进栈
[6,3,1]----->1出栈
[6,3]------->3出栈
[6]--------->6出栈,5进栈
[5]--------->5出栈
/* 根->左->右 */
var preorderTraversal = function (root) {
if (!root) return [];
let res = [], stack = [root];
/* 设置栈存序列 */
while (stack.length) {
let node = stack.pop();/* 栈顶元素 */
res.push(node.val);
/* 后进先出，左边的在后面进入，确保每次先弹出左边结点 */
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return res;
};
console.log(preorderTraversal(tree.root));//[ 4, 2, 1, 3, 6, 5 ]
中序遍历
实现： 用栈来存储结点，只有结点左子树全部输出完该结点才可能输出，查到没有左孩子的结点node进行输出，然后再到node的右子树进行同样的操作.
leetcode：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
/* 左->根->右 */
var inorderTraversal = function (root) {
if (!root) return [];
let res = [], stack = [], parent = root;
while (stack.length || parent) {
/* 一直往左下找，直到最左下方结点 */
while (parent) {
stack.push(parent);
parent = parent.left;
}
let node = stack.pop();//弹出最左下方结点
res.push(node.val);
parent=node.right;//完成(左->根),对该结点右下方的结点进行遍历
}
return res;
};
console.log(inorderTraversal(tree.root));//[ 1, 2, 3, 4, 5, 6 ]
后序遍历
实现： 在中序遍历的基础上添加一个判断，只有右子树全部输出才能输出当前结点。
leetcode：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
/* 左->右->根 */
var postorderTraversal = function (root) {
if (!root) return [];
let set = new Set();//记录结点是否被访问过
let stack = [], res = [], parent = root;
while (stack.length || parent) {
while (parent) {
stack.push(parent);
parent = parent.left;
}
let node = stack[stack.length - 1];/* 栈顶元素 */
/* 对还未输出的右子树进行遍历输出 */
if (node.right && !set.has(node.right)) {
set.add(node.right);//标记node.right下的子树已经输出
parent = node.right;
} else {
res.push(node.val);
stack.pop();
}
}
return res;
}
console.log(postorderTraversal(tree.root));//[ 1, 3, 2, 5, 6, 4 ]