2021-10-7 ！二叉树的前序、中序、后序遍历 （递归版本）

非常重要，等下次复习补一张系统栈的图

//前序遍历，递归版本，三个遍历的递归写法思想都一致，唯一区别就是在什么时候访问根结点
//画个图和栈更好理解，这里不多解释
void BinarySearchTreesZH::preorderTraversal(Node *node)
{
    if (node == nullptr)
    {
        return;
    }
    cout << node->element << " ";
    preorderTraversal(node->left);
    preorderTraversal(node->right);
}
//! 简单理解递归遍历二叉树，把遍历整个二叉树这个大问题，转化为遍历根节点的无数个子树
//! 因为遍历一个只有三个结点的二叉树的解决方式是一样的，比如中序遍历，先访问左子节点，根节点就在中间访问，然后访问右子结点
//! 而递归只不过是把访问子结点这个过程变成了先访问一颗以这个子结点为根结点的三个结点的子树的过程，然后把过程结果返回，当作该子结点的访问结果
//! 深入理解就是栈的思想，画图

//中序遍历，递归版本
void BinarySearchTreesZH::inorderTraversal(Node *node)
{
    if (node == nullptr)
    {
        return;
    }
    inorderTraversal(node->left);
    cout << node->element << " ";//! 就是根节点在中间访问，先访问左子树，然后根节点，然后右子树，对于子树的访问也是一样在中间访问根节点
    inorderTraversal(node->right);
}

//后序遍历，递归版本
void BinarySearchTreesZH::postorderTraversal(Node *node)
{
    if (node == nullptr)
    {
        return;
    }
    postorderTraversal(node->left);
    postorderTraversal(node->right);
    cout << node->element << " ";
}