数据结构-二叉树的三种遍历

在上一篇中我们实现了向二叉树中插入元素，下面我们说一下遍历二叉树的三种方式：前序、中序、和后序。三种步骤技术相同，但是顺序不同：访问节点、往左、往右。由此，我们可有以下三种访问顺序：中序（先往左，访问节点，再往右）、前序（访问节点，往左，再往右）、后序（先往左，再往右，最后访问节点）。
函数的实现如下，所有函数的参数都是树根和打印函数指针，它们是递归的。

//中序
void inOrder(TreeNode * root,DISPLAY display){
    if (root != NULL) {
        inOrder(root->left, display);
        display(root->data);
        inOrder(root->right, display);
    }
}

//后序
void postOrder(TreeNode* root, DISPLAY display) {
    if (root!=NULL){
        postOrder(root->left,display);
        postOrder(root->right, display);
        display(root->data);
    }
}

//前序
void preOrder(TreeNode * root, DISPLAY display) {
    if (root != NULL) {
        display(root->data);
        preOrder(root->left,display);
        preOrder(root->right,display);
    }
}

执行调用我们看到，中序遍历会返回树成员的排序列表，而前序和后序遍历常用来跟栈和队列配合使用可以计算算术表达式。