二叉树的中序遍历

二叉树是一种常用的数据结构，在计算机科学中被广泛应用。为了有效地处理二叉树，需要了解其遍历方式。本文将重点讨论二叉树的中序遍历。

一、什么是二叉树

二叉树是由节点和连接节点的指针所组成的一种层次结构。每个节点最多连接两个子节点，这些子节点被称为左孩子和右孩子。二叉树的节点可以存储数据，如整数、浮点数、字符串等。二叉树可以用来表示算法中的结构，例如表达式树、搜索树和堆。

二、什么是中序遍历

中序遍历是一种对二叉树进行遍历的方式，它呈现出从左到右、从下到上的顺序。具体来说，中序遍历的顺序是首先遍历左子树，然后访问当前节点，最后遍历右子树。这种顺序可以用递归的方式来实现，也可以使用堆栈来实现。

三、如何实现中序遍历

1. 递归实现

递归是实现中序遍历的最简单方式，通过简单的递归实现，可以遍历整个二叉树。递归遍历算法如下：

```

void inorderTraversal(TreeNode* root) {

if (root == NULL) {

return;

}

inorderTraversal(root->left);

//访问当前节点

inorderTraversal(root->right);

}

```

2. 迭代实现

递归实现中序遍历的效率并不高，在处理大型二叉树时容易发生栈溢出。为了避免这种情况，可以使用迭代实现中序遍历。使用迭代实现，需要用到堆栈。具体来说，代码如下：

```

vector inorderTraversal(TreeNode* root) {

vector res;

stack stk;

TreeNode *p = root;

while (p || !stk.empty()) {

while (p) {

stk.push(p);

p = p->left;

}

p = stk.top();

stk.pop();

res.push_back(p->val);

p = p->right;

}

return res;

}

```

四、中序遍历的应用场景

中序遍历能够遍历整个二叉树，并按照指定的顺序访问节点，这使得它在许多算法中得到了广泛应用。例如，使用中序遍历可以将二叉树转换为有序数组，也可以在二叉树中查找目标节点等。