二叉树迭代遍历golang

二叉树是一种常见的数据结构，在计算机科学中得到广泛应用。对二叉树进行遍历操作是基本的操作之一，可以帮助我们了解树的结构以及获取其中存储的数据。在本文中，我将分享如何使用迭代方法对二叉树进行遍历，并提供一些在Golang编程语言中实现此功能的示例代码。

前序遍历

前序遍历是二叉树遍历中最简单的一种方式，它的基本思想是：从根节点开始，依次访问节点的左子树和右子树，直到访问完所有节点为止。

在Golang中，可以使用栈来实现前序遍历。具体步骤如下：

1. 创建一个保存节点指针的栈。
2. 将根节点入栈。
3. 重复以下步骤直到栈为空：
   1. 弹出栈顶节点并访问。
   2. 如果该节点的右子树不为空，则将右子树入栈。
   3. 如果该节点的左子树不为空，则将左子树入栈。

func PreorderTraversal(root *TreeNode) []int {
  var result []int
  if root == nil {
    return result
  }
  
  stack := []*TreeNode{root}
  for len(stack) > 0 {
    curr := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    
    result = append(result, curr.Val)
    
    if curr.Right != nil {
      stack = append(stack, curr.Right)
    }
    if curr.Left != nil {
      stack = append(stack, curr.Left)
    }
  }
  
  return result
}

中序遍历

中序遍历是一种较为复杂的二叉树遍历方式，它的基本思想是：先递归访问节点的左子树，再访问节点本身，最后递归访问节点的右子树。

在Golang中，可以使用栈来实现中序遍历。具体步骤如下：

1. 创建一个保存节点指针的栈。
2. 初始化当前节点为根节点。
3. 重复以下步骤直到栈为空且当前节点为空：
   1. 将当前节点及其所有左子节点入栈，并更新当前节点为其左子节点。
   2. 弹出栈顶节点并访问。
   3. 将当前节点更新为弹出节点的右子节点。

func InorderTraversal(root *TreeNode) []int {
  var result []int
  if root == nil {
    return result
  }
  
  stack := []*TreeNode{}
  curr := root
  for len(stack) > 0 || curr != nil {
    for curr != nil {
      stack = append(stack, curr)
      curr = curr.Left
    }
    
    curr = stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    
    result = append(result, curr.Val)
    
    curr = curr.Right
  }
  
  return result
}

后序遍历

后序遍历是二叉树遍历中相对较为复杂的一种方式，它的基本思想是：先递归访问节点的左子树和右子树，再访问节点本身。

在Golang中，可以使用栈来实现后序遍历。具体步骤如下：

1. 创建一个保存节点指针的栈。
2. 初始化当前节点为根节点。
3. 创建一个辅助栈来记录访问过的节点。
4. 重复以下步骤直到栈为空且当前节点为空：
   1. 将当前节点及其所有左子节点入栈，并更新当前节点为其左子节点。
   2. 如果当前节点为空或当前节点被访问过，则弹出栈顶节点并访问，同时更新当前节点为nil。
   3. 否则，将当前节点标记为已访问并将当前节点更新为其右子节点。

func PostorderTraversal(root *TreeNode) []int {
  var result []int
  if root == nil {
    return result
  }
  
  stack := []*TreeNode{}
  curr := root
  visited := map[*TreeNode]bool{}
  for len(stack) > 0 || curr != nil {
    for curr != nil {
      stack = append(stack, curr)
      curr = curr.Left
    }
    
    curr = stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    
    if visited[curr] {
      result = append(result, curr.Val)
      curr = nil
    } else {
      visited[curr] = true
      stack = append(stack, curr)
      curr = curr.Right
    }
  }
  
  return result
}

通过以上示例，我们可以看到如何使用迭代方法对二叉树进行前序、中序和后序遍历。这些方法在实际的编程开发中非常有用，因为它们可以帮助我们处理二叉树相关的问题，并更好地理解和应用该数据结构。