go语言实现--二叉树

--write by zhuwx 2019-10-31 11:38:50 +0800 CST

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有 2^{i-1} 个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1(百度百科)。

二叉树有多种:

(1)完全二叉树——叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫作完全二叉树。
(2)满二叉树——叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点,这种二叉树就叫作满二叉树,他是一种特殊的完全二叉树。
(3)平衡二叉树——平衡二叉树又被称为AVL树(区别于AVL算法),它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

一般二叉树性质:
性质1:二叉树第i层上的结点数目最多为 2^{i-1} (i≥1)。
性质2:深度为k的二叉树至多有2^{k}-1个结点(k≥1)。
性质3:包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1。

完全二叉树性质:

具有n个节点的完全二叉树的高度k为[log2n]+1
对于具有n个节点的完全二叉树,如果按照从上(根节点)到下(叶节点)和从左到右的顺序对二叉树中的所有节点从0开始到n-1进行编号,则对于任意的下标为k的节点,有:
• 如果k=0,则它是根节点,它没有父节点;如果k>0,则它的父节点的下标为[(i-1)/2];
• 如果2k+1 <= n-1,则下标为k的节点的左子结点的下标为2k+1;否则,下标为k的节点没有左子结点.
• 如果2k+2 <= n-1,则下标为k的节点的右子节点的下标为2k+2;否则,下标为k的节点没有右子节点
满二叉树性质:
在满二叉树中,叶节点的个数比分支节点的个数多1

二叉查找树:
也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
任意节点的左、右子树也分别为二叉查找树;
没有键值相等的节点。

二叉树遍历

1、前序遍历(与树的前序遍历一样)
基本思想:先访问当前结点,再前序遍历左子树,最后再前序遍历右子树即根—左—右。
图中前序遍历结果是:1,2,4,5,7,8,3,6
2、中序遍历
基本思想:先中序遍历左子树,然后再访问当前结点,最后再中序遍历右子树即左—根—右。
图中中序遍历结果是:4,2,7,8,5,1,3,6
3、后序遍历
基本思想:先后序遍历左子树,然后再后序遍历右子树,最后再访问当前结点即左—右—根。
图中后序遍历结果是:4,8,7,5,2,6,3,1
4、层次遍历(与树的层次遍历一样)
基本思想:从第一层开始,依此遍历每层,直到结束。
图中层次遍历结果是:1,2,3,4,5,6,7,8

例子:


对上图的二叉树遍历做一个go语言的实现,代码如下:


package main

import (
"fmt"
)

type Node struct {
Value int
Left, Right *Node
}

func (node *Node) Print() {
fmt.Print(node.Value, " ")
}

func (node *Node) SetValue(v int) {
if node == nil {
fmt.Println("setting value to nil.node ignored.")
return
}
node.Value = v
}

//前序遍历
func (node *Node) PreOrder() {
if node == nil {
return
}
node.Print()
node.Left.PreOrder()
node.Right.PreOrder()
}

//中序遍历
func (node *Node) MiddleOrder() {
if node == nil {
return
}
node.Left.MiddleOrder()
node.Print()
node.Right.MiddleOrder()
}

//后序遍历
func (node *Node) PostOrder() {
if node == nil {
return
}
node.Left.PostOrder()
node.Right.PostOrder()
node.Print()
}

//层次遍历(广度优先遍历)
func (node *Node) BreadthFirstSearch() {
if node == nil {
return
}
result := []int{}
nodes := []*Node{node}
for len(nodes) > 0 {
curNode := nodes[0]
nodes = nodes[1:]
result = append(result, curNode.Value)
if curNode.Left != nil {
nodes = append(nodes, curNode.Left)
}
if curNode.Right != nil {
nodes = append(nodes, curNode.Right)
}
}
for _, v := range result {
fmt.Print(v, " ")
}
}

//层数(递归实现)
//对任意一个子树的根节点来说,它的深度=左右子树深度的最大值+1
func (node *Node) Layers() int {
if node == nil {
return 0
}
leftLayers := node.Left.Layers()
rightLayers := node.Right.Layers()
if leftLayers > rightLayers {
return leftLayers + 1
} else {
return rightLayers + 1
}
}

//层数(非递归实现)
//借助队列,在进行按层遍历时,记录遍历的层数即可
func (node *Node) LayersByQueue() int {
if node == nil {
return 0
}
layers := 0
nodes := []*Node{node}
for len(nodes) > 0 {
layers++
size := len(nodes) //每层的节点数
count := 0
for count < size {
count++
curNode := nodes[0]
nodes = nodes[1:]
if curNode.Left != nil {
nodes = append(nodes, curNode.Left)
}
if curNode.Right != nil {
nodes = append(nodes, curNode.Right)
}
}
}
return layers
}

func CreateNode(v int) *Node {
return &Node{Value: v}
}

func main() {
root := Node{Value: 3}
root.Left = &Node{}
root.Left.SetValue(0)
root.Left.Right = CreateNode(2)
root.Right = &Node{5, nil, nil}
root.Right.Left = CreateNode(4)

fmt.Print("\n前序遍历: ")
root.PreOrder()
fmt.Print("\n中序遍历: ")
root.MiddleOrder()
fmt.Print("\n后序遍历: ")
root.PostOrder()
fmt.Print("\n层次遍历: ")
root.BreadthFirstSearch()
fmt.Println("\n层数: ", root.Layers())
fmt.Println("\n层数: ", root.LayersByQueue())}
}
————————————————
版权声明:本文为CSDN博主「米兰的小铁匠1943」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/tuobicui6522/article/details/80502130


运行结果:


前序遍历: 3 0 2 5 4
中序遍历: 0 2 3 4 5
后序遍历: 2 0 4 5 3
层次遍历: 3 0 5 2 4
层数: 3
层数: 3
————————————————
版权声明:本文为CSDN博主「米兰的小铁匠1943」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/tuobicui6522/article/details/80502130