2020-08-31二叉树遍历

迭代方式遍历二叉树

1.前序遍历（根左右）

/**
 * 前序遍历
 * @tparam T
 * @param root
 * @param visit
 */
template<class T>
void startOrder(TreeNode<T> *root, void (visit)(T)) {
    //循环到底的情况
    if (root == NULL) {
        return;
    }
    //输出根节点
    visit(root->data);
    //遍历左节点
    startOrder(root->left, visit);
    //遍历右节点
    startOrder(root->right, visit);
}

2.中序遍历（左根右）

/**
 * 中序遍历
 * @tparam T
 * @param root
 * @param visit
 */
template<class T>
void centerOrder(TreeNode<T> *root, void (visit)(T)) {
    if (root == NULL) {
        return;
    }
    //先遍历左节点
    centerOrder(root->left, visit);
    visit(root->data);
    centerOrder(root->right, visit);
}

3.后序遍历（左右根）

/**
 * 后序遍历
 * @tparam T
 * @param root
 * @param visit
 */
template<class T>
void endOrder(TreeNode<T> *root, void (visit)(T)) {
    if (root == NULL) {
        return;
    }
    endOrder(root->left, visit);
    endOrder(root->right, visit);
    visit(root->data);
}

4.层序遍历

/**
 * 层序遍历
 * @tparam T
 * @param root
 * @param visit
 */
template<class T>
void levelOrder(TreeNode<T> *root, void (visit)(T)) {
    if (root == NULL) {
        return;
    }
    //借助队列实现层序遍历
    queue<TreeNode<T> *> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode<T> *node = q.front();
        q.pop();

        visit(node->data);

        TreeNode<T> *left = NULL;
        if ((left = node->left)) {
            q.push(left);
        }
        TreeNode<T> *right = NULL;
        if ((right = node->right)) {
            q.push(right);
        }
    }
}