树基础
定义
数的定义
可以使用递归的方法定义:一棵树是一些节点的集合。一棵树由根节点和0~多个非空树(即子树)组成。这些子树中的每一颗根节点都被来自母树跟的一条有向边链接。母树的根节点被称为父节点,子树的根节点被称为子节点。
其他定义
- 树叶:没有子节点的节点
- n到m的路径的长:n到m路径上边的数量
- n的深度:从根节点到n节点的唯一路径长度
- n的高:从n节点到树叶的最长路径长度
树的实现
可以由链表实现:
- 对于确定子节点数量不多或固定的情况下(如二叉树),每个节点具有所有子节点的指针
- 对于一般数,每个节点具有一个子节点和一个兄弟节点的指针
树的遍历
树的遍历可以用递归实现,对于每一个节点,分为为两步:
该顺序成为先序遍历,以上两个步骤顺序可以调换,为后序遍历(先处理子节点,再处理本节点)
1 2 3 4 5 6 7 8 9 10 11
| 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()) } } }
|
该函数即实现了文件树的遍历并打印路径,方式是先序遍历
二叉树
二叉树表示每个节点最多拥有两个子节点的树
二叉表达树
二叉表达数是一种表达算式的方式,其中每个叶子节点为操作数,其他节点均为操作符。操作符节点的左右子树代表的就是该操作符的两个操作数
二叉表达树节点
数据结构体
1 2 3 4
| type node_data struct { num int exp string }
|
结构体
1 2 3 4 5
| type tree_node struct { data node_data left_node *tree_node right_node *tree_node }
|
打印方法
1 2 3 4 5 6 7
| func (t *tree_node) print_data() { if t.data.exp == "n" { fmt.Println(t.data.num) } else { fmt.Println(t.data.exp) } }
|
前序遍历方法
依次访问:本节点->左侧节点->右侧节点。因为先访问本节点,故被称为前序遍历
1 2 3 4 5 6 7 8 9
| 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() } }
|
中序遍历方法
访问顺序为:左侧节点->本节点->右侧节点
1 2 3 4 5 6 7 8 9
| 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() } }
|
后续遍历方法
访问顺序为:左侧节点->右侧节点->本节点
1 2 3 4 5 6 7 8 9
| 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() }
|
构造方法
1 2 3 4 5 6 7
| 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 }
|
二叉表达树构造
结构体
1 2 3
| type expression_tree_structrue struct { tree []*tree_node }
|
表达树构造
- 若输入运算符,将切片中的后两个节点弹出,分别挂载在该运算符节点的左右叶子位置,再将该运算符节点从后方加入切片
- 若数据操作数,直接从后方插入切片
1 2 3 4 5 6 7 8 9 10
| 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) } }
|
遍历方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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") }
|