Golang 알고리즘: 이 진 트 리 앞 순서, 중간 순서, 뒤 순서 비 재 귀적 반복 알고리즘
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())
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.