Go语言实现二叉树

　　1、定义结点 package main  import (     ＂fmt＂ )  // 定义结点 type BinaryTreeNode struct {     Data  int     Left  *BinaryTreeNode     Right *BinaryTreeNode }
　　2、创建结点 // 创建结点 func CreateBinaryTree(data int) *BinaryTreeNode {     return &BinaryTreeNode{data, nil, nil} }
　　3、数据插入 // 插入结点 func (node *BinaryTreeNode) Insert(n *BinaryTreeNode, data int) bool {     cur := n     for cur != nil {         if cur.Data < data {             if cur.Right != nil {                 cur = cur.Right             } else {                 cur.Right = CreateBinaryTree(data)                 return true             }         } else {             if cur.Left != nil {                 cur = cur.Left             } else {                 cur.Left = CreateBinaryTree(data)                 fmt.Println(data, ＂d---＂)                 return true             }         }     }     return false }
　　4、层序遍历 // 层数打印 func (node *BinaryTreeNode) BreadthFirstSearch() []int {     if node == nil {         return nil     }     var result []int     par := node     cur := []*BinaryTreeNode{par}     for len(cur) > 0 {         result = append(result, cur[0].Data)         if cur[0].Left != nil {             cur = append(cur, cur[0].Left)         }         if cur[0].Right != nil {             cur = append(cur, cur[0].Right)         }         cur = cur[1:]     }     return result }
　　5、前序遍历 // 前序打印 func (node *BinaryTreeNode) PreOrder(n *BinaryTreeNode) {     if n != nil {         fmt.Println(n.Data)         node.PreOrder(n.Left)         node.PreOrder(n.Right)     } }
　　6、中序遍历 // 中序打印 func (node *BinaryTreeNode) InOrder(n *BinaryTreeNode) {     if n != nil {         node.InOrder(n.Left)         fmt.Println(n.Data)         node.InOrder(n.Right)     } }
　　7、后序遍历 // 后序打印 func (node *BinaryTreeNode) PostOrder(n *BinaryTreeNode) {     if n != nil {         node.InOrder(n.Left)         node.InOrder(n.Right)         fmt.Println(n.Data)     } }
　　8、获取树的高度 // 获取树的高度 func (node *BinaryTreeNode) GetHight(n *BinaryTreeNode) int {     if n == nil {         return 0     }     l := node.GetHight(n.Left)     r := node.GetHight(n.Right)     if l > r {         return l + 1     } else {         return r + 1     } }
　　9、打印叶子结点 // 打印叶子节点 func (node *BinaryTreeNode) FindLead(n *BinaryTreeNode) {     if n != nil {         if n.Left == nil && n.Right == nil {             fmt.Println(n.Data)         }         node.FindLead(n.Left)         node.FindLead(n.Right)     } }
　　10、查找指定值的节点 // 查找指定值的节点 func (node *BinaryTreeNode) FindValueNode(n *BinaryTreeNode, target int) *BinaryTreeNode {     if n == nil {         return nil     } else if n.Data == target {         return n     } else {         cur := node.FindValueNode(n.Left, target)         if cur != nil {             return cur         }         return node.FindValueNode(n.Right, target)     } }
　　11、主函数 func main() {     var node *BinaryTreeNode // 创建一个根结点     node = CreateBinaryTree(10)     li := []int{9, 11, 8, 5, 6, 4, 12, 15, 18, 17} // 准备数据     // 插入数据     for _, val := range li {         node.Insert(node, val)     }     ret := node.BreadthFirstSearch()     fmt.Println(ret)     node.PreOrder(node)     node.InOrder(node)     node.PostOrder(node)     res := node.GetHight(node)     fmt.Println(res)     node.FindLead(node)     ref := node.FindValueNode(node, 17)     fmt.Println(ref) }
　　12、运行结果 9 d--- 8 d--- 5 d--- 4 d--- 17 d--- [10 9 11 8 12 5 15 4 6 18 17] 10 9 8 5 4 6 11 12 15 18 17 4 5 6 8 9 10 11 12 15 17 18 4 5 6 8 9 11 12 15 17 18 10 6 4 6 17 &{17  }
　　该实例生成的二叉树如下：