树基础

定义

数的定义

可以使用递归的方法定义：一棵树是一些节点的集合。一棵树由根节点和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")
}