SOURCE

// 二叉树遍历
// (a+b*c)-d/e

let tree = {
    value: "-",
    left: {
        value: '+',
        left: {
            value: 'a',
        },
        right: {
            value: '*',
            left: {
                value: 'b',
            },
            right: {
                value: 'c',
            }
        }
    },
    right: {
        value: '/',
        left: {
            value: 'd',
        },
        right: {
            value: 'e',
        }
    }
}

// 先序遍历
let preList = [];
// 非递归遍历
const preOrderUnRecusion = function(node) {
    // 判断二叉树是否为空
    if(node) {
        // 将二叉树压入栈
        let stack = [node];
        // 如果栈不为空，循环遍历
        while(stack.length !== 0) {
            // 从栈中取出一个节点
            node = stack.pop();
            // 将取出节点的值存入到数组中
            preList.push(node.value);
            // 如果存在右子树，将右子树压入栈
            if(node.right) {
                stack.push(node.right);
            }
             // 如果存在左子树，将左子树压入栈
            if(node.left) {
                stack.push(node.left);
            }
        }
    }
}
// preOrderUnRecusion(tree);
// console.log(preList);

// 递归遍历
const preOrderRec = function(node) {
    // 判断二叉树是否为空
    if(node) {
        // 将节点的值存入到数组中
        preList.push(node.value);
        // 递归遍历左子树
        preOrderRec(node.left);
        // 递归遍历右子树
        preOrderRec(node.right);
    }
}
// preOrderRec(tree);
// console.log(preList);


// 中序遍历
// 非递归遍历
const middleOrderUnRec = function(node) {
    // 判断二叉树是否为空
    if(node) {
        // 建立一个栈
        let stack = [];
        // 如果栈不为空或者节点不为空，则循环遍历
        while(stack.length !== 0 || node) {
            // 如果节点不为空
            if(node) {
                // 将节点压入栈
                stack.push(node);
                // 将左子树作为当前节点
                node = node.left;
            }
            // 如果左子树为空
            else {
                // 取出节点
                node = stack.pop();
                // 将取出节点的值放入到数组中
                preList.push(node.value);
                // 把右节点作为现在节点
                node = node.right;
            }
        }
    }
}


// 递归遍历
const middleOrderRec = function(node) {
    if(node) {
        // 递归遍历左子树
        middleOrderRec(node.left);
        // 将节点的值存入到数组中
        preList.push(node.value);
        // 递归遍历右子树
        middleOrderRec(node.right);
    }
}

// middleOrderRec(tree);
// console.log(preList);

// 后序遍历
// 非递归
const postOrderUnRec = function(node) {
    if(node) {
        let stack = [node];
        let temp = null;
        while(stack.length !== 0) {
            // 将栈顶的值保存到变量中
            temp = stack[stack.length -1];
            // 如果存在左子树
            if(temp.left && node !== temp.left && node !== temp.right) {
                // 将左子树压入栈
                stack.push(temp.left);
            }
            // 如果存在右子树
            else if(temp.right && node !== temp.right) {
                // 将右子树压入栈
                stack.push(temp.right);
            }
            else {
                preList.push(stack.pop().value);
                node = temp;
            }
        }
    }
}

// 递归遍历
const postOrderRec = function(node) {
    if(node) {
        // 递归遍历左子树
        postOrderRec(node.left);
        // 递归遍历右子树
        postOrderRec(node.right);
        // 将节点的值放入到数组中
        preList.push(node.value);
    }
}



// 二叉树的广度遍历
const breathTraversal = function(node) {
    if(node) {
        // 把二叉树放入队列中
        let que = [node];
        // 判断队列是否为空
        while(que.length !== 0) {
            // 从队列中取出一个节点
            node = que.shift();
            // 将节点的值保存到数组中
            preList.push(node.value);
            // 如果存在左子树，将左子树放入到队列中
            if(node.left) {
                que.push(node.left);
            }
            // 如果存在右子树，将右子树放入到队列中
            if(node.right) {
                que.push(node.right);
            }
        }
    }
}

breathTraversal(tree);
console.log(preList);