树基础

定义

数的定义

可以使用递归的方法定义：一棵树是一些节点的集合。一棵树由根节点和0~多个非空树（即子树）组成。这些子树中的每一颗根节点都被来自母树跟的一条有向边链接。母树的根节点被称为父节点，子树的根节点被称为子节点。

其他定义

• 树叶：没有子节点的节点
• n到m的路径的长：n到m路径上边的数量
• n的深度：从根节点到n节点的唯一路径长度
• n的高：从n节点到树叶的最长路径长度

树的实现

可以由链表实现：

• 对于确定子节点数量不多或固定的情况下（如二叉树），每个节点具有所有子节点的指针
• 对于一般数，每个节点具有一个子节点和一个兄弟节点的指针

树的遍历

树的遍历可以用递归实现，对于每一个节点，分为为两步：

• 处理当前节点内容（如打印等）
• 递归调用处理子节点

该顺序成为先序遍历，以上两个步骤顺序可以调换，为后序遍历（先处理子节点，再处理本节点）

func read_tree(path, indent string) {
    files, _ := ioutil.ReadDir(path)
    fmt.Println(indent, path)
    for _, i := range files {
        if i.IsDir() {
            read_tree(path+"/"+i.Name(), "\t"+indent)
        } else {
            fmt.Println("\t" + indent + path + "/" + i.Name())
        }
    }
}

该函数即实现了文件树的遍历并打印路径，方式是先序遍历

二叉树

二叉树表示每个节点最多拥有两个子节点的树

二叉表达树

二叉表达数是一种表达算式的方式，其中每个叶子节点为操作数，其他节点均为操作符。操作符节点的左右子树代表的就是该操作符的两个操作数

二叉表达树节点

数据结构体

type node_data struct {
    num int
    exp string
}

结构体

type tree_node struct {
    data       node_data
    left_node  *tree_node
    right_node *tree_node
}

打印方法

func (t *tree_node) print_data() {
    if t.data.exp == "n" {
        fmt.Println(t.data.num)
    } else {
        fmt.Println(t.data.exp)
    }
}

前序遍历方法

依次访问：本节点->左侧节点->右侧节点。因为先访问本节点，故被称为前序遍历

func (t *tree_node) preorder_traversal() {
    t.print_data()
    if t.left_node != nil {
        t.left_node.preorder_traversal()
    }
    if t.right_node != nil {
        t.right_node.preorder_traversal()
    }
}

中序遍历方法

访问顺序为：左侧节点->本节点->右侧节点

func (t *tree_node) inorder_traversal() {
    if t.left_node != nil {
        t.left_node.inorder_traversal()
    }
    t.print_data()
    if t.right_node != nil {
        t.right_node.inorder_traversal()
    }
}

后续遍历方法

访问顺序为：左侧节点->右侧节点->本节点

func (t *tree_node) postorder_traversal() {
    if t.left_node != nil {
        t.left_node.postorder_traversal()
    }
    if t.right_node != nil {
        t.right_node.postorder_traversal()
    }
    t.print_data()
}

构造方法

func new_tree_node(data node_data) *tree_node {
    temp := &tree_node{}
    temp.data = data
    temp.left_node = nil
    temp.right_node = nil
    return temp
}

二叉表达树构造

结构体

type expression_tree_structrue struct {
    tree []*tree_node
}

表达树构造

• 若输入运算符，将切片中的后两个节点弹出，分别挂载在该运算符节点的左右叶子位置，再将该运算符节点从后方加入切片
• 若数据操作数，直接从后方插入切片

func (e *expression_tree_structrue) din(data node_data) {
    indata := new_tree_node(data)
    if data.exp != "n" {
        indata.left_node = e.tree[len(e.tree)-2]
        indata.right_node = e.tree[len(e.tree)-1]
        e.tree = append(e.tree[:len(e.tree)-2], indata)
    } else {
        e.tree = append(e.tree, indata)
    }
}

遍历方法

func (e *expression_tree_structrue) preorder_traversal() {
    e.tree[0].preorder_traversal()
    fmt.Println("\n")
}

func (e *expression_tree_structrue) inorder_traversal() {
    e.tree[0].inorder_traversal()
    fmt.Println("\n")
}

func (e *expression_tree_structrue) postorder_traversal() {
    e.tree[0].postorder_traversal()
    fmt.Println("\n")
}