golang二叉树前序,中序,后序非递归遍历算法-创新互联
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二叉树前序,中序,后序非递归遍历算法-创新互联
当前URL:http://pwwzsj.com/article/coeohj.html