公司新建了网站以前的就网站可以全部删除吗,桂林创新大厦网站,厦门网站建设网页设计,网站文章不收录怎么做本文使用golang实现二叉树的遍历#xff0c;包含以下7种方法。
深度优先遍历 先序遍历 递归法非递归法 中序遍历 递归法非递归法 后序遍历 递归法非递归法 广度优先遍历
二叉树节点定义#xff1a;
type Node struct {Val intLeft *NodeRight *Node
}深度优先遍历
先…本文使用golang实现二叉树的遍历包含以下7种方法。
深度优先遍历 先序遍历 递归法非递归法 中序遍历 递归法非递归法 后序遍历 递归法非递归法 广度优先遍历
二叉树节点定义
type Node struct {Val intLeft *NodeRight *Node
}深度优先遍历
先序遍历
定义 1 访问根节点 2 先序遍历左子树 3 先序遍历右子树。
递归实现
func preorder(root *Node, consume func(*Node)) {if root nil {return}consume(root)preorder(root.Left, consume)preorder(root.Right, consume)
}非递归实现 思路使用一个栈实现 1将根节点压入栈 2栈中弹出一个节点访问该节点 3将该节点的右孩子、左孩子依次压入栈 4重复步骤2~3直至完成步骤3时栈为空。
栈实现
type Stack struct {values []*Node
}func (s *Stack) Push(node *Node) {if s.values nil {s.values make([]*Node, 0)}s.values append(s.values, node)
}func (s *Stack) Pop() *Node {sl : len(s.values)if sl 0 {return nil}node : s.values[sl-1]s.values s.values[:sl-1]return node
}func (s *Stack) IsEmpty() bool {return len(s.values) 0
}func preorder(root *Node, consume func(*Node)) {if root nil {return}stack : Stack{}stack.Push(root)for node : stack.Pop(); node ! nil; node stack.Pop() {consume(node)if node.Right ! nil {stack.Push(node.Right)}if node.Left ! nil {stack.Push(node.Left)}}
}中序遍历
定义 1 中序遍历左子树 2 访问根节点 3 中序遍历右子树。
递归实现
func inorder(root *Node, consume func(*Node)) {if root nil {return}inorder(root.Left, consume)consume(root)inorder(root.Right, consume)
}非递归实现 思路使用一个栈实现 1 将根节点及其所有直系左孩子压入栈直系左孩子其父节点也是左孩子 2 栈弹出一个节点访问该节点 3 若弹出的节点有右孩子则将右孩子视为根节点执行步骤1 4 重复步骤2~3直至栈为空。
func inorder(root *Node, consume func(*Node)) {if root nil {return}stack : Stack{}pushAllLeft(root, stack)for !stack.IsEmpty() {node : stack.Pop()consume(node)if node.Right ! nil {pushAllLeft(node.Right, stack)}}
}func pushAllLeft(root *Node, stack *Stack) {for node : root; node ! nil; node node.Left {stack.Push(node)}
}后序遍历
定义 1 后序遍历左子树 2 后序遍历右子树 3 访问根节点。
递归实现
func postorder(root *Node, consume func(*Node)) {if root nil {return}postorder(root.Left, consume)postorder(root.Right, consume)consume(root)
}非递归实现 思路使用2个栈实现 1 将根节点压入栈1 2 栈1弹出一个节点将其左孩子、右孩子依次压入栈1 3 将步骤2弹出的节点压入栈2 4 重复步骤2~3直至执行完步骤3时栈1为空 5 栈2弹出一个节点并访问该节点 6 重复步骤5直至栈2为空。
func postorder(root *Node, consume func(*Node)) {if root nil {return}stack1 : Stack{}stack2 : Stack{}stack1.Push(root)for !stack1.IsEmpty() {node : stack1.Pop()stack2.Push(node)if node.Left ! nil {stack1.Push(node.Left)}if node.Right ! nil {stack1.Push(node.Right)}}for !stack2.IsEmpty() {consume(stack2.Pop())}
}广度优先遍历
定义按从上往下、从左往右的顺序来遍历 思路使用一个队列实现 1 将根节点加入队尾 2 从队列头取出一个节点访问该节点 3 将该节点的左孩子、右孩子依次加入队尾 4 重复步骤2~3直至执行完步骤3时队列为空。
func widthorder(root *Node, consume func(*Node)) {if root nil {return}queue : make([]*Node, 0)queue append(queue, root)for len(queue) 0 {node : queue[0]queue queue[1:]consume(node)if node.Left ! nil {queue append(queue, node.Left)}if node.Right ! nil {queue append(queue, node.Right)}}
}
