Golang算法:二叉树前序,中序,后序非递归遍历算法

不屈真实 · · 553 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

本文主要介绍了二叉树前序,中序,后序非递归遍历算法

import (
   "container/list"
)
// 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())
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:不屈真实

查看原文:Golang算法:二叉树前序,中序,后序非递归遍历算法

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

553 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传