tree

README

树

在计算机科学中，树（tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。 它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

它具有以下的特点：

1. 每个节点有零个或多个子节点（child）；
2. 没有父节点的节点称为根节点（root）；
3. 每一个非根节点有且只有一个父节点（parent）；
4. 除了根节点外，每个子节点可以分为多个不相交的子树；

一些基本概念

1. 节点（node）的度：

   一个节点含有的子树的个数称为该节点的度；

2. 树的度：

   一棵树中，最大的节点的度称为树的度；

3. 叶节点或终端节点（leaf）：

   度为零的节点；

4. 非终端节点或分支节点：

   度不为零的节点；

5. 父亲节点或父节点：

   若一个节点含有子节点，则这个节点称为其子节点的父节点；

6. 孩子节点或子节点：

   一个节点含有的子树的根节点称为该节点的子节点；

7. 兄弟节点（sibling）：

   具有相同父节点的节点互称为兄弟节点；

8. 节点的层次：

   从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

9. 树的高度或深度（depth）：

   树中节点的最大层次；

10. 堂兄弟节点：

    父节点在同一层的节点互为堂兄弟；

11. 节点的祖先：

    从根到该节点所经分支上的所有节点；

12. 子孙：

    以某节点为根的子树中任一节点都称为该节点的子孙。

13. 森林：

    由m（m>=0）棵互不相交的树的集合称为森林；

遍历与搜索

从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点）、遍历左边子节点、遍历右边子节点。这三个步骤的先后顺序也是不同遍历方式的根本区别。

深度优先遍历（Depth-First-Search, DFS）

如果把左节点和右节点的位置固定不动，那么:

1. 根节点放在左节点的左边，称为前序遍历（Pre-Order Traversal）;
2. 根节点放在左节点和右节点的中间，称为中序遍历（In-Order Traversal）;
3. 根节点放在右节点的右边，称为后序遍历（Post-Order Traversal）。

广度优先遍历（Breadth-First-Search, BFS）

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。

实现

1. 首先将根节点放入队列中。
2. 从队列中取出第一个节点，并检验它是否为目标。 如果找到目标，则结束搜寻并回传结果。 否则将它所有尚未检验过的直接子节点加入队列中。
3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
4. 重复步骤2。

树的种类

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
  • 二叉树：每个节点最多含有两个子树的树称为二叉树；
  • 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
    • 满二叉树：所有叶节点都在最底层的完全二叉树；
  • 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
  • 排序二叉树(二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树)；
• 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
• B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

Documentation

Index

• func BFS(root *TreeNode)
• func InOrderRecursion(root *TreeNode) []int
• func InOrderStack(root *TreeNode) []int
• func PostOrderRecursion(root *TreeNode) []int
• func PostOrderStack(root *TreeNode) []int
• func PreOrderRecursion(root *TreeNode) []int
• func PreOrderStack(root *TreeNode) []int
• type AVL
  • func NewAVL() *AVL
  • func (avl *AVL) Delete(el int) bool
  • func (avl *AVL) Insert(el int) bool
  • func (avl *AVL) Search(el int) bool
• type BST
  • func NewBST() *BST
  • func (b *BST) Delete(el int) bool
  • func (b *BST) Insert(el int) bool
  • func (b *BST) Search(el int) bool
• type TreeNode
  • func (t *TreeNode) String() string

Functions

func BFS

func BFS(root *TreeNode)

广度优先遍历

func InOrderRecursion

func InOrderRecursion(root *TreeNode) []int

InOrderRecursion : 中序遍历的递归实现。

func InOrderStack

func InOrderStack(root *TreeNode) []int

InOrderStack : 中序遍历的非递归实现。

func PostOrderRecursion

func PostOrderRecursion(root *TreeNode) []int

PostOrderRecursion : 后序遍历的递归实现。

func PostOrderStack

func PostOrderStack(root *TreeNode) []int

PostOrderStack : 后序遍历的非递归实现。

func PreOrderRecursion

func PreOrderRecursion(root *TreeNode) []int

PreOrderRecursion : 前序遍历的递归实现。

func PreOrderStack

func PreOrderStack(root *TreeNode) []int

PreOrderStack : 前序遍历的非递归实现。

Types

type AVL

type AVL struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

AVL(Adelson-Velskii & Landis)树是带有平衡条件的二叉查找树(BST)，其每个节点的左子树和右子树的高度最多差1。 查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log(n))。

func NewAVL

func NewAVL() *AVL

AVL Construtor

func (*AVL) Delete

func (avl *AVL) Delete(el int) bool

func (*AVL) Insert

func (avl *AVL) Insert(el int) bool

func (*AVL) Search

func (avl *AVL) Search(el int) bool

type BST

type BST struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

二叉查找树（Binary Search Tree）是指一棵空树或者具有下列性质的二叉树：

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

func NewBST

func NewBST() *BST

BST Construtor

func (*BST) Delete

func (b *BST) Delete(el int) bool

在二叉查找树删除结点

func (*BST) Insert

func (b *BST) Insert(el int) bool

在二叉搜索树插入节点

func (*BST) Search

func (b *BST) Search(el int) bool

在二叉搜索树查找一个节点

type TreeNode

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func (*TreeNode) String

func (t *TreeNode) String() string