二叉树遍历算法

二叉树是一种经典的数据结构，它由一个根节点和两个子树组成，其中每个节点最多有两个子节点。在二叉树中，节点的访问顺序非常重要，这就引出了二叉树遍历算法。二叉树遍历是指按一定的规则访问树的每个节点，而且每个节点只能访问一次。在本文中，我们将从多个角度对二叉树遍历算法进行分析。

1.前序遍历

前序遍历是指先访问根节点，然后按照从左到右的顺序依次访问左子树和右子树。前序遍历可以用递归或者非递归的方式实现。在递归实现中，代码非常简洁易懂，如下所示：

```

void preorder(Node *root){

if(root){

cout<< root->data<<" ";

preorder(root->left);

preorder(root->right);

}

}

```

在非递归实现中，可以使用栈的数据结构来实现。具体来讲，我们首先将根节点压入栈中，然后将右子树和左子树按照相反的顺序压入栈中。具体代码如下所示：

```

void preorder(Node *root){

if(!root) return;

stack s;

s.push(root);

while(!s.empty()){

Node *node = s.top();

s.pop();

cout< data<<" ";

if(node->right) s.push(node->right);

if(node->left) s.push(node->left);

}

}

```

2.中序遍历

中序遍历是指先访问左子树，然后访问根节点，最后访问右子树。和前序遍历一样，中序遍历也可以用递归或者非递归的方式实现。

在递归实现中，具体实现代码如下所示：

```

void inorder(Node *root){

if(root){

inorder(root->left);

cout< data<<" ";

inorder(root->right);

}

}

```

在非递归实现中，可以先将根节点及其左子节点依次压入栈中，然后在弹出根节点时访问它，最后将右子节点压入栈中。具体实现代码如下所示：

```

void inorder(Node *root){

stack s;

while(root || !s.empty()){

while(root){

s.push(root);

root = root->left;

}

root = s.top();

s.pop();

cout< data<<" ";

root = root->right;

}

}

```

3.后序遍历

后序遍历是指先访问左子树，然后访问右子树，最后访问根节点。和前面两种遍历方式一样，后序遍历也可以用递归或者非递归的方式实现。

在递归实现中，具体代码如下所示：

```

void postorder(Node *root){

if(root){

postorder(root->left);

postorder(root->right);

cout< data<<" ";

}

}

```

在非递归实现中，可以用两个栈来实现。具体实现过程如下：首先将根节点压入第一个栈中，接着弹出栈顶元素，把它压入第二个栈中，然后依次将它的左子节点和右子节点压入第一个栈中，最后将第二个栈中的元素依次弹出并访问即可。具体实现代码如下所示：

```

void postorder(Node *root){

if(!root) return;

stack s;

stack out;

s.push(root);

while(!s.empty()){

Node *node = s.top();

s.pop();

out.push(node);

if(node->left) s.push(node->left);

if(node->right) s.push(node->right);

}

while(!out.empty()){

Node *node = out.top();

out.pop();

cout< data<<" ";

}

}

```