树型结构(Tree)是一种重要的非线性数据结构,它为计算机应用中出现的具有层次关系的数据提供了一种有效的表示方法,比如文件目录结构、源程序语法结构等。
树是 n(n>=0) 个节点的有限集合 T。在任意一棵非空树中满足如下两个条件:
由上图可知,树的定义是递归的,树是一种递归数据结构。树的这种定义为树的递归处理带来了很大方便,本节举例中几乎所有对树的处理都采用了递归算法。
在了解树型结构时,还有几个基本概念非常重要,必须要掌握:
二叉树是一种特殊的树,具有如下特点:
除了这些基本特征外,还有如下一些特殊的二叉树。
所有的节点只有左子树则称为左斜树;所有节点只有右子树则称为右斜树。如下图所示:
在一棵二叉树中,所有的分支结点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样的二叉树称为满二叉树。就是完美圆满的意思。
满二叉树的特点如下所示:
在一棵二叉树中,除最后一层外,若其余各层都是满的,最后一层要么是满的,要么在右边缺少若干个连续的节点,这样的二叉树被称为完全二叉树。满二叉树必须是完全二叉树,而完全二叉树不一定是满二叉树。
完全二叉树的特点如下所示:
二叉树的存储方法有顺序存储、链接存储和线索树存储等几种存储方法,顺序存储是使用数组来完成,而链接存储和线索树存储都使用了链表来完成。本节在二叉树的应用举例中使用了链接存储法。
在二叉树的链接存储结构中,通常采用的方法是:每个节点设置三个域,即值域、左指针域和右指针域,其结构如下图所示。
其中 Data 表示值域,用于存储放入节点中的数据元素,LeftChild 和 RightChild 分别表示左指针域和右指针域,用以分别存储左子树和右子树节点的指针地址。
链接存储的指针类型和节点定义如下:
这里的 Data 字段可以是任意基本数据类型,如 int、float、string 等。链表所有节点的 Data 字段类型一致,比如同为 int 型或同为 string 型。在本节的应用举例中,二叉树节点的 Data 字段将被设置成空接口 interface{},这样二叉树的叶子节点将能够存储不同类型的数据,比如一个节点为 int 型,其他节点可以为 string 型等。
二叉树的应用处理功能主要包括:
针对这些功能本例共定义了三个接口:Initer、Operater 和 Order。
当为二叉树创建了一个新节点时,Initer 接口提供了 SetData() 方法可以对节点的 Data 字段进行初始化。
Initer 接口定义如下:
当已经生成了一个二叉树时,可以使用 Operater 接口提供的三个方法:PrintBT()、Depth() 和 LeafCount(),对二叉树进行输出、深度计算和叶子统计等基本操作。
Operater 接口定义如下:
对二叉树的遍历是一个重要的功能,这些功能在接口 Order 中实现,Order 接口中共定义了三个方法,分别是 PreOrder()、InOrder() 和 PostOrder(),分别可以实现前序遍历、中序遍历和后序遍历。
Order 接口的定义如下:
可以看到,在定义接口时,接口中的方法只需声明原型,而并不需在此实现。这些方法的实现可以在其他 Go 包文件中实现,或者直接由其他用户提供。
接口的意义也在于此,即同一个接口可以有不同的实现方式,甚至由不同的人去完成。
通过接口的概念知道接口是方法的组合,而在定义接口时不必马上实现方法,方法可由设计者自己或交由其他人单独设计。本例三个接口中共有 7 个方法,下面分别介绍一下它们是怎么实现的。
SetData() 通过空接口 interface{},可以将任意类型数据赋值给二叉树节点的 Data 字段,实现二叉树对任意数据类型的存储。
SetData 方法的定义如下:
PrintBT() 调用底层函数 PrintBT(),输出一个给定二叉树的嵌套括号表示。
PrintBT 方法的定义如下:
Depth() 调用底层函数 Depth(),返回二叉树的深度。
Depth 方法的定义如下:
LeafCount() 调用底层函数 LeafCount(),返回二叉树的叶子节点数。
LeafCount 方法的定义如下:
PreOrder() 调用底层函数 PreOrder() 对二叉树进行前序遍历。
PreOrder 方法的定义如下:
InOrder() 调用底层函数 InOrder() 对二叉树进行中序遍历。
InOrder 方法的定义如下:
PostOrder() 调用底层函数 PostOrder() 对二叉树进行后序遍历。
PostOrder 方法的定义如下:
在面向对象程序设计中,上层方法的功能实现还要依赖底层函数,本例中大部分方法也是这样,现将所有底层函数一一列举如下。
NewNode() 按照链接存储方式生成一个新的二叉树节点,参数 left 指向左指针域,参数 right 指向右指针域。
NewNode 函数的定义如下:
PrintBT() 用于输出一个给定二叉树的嵌套括号表示,采用递归算法:
PrintBT 函数的定义如下:
func PrintBT(n *Node) {
if n != nil {
fmt.Printf("%v", n.Data)
if n.Left != nil || n.Right != nil {
fmt.Printf("(")
PrintBT(n.Left)
if n.Right != nil {
fmt.Printf(",")
}
PrintBT(n.Right)
fmt.Printf(")")
}
}
}
Depth() 用于计算二叉树的深度,采用递归算法:
Depth 函数的定义如下:
func Depth(n *Node) int {
var depleft, depright int
if n == nil {
return 0
} else {
depleft = Depth(n.Left)
depright = Depth(n.Right)
if depleft > depright {
return depleft + 1
} else {
return depright + 1
}
}
}
LeafCount() 用于统计二叉树叶子节点数,采用递归算法:
LeafCount 函数的定义如下:
func LeafCount(n *Node) int {
if n == nil {
return 0
} else if (n.Left == nil) && (n.Right == nil) {
return 1
} else {
return (LeafCount(n.Left) + LeafCount(n.Right))
}
}
PreOrder() 可以对二叉树进行前序遍历,采用递归算法,按照先访问根节点,再访问左子树,最后访问右子树的次序访问二叉树中的所有节点,且每个节点仅访问一次。
PreOrder 函数的定义如下:
func PreOrder(n *Node) {
if n != nil {
fmt.Printf("%v", n.Data)
PreOrder(n.Left)
PreOrder(n.Right)
}
}
InOrder() 可以对二叉树进行中序遍历,采用递归算法,按照先访问左子树,再访问根节点,最后访问右子树的次序访问二叉树中的所有节点,且每个节点仅访问一次。
InOrder 函数的定义如下:
func InOrder(n *Node) {
if n != nil {
PreOrder(n.Left)
fmt.Printf("%v", n.Data)
PreOrder(n.Right)
}
}
PostOrder() 可以对二叉树进行后序遍历,采用递归算法,按照先访问左子树,再访问右子树,最后访问根节点的次序访问二叉树中的所有节点,且每个节点仅访问一次。
PostOrder 函数的定义如下:
func PostOrder(n *Node) {
PreOrder(n.Left)
PreOrder(n.Right)
fmt.Printf("%v", n.Data)
}
前面介绍了二叉树链接存储结构,以及节点定义、接口定义、方法实现和底层函数设计,并在包 btree 中实现。接下来将利用这些知识实现几个二叉树的基本应用,包括二叉树的创建、基本操作和遍历。
二叉树的创建过程一般如下:
【示例 1】二叉树的建立,本例将演示如何使用 Initer 接口实现根节点的初始化。
// 二叉树的建立
package main
import(
"fmt"
"btree"
)
func main() {
//创建根节点
root := NewNode(nil, nil)
var it Initer
it = root
it.SetData("root node")
//创建左子树
a := NewNode(nil, nil)
a.SetData("left node")
al := NewNode(nil, nil) //左叶子节点
al.SetData(100)
ar := NewNode(nil, nil) //右叶子节点
ar.SetData(3.14)
a.Left = al
a.Right = ar
//创建右子树
b := NewNode(nil, nil)
b.SetData("right node")
root.Left = a
root.Right = b
root.PrintBT()
}
编译并运行该程序,输出结果为:
通过输出结果可以看出,在示例中首先创建了根节点 root node,然后创建左子树 left node 和右子树 right node。左子树有两个叶子节点,左叶子的值为 int 型 "100",右叶子的值为 float 型 "3.14"。即该二叉树可以存储不同类型的值,这些都是由空接口 interface{} 实现的。
对一个已存在的二叉树的基本操作包括二叉树的输出、深度计算、叶子数统计等,在下面将演示如何使用 Operater 接口实现这些基本操作。
【示例 2】二叉树的基本操作。
// 二叉树的基本操作
package main
import(
"fmt"
"btree"
)
func main() {
//创建二叉树
root := NewNode(nil, nil)
root.SetData("root node")
a := NewNode(nil, nil)
a.SetData("left node")
al := NewNode(nil, nil)
al.SetData(100)
ar := NewNode(nil, nil)
ar.SetData(3.14)
a.Left = al
a.Right = ar
b := NewNode(nil, nil)
b.SetData("right node")
root.Left = a
root.Right = b
// 使用 Operater 接口实现对二叉树的基本操作
var it Operater
it = root
it.PrintBT()
fmt.Println()
fmt.Println("The depths of the Btree is:", it.Depth())
fmt.Println("The leaf counts of the Btree is:", it.LeafCount())
}
编译并运行该程序,输出结果为:
通过输出结果可以看出,上面示例中二叉树的深度为 3,叶子节点数也为 3,这和验证结果完全一致。另外,对二叉树的操作还有査找、插入、删除节点等,大家可以在上面的基础上自行完成。
在二叉树的一些基本应用中,常常需要在树中查找具有某种特征的节点,或者对树中全部节点逐一进行某种处理,这就是二叉树的遍历(Traversing binary tree)。即如何按某条搜索路径访问树中的每个节点,使得每个节点均能被访问一次,而且仅被访问一次。
二叉树的遍历方法一般分为前序遍历、中序遍历和后序遍历,下面示例将演示如何使用 Order 接口实现二叉树的三种遍历。
【示例 3】二叉树的遍历。
// 二叉树的遍历
package main
import(
"fmt"
"btree"
)
func main() {
//创建二叉树
root := NewNode(nil, nil)
root.SetData("root node")
a := NewNode(nil, nil)
a.SetData("left node")
al := NewNode(nil, nil)
al.SetData(100)
ar := NewNode(nil, nil)
ar.SetData(3.14)
a.Left = al
a.Right = ar
b := NewNode(nil, nil)
b.SetData("right node")
root.Left = a
root.Right = b
// 使用 Order 接口实现对二叉树的基本操作
var it Order
it = root
it.PreOrder() //先序遍历
fmt.Println()
it.InOrder() //中序遍历
fmt.Println()
it.PostOrder() //后序遍历
}
编译并运行该程序,输出结果为:
通过输出结果可以看出,示例的三种遍历方法输出结果和验证结果完全一致。当然在对二叉树进行遍历的同时,用户也可以对树中的节点做各种处理,比如修改节点信息等。