可以使用递归的方法定义:一棵树是一些节点的集合。一棵树由根节点和0~多个非空树(即子树)组成。这些子树中的每一颗根节点都被来自母树跟的一条有向边链接。母树的根节点被称为父节点,子树的根节点被称为子节点。
可以由链表实现:
树的遍历可以用递归实现,对于每一个节点,分为为两步:
该顺序成为先序遍历,以上两个步骤顺序可以调换,为后序遍历(先处理子节点,再处理本节点)
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")
}