go实现二叉树

阳光穿透心脏的1/2处 2021-07-24 13:13 354阅读 0赞

# 一 代码 #

package main
    
    import (
       "fmt"
    )
    
    type Hero struct {
       No    int
       Name  string
       Left  *Hero
       Right *Hero
    }
    
    // 前序遍历：先输 root 结点，然后再输出左子树，然后再输出右子树
    func PreOrder(node *Hero) {
       if node != nil {
          fmt.Printf("no=%d name=%s\n", node.No, node.Name)
          PreOrder(node.Left)
          PreOrder(node.Right)
       }
    }
    
    // 中序遍历：先输出 root 的左子树，再输 root 结点，最后输出 root 的右子树
    func InfixOrder(node *Hero) {
       if node != nil {
          InfixOrder(node.Left)
          fmt.Printf("no=%d name=%s\n", node.No, node.Name)
          InfixOrder(node.Right)
       }
    }
    
    // 后序遍历：先输出 root 的左子树，最后输出 root 的右子树，再输 root 结点
    func PostOrder(node *Hero) {
       if node != nil {
          PostOrder(node.Left)
          PostOrder(node.Right)
          fmt.Printf("no=%d name=%s\n", node.No, node.Name)
       }
    }
    
    func main() {
       // 构建一个二叉树
       root := &Hero{
          No:   1,
          Name: "宋江",
       }
       left1 := &Hero{
          No:   2,
          Name: "吴用",
       }
       node10 := &Hero{
          No:   10,
          Name: "tom",
       }
       node12 := &Hero{
          No:   12,
          Name: "jack",
       }
       left1.Left = node10
       left1.Right = node12
       right1 := &Hero{
          No:   3,
          Name: "卢俊义",
       }
       root.Left = left1
       root.Right = right1
       right2 := &Hero{
          No:   4,
          Name: "林冲",
       }
       right1.Right = right2
       // PreOrder(root)
       // InfixOrder(root)
       PostOrder(root) // 后序遍历
    }

# 二 测试 #

no=10 name=tom
    no=12 name=jack
    no=2 name=吴用
    no=4 name=林冲
    no=3 name=卢俊义
    no=1 name=宋江