在Javascript上显示二叉搜索树遍历（递归方式）

Question

我正在尝试控制台二叉树中的每个数据。我的主要问题是我想以递归方式实现。到目前为止我基本上有这个代码：

this.levelOrder = function (root) {
    if (root.data != null) {
        console.log(root.data);

        if (root.left != null) {
            this.levelOrder(root.left);
        }

        if (root.right != null) {
            this.levelOrder(root.right)
        }
    } else {
        return;
    }
};

输出是3 2 1 5 4 7

但应该是3 2 5 1 4 7。所以基本上我正在访问节点的第一个子节点，而不是首先打印所有子节点。

Answer 1

假设有一棵这样的树，

      4
  2       6
1   3   5   7

和一个对象字面量

tree = {
    data: 4,
    left: {
        data: 2,
        left: {
            data: 1,
            left: null,
            right: null
        },
        right: {
            data: 3,
            left: null,
            right: null
        }
    },
    right: {
        data: 6,
        left: {
            data: 5,
            left: null,
            right: null
        },
        right: {
            data: 7,
            left: null,
            right: null
        }
    }
};

您可以递归调用该函数，首先获取树的左侧部分，然后获取树的右侧部分。该算法称为深度优先搜索。

该函数使用单次检查，因为这足以首先检查然后继续。

      4
  2       6
1   3   5   7

对于广度优先搜索（一种首先迭代树的每个级别的算法），您可以将此代码与上面相同的树数据一起使用。

tree = {
    data: 4,
    left: {
        data: 2,
        left: {
            data: 1,
            left: null,
            right: null
        },
        right: {
            data: 3,
            left: null,
            right: null
        }
    },
    right: {
        data: 6,
        left: {
            data: 5,
            left: null,
            right: null
        },
        right: {
            data: 7,
            left: null,
            right: null
        }
    }
};