二叉树遍历

发布时间:2019-03-07 00:35:17
算法 

测试用例

			  1
		2			3
	  4	   5	 6	   7
		  8 9		

前序遍历:1, 2 4 [5 8 9], 3 6 7
中序遍历:4 2 [8 5 9], 1, 6 3 7
后序遍历:4 [8 9 5] 2, 6 7 3, 1

递归遍历

type TreeNode struct {
	data  int
	left  *TreeNode
	right *TreeNode
}

func (t *TreeNode) PreOrderTreeWalk() []int {
	r := make([]int, 0)
	if t == nil {
		return r
	}
	r = append(r, t.data)
	if t.left != nil {
		r = append(r, t.left.PreOrderTreeWalk()...)
	}
	if t.right != nil {
		r = append(r, t.right.PreOrderTreeWalk()...)
	}
	return r
}

func (t *TreeNode) InOrderTreeWalk() []int {
	r := make([]int, 0)
	if t == nil {
		return r
	}
	if t.left != nil {
		r = append(r, t.left.InOrderTreeWalk()...)
	}
	r = append(r, t.data)
	if t.right != nil {
		r = append(r, t.right.InOrderTreeWalk()...)
	}
	return r
}

func (t *TreeNode) PostOrderTreeWalk() []int {
	r := make([]int, 0)
	if t == nil {
		return r
	}
	if t.left != nil {
		r = append(r, t.left.PostOrderTreeWalk()...)
	}
	if t.right != nil {
		r = append(r, t.right.PostOrderTreeWalk()...)
	}
	r = append(r, t.data)
	return r
}

非递归遍历

func (t *TreeNode) NotRecursivePreOrderTreeWalk() []int {
	r := make([]int, 0)
	if t == nil {
		return r
	}
	s := NewStack()
	s.Push(t)
	for !s.Empty() {
		c := s.Pop().(*TreeNode)
		r = append(r, c.data)
		//right child is pushed first so that left is processed first
		if c.right != nil {
			s.Push(c.right)
		}
		if c.left != nil {
			s.Push(c.left)
		}
	}
	return r
}

func (t *TreeNode) NotRecursiveInOderTreeWalk() []int {
	r := make([]int, 0)
	if t == nil {
		return r
	}
	s := NewStack()
	p := t
	for !s.Empty() || p != nil {
		if p != nil {
			s.Push(p)
			p = p.left
		} else {
			c := s.Pop().(*TreeNode)
			r = append(r, c.data)
			p = c.right
		}
	}
	return r
}

func (t *TreeNode) NotRecursivePostOrderTreeWalk() []int {
	r := make([]int, 0)
	if t == nil {
		return r
	}
	s := NewStack()
	var lastNodeVisited *TreeNode = nil
	p := t
	for !s.Empty() || p != nil {
		if p != nil {
			s.Push(p)
			p = p.left
		} else {
			topNode := s.Top().(*TreeNode)
			// if right child exists and traversing node
			// from left child, then move right
			if topNode.right != nil && topNode.right != lastNodeVisited {
				p = topNode.right
			} else {
				r = append(r, topNode.data)
				lastNodeVisited = s.Pop().(*TreeNode)
			}
		}
	}
	return r
}

层次遍历

func (t *TreeNode) LevelWalk() []int {
	r := make([]int, 0)
	if t == nil {
		return r
	}
	q := NewQueue()
	q.EnQueue(t)
	for !q.Empty() {
		c := q.DeQueue().(*TreeNode)
		r = append(r, c.data)
		if c.left != nil {
			q.EnQueue(c.left)
		}
		if c.right != nil {
			q.EnQueue(c.right)
		}
	}
	return r
}

辅助数据结构

type Stack struct {
	data []interface{}
}

func NewStack() *Stack {
	return &Stack{
		data: make([]interface{}, 0),
	}
}

func (s *Stack) Push(v interface{}) {
	s.data = append(s.data, v)
}

func (s *Stack) Pop() interface{} {
	if len(s.data) == 0 {
		panic("stack is empty")
	}
	v := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return v
}

func (s *Stack) Top() interface{} {
	if len(s.data) == 0 {
		panic("stack is empty")
	}
	return s.data[len(s.data)-1]
}

func (s *Stack) Empty() bool {
	return len(s.data) == 0
}

func (s *Stack) String() string {
	return fmt.Sprintf("%+v", s.data)
}

队列

type Queue struct {
	data []interface{}
}

func NewQueue() *Queue {
	return &Queue{
		data: make([]interface{}, 0),
	}
}

func (q *Queue) EnQueue(v interface{}) {
	q.data = append(q.data, v)
}

func (q *Queue) DeQueue() interface{} {
	if len(q.data) == 0 {
		panic("queue is empty")
	}
	r := q.data[0]
	q.data = q.data[1:len(q.data)]
	return r
}

func (q *Queue) Empty() bool {
	return len(q.data) == 0
}

测试用例

func createExampleTree() *TreeNode {
	root := &TreeNode{
		data: 1,
		left: &TreeNode{
			data: 2,
			left: &TreeNode{
				data:  4,
				left:  nil,
				right: nil,
			},
			right: &TreeNode{
				data: 5,
				left: &TreeNode{
					data:  8,
					left:  nil,
					right: nil,
				},
				right: &TreeNode{
					data:  9,
					left:  nil,
					right: nil,
				},
			},
		},
		right: &TreeNode{
			data: 3,
			left: &TreeNode{
				data:  6,
				left:  nil,
				right: nil,
			},
			right: &TreeNode{
				data:  7,
				left:  nil,
				right: nil,
			},
		},
	}
	return root
}

func main() {
	t := createExampleTree()
	fmt.Println(t.PreOrderTreeWalk())
	fmt.Println(t.InOrderTreeWalk())
	fmt.Println(t.PostOrderTreeWalk())
	fmt.Println(t.NotRecursivePreOrderTreeWalk())
	fmt.Println(t.NotRecursiveInOderTreeWalk())
	fmt.Println(t.NotRecursivePostOrderTreeWalk())
	fmt.Println(t.LevelWalk())
}

参考

原文地址:http://zhyoulun.com/post/binary-tree-walk
转载请注明出处