二叉树

树中最多的子节点树为2, JS 来模拟二叉树数据结构

const bTree = {
    value: 1,
    left: {
        value: 2,
        left: {
            value: 3,
            left: null,
            right: null
        },
        right: {
            value: 4,
            left: {
                value: 5,
                left: null,
                right: null
            },
            right: null
        }
    },
    right: {
        value: 6,
        left: null,
        right: {
            value: 7,
            left: null,
            right: null
        }
    }
}

先序遍历

遍历规则

• 访问根节点
• 访问左子树
• 访问右子树

递归版

// 先序遍历
// 1 2 3 4 5 6 7
const preorder = (root) => {
    if(!root) return
    // 先访问根节点
    console.log(root.value)
    // 访问左子树
    preorder(root.left)
    // 访问右子树
    preorder(root.right)
}
preorder(bTree)

非递归版本

// 非递归版本使用堆栈模拟递归
const prevorder = (root) => {
    if(!root) return
    // console.log(root.value)
    // prevorder(root.left)
    // prevorder(root.right)
    const stack = [root]
    while(stack.length) {
        // 栈顶元素弹出
        const item = stack.pop()
        // 读取根节点
        console.log(item.value)
        if(item.right) stack.push(item.right)
        if(item.left) stack.push(item.left)
    }
}
prevorder(bTree)

中序遍历

遍历规则

• 访问左子树
• 访问根节点
• 访问右子树

递归版本

// 中序遍历
// 3 2 5 4 1 6 7
const middleorder = (root) => {
    if(!root) return
    middleorder(root.left)
    console.log(root.value)
    middleorder(root.right)
}
middleorder(bTree)

// 中序遍历需要借助链表指针
// 需要链表指针遍历左子树
const middleorder = (root) => {
    if(!root) return
    // middleorder(root.left)
    // console.log(root.value)
    // middleorder(root.right)
    let stack = []
    let point = root
    while(stack.length || point) {
        // 将所有左子树放入栈中
        while(point) {
            stack.push(point)
            point = point.left
        }
        // 左子树先出栈
        let item = stack.pop()
        // 读取根节点
        console.log(item.value)
        point = item.right
    }
}
middleorder(bTree)

后序遍历

遍历规则

• 访问左子树
• 访问右子树
• 访问根节点

递归版本

// 后序遍历
// 3 5 4 2 7 6 1
const postorder = (root) => {
    if(!root) return
    postorder(root.left)
    postorder(root.right)
    console.log(root.value)
}
postorder(bTree)

非递归版本

// 后序遍历可以倒置前序遍历
const lastorder = (root) => {
    if(!root) return
    // lastorder(root.left)
    // lastorder(root.right)
    // console.log(root.value)
    let stack = [root]
    let outputStack = []
    while(stack.length) {
        const item = stack.pop()
        if(item) {
            outputStack.push(item.value)
            stack.push(item.left)
            stack.push(item.right)
        }
    }
    while(outputStack.length) {
        console.log(outputStack.pop())
    }
}
lastorder(bTree)