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

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

//中序
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);
    }
}

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容