数据结构-中序遍历二叉树（基于C++）

深藏阁楼爱情的钟 2024-03-22 12:06 9阅读 0赞

二叉树是一种常见的数据结构，它由节点和边组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的遍历是指按照一定的顺序访问二叉树中的所有节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。本文将详细介绍二叉树中序遍历。

**目录**

一、中序遍历的定义

二、中序遍历的实现

1. 递归实现

2. 非递归实现

三、中序遍历的应用

四、总结

五、完整代码

--------------------

## 一、中序遍历的定义 ##

中序遍历是指按照左子树、根节点、右子树的顺序遍历二叉树中的所有节点。具体来说，中序遍历的过程是先遍历左子树，然后访问根节点，最后遍历右子树。

## 二、中序遍历的实现 ##

中序遍历可以使用递归或者非递归的方式实现。

### 1. 递归实现 ###

递归实现中序遍历的过程比较简单，只需要按照左子树、根节点、右子树的顺序递归遍历即可。具体实现如下：

void inorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    }

### 2. 非递归实现 ###

非递归实现中序遍历需要借助栈来实现。具体实现过程如下：

（1）首先将根节点入栈。

（2）如果栈不为空，则取出栈顶元素，如果该节点有左子节点，则将左子节点入栈。

（3）如果该节点没有左子节点，则访问该节点，并将其右子节点入栈。

（4）重复步骤（2）和（3）直到栈为空。

具体实现如下：

void inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode* p = root;
        while (p != nullptr || !s.empty()) {
            while (p != nullptr) {
                s.push(p);
                p = p->left;
            }
            if (!s.empty()) {
                p = s.top();
                s.pop();
                cout << p->val << " ";
                p = p->right;
            }
        }
    }

## 三、中序遍历的应用 ##

中序遍历在二叉搜索树中有着重要的应用。二叉搜索树是一种特殊的二叉树，它的左子树中的所有节点的值都小于根节点的值，右子树中的所有节点的值都大于根节点的值。因此，对于一个二叉搜索树，中序遍历的结果就是一个有序序列。

中序遍历还可以用于表达式求值。对于一个表达式二叉树，中序遍历的结果就是该表达式的中缀表达式。可以通过中序遍历将中缀表达式转换为后缀表达式，然后再通过后缀表达式求值。

## 四、总结 ##

中序遍历是二叉树遍历中的一种，它按照左子树、根节点、右子树的顺序遍历二叉树中的所有节点。中序遍历可以使用递归或者非递归的方式实现。中序遍历在二叉搜索树中有着重要的应用，可以用于表达式求值等方面。

## 五、完整代码 ##

#include <iostream>
    
    using namespace std;
    
    // 定义二叉树节点结构体
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    // 中序遍历函数
    void inorderTraversal(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    }
    
    int main() {
        // 构造二叉树
        TreeNode* root = new TreeNode(1);
        root->left = new TreeNode(2);
        root->right = new TreeNode(3);
        root->left->left = new TreeNode(4);
        root->left->right = new TreeNode(5);
    
        // 中序遍历
        inorderTraversal(root);
    
        return 0;
    }