二叉树

二叉树是什么？

• 一种特殊的树型结构
• 树中每个节点最多只能有两个子节点（左右）
• 在 JS 中常用 Object 来模拟二叉树

代码示例

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

二叉树的先序遍历(DFS) 算法口诀与代码实现

• 算法口诀
  • ① 访问根节点
  • ② 对根节点的左子树进行先序遍历
  • ③ 对根节点的右子树进行先序遍历
• 图示

• 代码实现

  function getResult(binaryTree) {
    // 1.定义结果变量
    let result = [];
    // 2.定义递归函数
    const perorder = (root) => {
        if(!root) {
            return;
        }
        // 访问根节点
        console.log(root.val);
        result.push(root.val);
        // 对根节点左子树进行先序遍历
        perorder(root.left);
        // 对根节点右子树进行先序遍历
        perorder(root.right);
    }
    // 3.调用递归函数
    perorder(binaryTree);
    // 4.返回结果
    return result;
  }
  getResult(binaryTree);