1 树的定义
树(Tree) 是 n(n>=0) 个结点的有限集, n=0 时称为空树, 在任意一颗非空树当中,
(1) 有且只有一个特定的称为根(Root) 的结点
(2) 当n>1时, 其余结点可分为 m(m>0) 个互不相交的优先集 T1 T2 ...... Tm, 其余每一个集合本身又是一棵树, 并且称为根的子树 (SubTree)
image.png
特别强调两点 :
1 n>0时, 根节点是位移的, 不可能存在多个根节点
2 当m>0时, 子树的个数并没有限制, 但他们一定是互不相交的, 像下图的两个结构就不符合树的定义, 因为他们都有相交的子树
image.png
树的结点包含一个暑假元素以及若干个指向其子树的分支. 结点所拥有的子树的个数, 称为结点的度(Degree)
度为0的结点称为叶节点 或者终端结点, 度不为0的结点称为非终端结点或者分支结点, 除根节点以外, 分支结点也称为内部结点, 数的度是树内部各结点的度的最大值。
2 树的其他相关概念
结点的层级（level), 根为第一层, 根的孩子为第二层, 同一个父节点的结点互为堂兄弟结点。
image.png
森林（Forest） 是 m(m>=0) 棵互不相交的数的集合, 对数中每个节点而言, 其子树的集合即为森林,
对于下图1 来说, 两个子树就可以理解为森林
图1
image.png
图2
image.png
二叉树
1 每个节点最多有两棵子树, 没有子树或者只有一颗子树也是可以的
2 左子树和右子树是有顺序的, 次序不能任意颠倒
3 即使树中某结点只有一颗数, 也要区分是右树还是左树
特殊二叉树
1 斜树
所有的结点都只有左子树的二叉树, 叫左斜树, 所有结点都只有右子树的, 叫右斜树
2 满二叉树
在一颗二叉树中, 如果所有分支结点都存在左子树和右子树, 并且所有叶子都在同一层上, 这样的二叉树称为满二叉树
image.png
3 完全二叉树
对于一棵具有n个结点的二叉树, 如果编号为 i (1<= i <= n)的结点与同样深度的二叉树中编号为i的结点在二叉树中完全相同, 则这棵二叉树称为完全二叉树
image.png
二叉树的遍历
二叉树的遍历 : 从根节点出发, 按照某种次序, 一次访问二叉树的所有结点, 使得每个节点被访问一次 且 只被访问一次
二叉树的遍历方法 :
1 前序遍历 : 若二叉树为空,则空操作返回, 否则先访问跟结点, 然后前序遍历左子树, 再前序遍历右子树
如下图, 遍历顺序为 ABDGHCEIF
image.png
2 中序遍历: 若树为空, 则空操作返回, 否则从根节点开始, 中序遍历结点的左子树, 然后访问根节点, 最后中序遍历右子树 遍历顺序为 GDHBAEICF
image.png
3 后序遍历:
规则是, 若树为空, 则空操作返回, 否则从左到右先叶子后结点的方式遍历访问左右子树, 最后访问跟结点 , 如下图, 遍历顺序是 GHDBIEFCA
image.png
4 层序遍历:
规则: 若树为空, 则空操作返回, 否则从数的第一层, 也就是根节点开始, 在同一层中, 按照从左到右的顺序逐个访问, 如下图, 遍历顺序是 ABCDEFGHI
image.png
go 语言代码
代码参考地址:
https://gitee.com/babyb/data_srtuct/tree/master/010tree
数据结构
type Object interface{}
type node struct{
data Object
lchild *node
rchild *node
}
初始化二叉树
var a = &node{
data : "A",
}
var b = &node{
data : "B",
}
var c = &node{
data : "C",
}
a.lchild = b;
a.rchild = c;
var d = &node{
data : "D",
}
b.lchild= d
var e = &node{
data : "E",
}
c.lchild = e
var f = &node{
data : "F",
}
c.rchild = f
var g = &node{
data : "G",
}
d.lchild = g
var h = &node{
data : "H",
}
d.rchild = h
var i = &node{
data : "I",
}
e.lchild = i
前序遍历
//PreOrder 前序遍历
func PreOrder(BiTree *node) {
if BiTree.data == nil{
fmt.Println("二叉树为空, 无法遍历");
return ;
}
// 先展示当前结点的元素
fmt.Print(BiTree.data)
///再遍历左子树
if BiTree.lchild != nil {
PreOrder(BiTree.lchild)
}
//最后遍历右子树
if BiTree.rchild != nil{
PreOrder(BiTree.rchild)
}
}
//PreOrder 中序遍历
func midOrder(BiTree *node) {
//先遍历左子树
if BiTree.lchild != nil {
midOrder(BiTree.lchild)
}
if BiTree.data != nil {
fmt.Print(BiTree.data)
}
//再遍历右子树
if BiTree.rchild != nil {
midOrder(BiTree.rchild)
}
}
func afterOrder(BiTree *node){
//后序遍历左子树
if BiTree.lchild != nil {
afterOrder(BiTree.lchild)
}
//后序遍历右子树
if BiTree.rchild != nil {
afterOrder(BiTree.rchild)
}
//最后是自己
if BiTree.data != nil {
fmt.Print(BiTree.data)
}
}
层序遍历
//层序遍历
func layerOrder(BiTree *node){
// 借助队列实现: 1 把根节点入队, a
//2 弹出根节点 a , 并把 a结点的子结点 bc 入队
//3弹出结点b , 把他的子节点加入队列,
// 如此操作, 直到队列为空
q := queue.InitQueue();
if BiTree.data != nil {
//BiTree 前面加上* , 对 指针取值
q.Push(*BiTree)
}
for !q.Empty(){
n,_ := q.Pop();
//强制转换一下类型
node := n.(node);
fmt.Print(node.data);
if node.lchild != nil {
q.Push(*node.lchild)
}
if node.rchild != nil {
q.Push(*node.rchild)
}
}
}
网友评论