package main

import (
   "container/list"
   "fmt"
)

// Binary Tree
type BinaryTree struct {
   Data  interface{}
   Left  *BinaryTree
   Right *BinaryTree
}

// Constructor
func NewBinaryTree(data interface{}) *BinaryTree {
   return &BinaryTree{Data: data}
}

// 先序遍历-非递归
func (bt *BinaryTree) PreOrderNoRecursion() []interface{} {
   t := bt
   stack := list.New()
   res := make([]interface{}, 0)
   for t != nil || stack.Len() != 0 {
      for t != nil {
         res = append(res, t.Data)//visit
         stack.PushBack(t)
         t = t.Left
      }
      if stack.Len() != 0 {
         v := stack.Back()
         t = v.Value.(*BinaryTree)
         t = t.Right
         stack.Remove(v)
      }
   }
   return res
}

// 中序遍历-非递归
func (bt *BinaryTree) InOrderNoRecursion() []interface{} {
   t := bt
   stack := list.New()
   res := make([]interface{}, 0)
   for t != nil || stack.Len() != 0 {
      for t != nil {
         stack.PushBack(t)
         t = t.Left
      }
      if stack.Len() != 0 {
         v := stack.Back()
         t = v.Value.(*BinaryTree)
         res = append(res, t.Data)//visit
         t = t.Right
         stack.Remove(v)
      }
   }
   return res
}

// 后序遍历-非递归
func (bt *BinaryTree) PostOrderNoRecursion() []interface{} {
   t := bt
   stack := list.New()
   res := make([]interface{}, 0)
   var preVisited *BinaryTree

   for t != nil || stack.Len() != 0 {
      for t != nil {
         stack.PushBack(t)
         t = t.Left
      }

      v   := stack.Back()
      top := v.Value.(*BinaryTree)

      if (top.Left == nil && top.Right == nil) || (top.Right == nil && preVisited == top.Left) || preVisited == top.Right{
         res = append(res, top.Data)//visit
         preVisited = top
         stack.Remove(v)
      }else {
         t = top.Right
      }
   }
   return res
}



func main() {
   t := NewBinaryTree(1)
   t.Left  = NewBinaryTree(3)
   t.Right = NewBinaryTree(6)
   t.Left.Left = NewBinaryTree(4)
   t.Left.Right = NewBinaryTree(5)
   t.Left.Left.Left = NewBinaryTree(7)

   fmt.Println(t.PreOrderNoRecursion())
   fmt.Println(t.InOrderNoRecursion())
   fmt.Println(t.PostOrderNoRecursion())
}

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

成都创新互联-专业网站定制、快速模板网站建设、高性价比虎丘网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式虎丘网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖虎丘地区。费用合理售后完善，十余年实体公司更值得信赖。
文章题目：golang二叉树前序，中序，后序非递归遍历算法-创新互联
标题链接：http://myzitong.com/article/coeohj.html