遍历二叉树口诀

二叉树是一种非常常见的数据结构，它是由结点和边组成的树形结构。在二叉树中，每个结点最多只有两个子结点，分别称为左子结点和右子结点。通过遍历二叉树，我们可以按照一定规律访问二叉树中所有的结点，找到我们需要的信息。本文将从多个角度分析如何遍历二叉树。

一、遍历方式

在二叉树中，遍历方式分为三种：先序遍历、中序遍历和后序遍历。不同的遍历方式会按照不同的规律访问二叉树中的结点，因此可以达到不同的效果。

1. 先序遍历

从根结点开始，先访问根结点，然后按照先序遍历的方式访问左子树和右子树。

2. 中序遍历

从根结点开始，按照中序遍历的方式访问左子树，然后访问根结点，最后按照中序遍历的方式访问右子树。

3. 后序遍历

从根结点开始，按照后序遍历的方式访问左子树，然后按照后序遍历的方式访问右子树，最后访问根结点。

二、遍历算法

在对二叉树进行遍历的时候，我们需要使用遍历算法。下面介绍一下三种遍历算法的递归写法。

1. 先序遍历算法

```

void preorderTraversal(TreeNode* root) {

if (root != nullptr) {

cout << root->val << endl;

preorderTraversal(root->left);

preorderTraversal(root->right);

}

}

```

2. 中序遍历算法

```

void inorderTraversal(TreeNode* root) {

if (root != nullptr) {

inorderTraversal(root->left);

cout << root->val << endl;

inorderTraversal(root->right);

}

}

```

3. 后序遍历算法

```

void postorderTraversal(TreeNode* root) {

if (root != nullptr) {

postorderTraversal(root->left);

postorderTraversal(root->right);

cout << root->val << endl;

}

}

```

三、应用场景

遍历二叉树是一项非常基础的技能，在实际应用中有很多场景。下面介绍一些可能用到遍历二叉树的应用场景。

1. 二叉树题目解答

在做一些算法题目中，可能会出现关于二叉树的问题，需要通过遍历二叉树找到需要的信息。因此，遍历二叉树是解决二叉树题目的重要技巧。

2. 二叉搜索树的搜索

二叉搜索树是一种特殊的二叉树，它的左子树中的所有结点都小于根结点，右子树中的所有结点都大于根结点。因此，在搜索二叉搜索树的时候，可以按照中序遍历的方式来进行，可以快速找到需要的信息。

3. AVL树的调整

AVL树是一种平衡二叉树，它的左右子树高度差不超过1。当插入或者删除结点的时候，可能会导致AVL树的失衡，需要通过遍历二叉树，进行相应的旋转调整。