二叉树遍历的三种方法

二叉树是一种非常重要的数据结构，在计算机科学中广泛应用。遍历是二叉树的基本操作之一，分为三种方法：前序遍历、中序遍历和后序遍历。

一、前序遍历

前序遍历是指先访问节点自身，然后遍历左子树和右子树。对于一棵二叉树来说，前序遍历的顺序是先根节点，再左子树，然后右子树。它的递归实现方式如下：

```

void preOrder(BinaryTree *root) {

if(root) {

cout << root->data << " "; //输出节点数据

preOrder(root->left); //遍历左子树

preOrder(root->right);//遍历右子树

}

}

```

根据前序遍历，可以输出二叉树的前序遍历序列。

二、中序遍历

中序遍历是指先遍历左子树，然后访问节点自身，最后遍历右子树。对于一棵二叉树来说，中序遍历的顺序是先左子树，然后根节点，最后右子树。它的递归实现方式如下：

```

void inOrder(BinaryTree *root) {

if(root) {

inOrder(root->left); //遍历左子树

cout << root->data << " "; //输出节点数据

inOrder(root->right);//遍历右子树

}

}

```

根据中序遍历，可以输出二叉树的中序遍历序列。

三、后序遍历

后序遍历是指先遍历左子树，然后遍历右子树，最后访问节点自身。对于一棵二叉树来说，后序遍历的顺序是先左子树，然后右子树，最后根节点。它的递归实现方式如下：

```

void postOrder(BinaryTree *root) {

if(root) {

postOrder(root->left); //遍历左子树

postOrder(root->right);//遍历右子树

cout << root->data << " "; //输出节点数据

}

}

```

根据后序遍历，可以输出二叉树的后序遍历序列。

四、遍历方式的比较

前序遍历、中序遍历和后序遍历的主要区别在于访问节点的顺序不同。通过比较三种遍历方式的输出结果，可以发现它们输出的序列有所不同。具体来说：

- 前序遍历输出的序列是先根节点，然后左子树，最后右子树；

- 中序遍历输出的序列是先左子树，然后根节点，最后右子树；

- 后序遍历输出的序列是先左子树，然后右子树，最后根节点。

因此，不同的遍历方式适用于不同的场景。比如，如果需要遍历一棵二叉树并按照节点的顺序输出序列，可以选择中序遍历。如果需要先处理根节点，可以选择前序遍历。