二叉树

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树；

二叉树的前序遍历，中序遍历，后序遍历

树的常用术语：

• 根节点root
• 父节点
• 子节点
• 叶子节点：没有子节点的节点；

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 {
        InfixOrder(node.Left)
        InfixOrder(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: "吴用",
    }

    right1 := &Hero{
        No:   3,
        Name: "卢俊义",
    }

    right2 := &Hero{
        No:   4,
        Name: "林冲",
    }

    node10 := &Hero{
        No:   10,
        Name: "tom",
    }

    node12 := &Hero{
        No:   12,
        Name: "jerry",
    }

    root.Left = left1
    root.Right = right1

    right1.Right = right2
    left1.Left = node10
    left1.Right = node12

    // PreOrder(root)
    // InfixOrder(root)

    PostOrder(root)
}