packagemainimport("container/list""fmt")//BinaryTreetypeBinaryTreestruct{Datainterface{}Left*BinaryTreeRight*BinaryTree}//ConstructorfuncNewBinaryTree(datainterface{})*BinaryTree{return&BinaryTree{Data:data}}//先序遍历-非递归func(bt*BinaryTree)PreOrderNoRecursion()[]interface{}{t:=btstack:=list.New()res:=make([]interface{},0)fort!=nil||stack.Len()!=0{fort!=nil{res=append(res,t.Data)//visitstack.PushBack(t)t=t.Left}ifstack.Len()!=0{v:=stack.Back()t=v.Value.(*BinaryTree)t=t.Rightstack.Remove(v)}}returnres}//中序遍历-非递归func(bt*BinaryTree)InOrderNoRecursion()[]interface{}{t:=btstack:=list.New()res:=make([]interface{},0)fort!=nil||stack.Len()!=0{fort!=nil{stack.PushBack(t)t=t.Left}ifstack.Len()!=0{v:=stack.Back()t=v.Value.(*BinaryTree)res=append(res,t.Data)//visitt=t.Rightstack.Remove(v)}}returnres}//后序遍历-非递归func(bt*BinaryTree)PostOrderNoRecursion()[]interface{}{t:=btstack:=list.New()res:=make([]interface{},0)varpreVisited*BinaryTreefort!=nil||stack.Len()!=0{fort!=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)//visitpreVisited=topstack.Remove(v)}else{t=top.Right}}returnres}funcmain(){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())}