什么是二叉树

二叉树（Binary tree）：是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树图

先序遍历

先序：是二叉树遍历中的一种，即先访问根结点，然后遍历左子树，后遍历右子树。遍历左、右子树时，先访问根结点，后遍历左子树，后遍历右子树，如果二叉树为空则返回。

package main
import "fmt"
type node struct {
	value     string
	leftNode  *node
	rightNode *node
}
func main() {
	n := node{}
	node := n.newTree()
	n.Show(node)
}
// 前序遍历  根左右
func (n *node) Show(node *node) {
	if node != nil {
		fmt.Print(node.value)
		n.Show(node.leftNode)
		n.Show(node.rightNode)
	}
}
// 构造二叉树   返回根节点
func (n *node) newTree() *node {
	nodeA := &node{
		value: "A",
	}
	nodeB := &node{
		value: "B",
	}
	nodeC := &node{
		value: "C",
	}
	nodeD := &node{
		value: "D",
	}
	nodeE := &node{
		value: "E",
	}
	nodeF := &node{
		value: "F",
	}
	nodeG := &node{
		value: "G",
	}
	nodeH := &node{
		value: "H",
	}
	nodeI := &node{
		value: "I",
	}
	nodeJ := &node{
		value: "J",
	}
	nodeK := &node{
		value: "K",
	}
	nodeA.leftNode = nodeB
	nodeA.rightNode = nodeC
	nodeB.leftNode = nodeD
	nodeB.rightNode = nodeE
	nodeC.leftNode = nodeF
	nodeC.rightNode = nodeG
	nodeD.rightNode = nodeH
	nodeE.rightNode = nodeI
	nodeF.leftNode = nodeJ
	nodeF.rightNode = nodeK
	fmt.Print("先序：")
	return nodeA
}

中序遍历

中序：是二叉树遍历中的一种，即先遍历左子树，后访问根结点，然后遍历右子树。若二叉树为空则结束返回。

package main
import "fmt"
type node struct {
	value     string
	leftNode  *node
	rightNode *node
}

func main() {
	n := node{}
	node := n.newTree()
	n.Show(node)
}

// 中序遍历  左根右
func (n *node) Show(node *node) {
	if node != nil {
		n.Show(node.leftNode)
		fmt.Print(node.value)
		n.Show(node.rightNode)
	}
}

// 构造二叉树   返回根节点
func (n *node) newTree() *node {
	nodeA := &node{
		value: "A",
	}
	nodeB := &node{
		value: "B",
	}
	nodeC := &node{
		value: "C",
	}
	nodeD := &node{
		value: "D",
	}
	nodeE := &node{
		value: "E",
	}
	nodeF := &node{
		value: "F",
	}
	nodeG := &node{
		value: "G",
	}
	nodeH := &node{
		value: "H",
	}
	nodeI := &node{
		value: "I",
	}
	nodeJ := &node{
		value: "J",
	}
	nodeK := &node{
		value: "K",
	}
	nodeA.leftNode = nodeB
	nodeA.rightNode = nodeC
	nodeB.leftNode = nodeD
	nodeB.rightNode = nodeE
	nodeC.leftNode = nodeF
	nodeC.rightNode = nodeG
	nodeD.rightNode = nodeH
	nodeE.rightNode = nodeI
	nodeF.leftNode = nodeJ
	nodeF.rightNode = nodeK
	fmt.Print("中序：")
	return nodeA
}

后序遍历

后序：是二叉树遍历中的一种，即先遍历左子树，后遍历右子树，然后访问根结点，遍历左、右子树时，仍先遍历左子树，后遍历右子树，最后遍历根结点。

package main
import "fmt"
type node struct {
	value     string
	leftNode  *node
	rightNode *node
}
func main() {
	n := node{}
	node := n.newTree()
	n.Show(node)
}
// 后序遍历  左右根
func (n *node) Show(node *node) {
	if node != nil {
		n.Show(node.leftNode)
		n.Show(node.rightNode)
		fmt.Print(node.value)
	}
}
// 构造二叉树   返回根节点
func (n *node) newTree() *node {
	nodeA := &node{
		value: "A",
	}
	nodeB := &node{
		value: "B",
	}
	nodeC := &node{
		value: "C",
	}
	nodeD := &node{
		value: "D",
	}
	nodeE := &node{
		value: "E",
	}
	nodeF := &node{
		value: "F",
	}
	nodeG := &node{
		value: "G",
	}
	nodeH := &node{
		value: "H",
	}
	nodeI := &node{
		value: "I",
	}
	nodeJ := &node{
		value: "J",
	}
	nodeK := &node{
		value: "K",
	}
	nodeA.leftNode = nodeB
	nodeA.rightNode = nodeC
	nodeB.leftNode = nodeD
	nodeB.rightNode = nodeE
	nodeC.leftNode = nodeF
	nodeC.rightNode = nodeG
	nodeD.rightNode = nodeH
	nodeE.rightNode = nodeI
	nodeF.leftNode = nodeJ
	nodeF.rightNode = nodeK
	fmt.Print("后序：")
	return nodeA
}