04 基本数据结构：树与二叉搜索树

在计算机领域中，树是一种很常见的数据结构之一，这是一种非线性的数据结构。树能够把数据按照等级模式存储起来，例如树干中的数据比较重要，而小分支中的数据的功能一般比较次要。

在学习树结构之前需要先了解一些概念：

• 节点的度：是指一个节点的子树个数。
• 树的度：一棵树中节点度的最大值。
• 叶子（终端节点）：度为0的节点。
• 分支节点（非终端节点）：度不为0的节点。
• 内部节点：除根节点之外的分支节点。
• 孩子：将树中某个节点的子树的根称为这个节点的孩子。
• 双亲：是下面子节点的双亲。
• 兄弟：同一个双亲的孩子。
• 路径：如果在树中存在一个节点序列k1 ，k2 ，…，kj ，使得ki 是ki+1 的双亲（1≤i<j），则称该节点序列是从k1 到kj 的一条路径。
• 祖先：如果树中的节点k到ks 之间存在一条路径，则称k是ks 的祖先。
• 子孙：ks 是k的子孙。
• 层次：节点的层次是从根开始算起的，第1层为根。
• 高度：树中节点的最大层次称为树的高度或深度。
• 有序树：将树中每个节点的各子树看成是从左到右有秩序的。
• 无序树：有序树之外的树称为无序树。
• 森林：是n（n≥0）棵互不相交的树的集合。

可以使用树中节点之间的父子关系来描述树形结构的逻辑特征。

树是一个比较大的概念，一颗树节点其前驱和后继的关系是1：N，直观看是非线性结构，也因为这样，如果单单以树的概念来研究它非常庞杂，为了简化树的研究，我们一般都只关注二叉树，即每一颗子树都有左子树和右子树。（事实上，任何任何树、二叉树、森林都可以互相转换。）以下我们只针对二叉树展开。

二叉树是节点的有限集，不但可以是空集，而且也可以是由一个根节点及两棵不相交的子树组成，通常将这两棵不相交的子树分别称作这个根的左子树和右子树。

（1）在二叉树中，第i层的节点总数不超过2i-1 。 （2）深度为h的二叉树最少有h个节点，最多有2h -1个节点（h≥1）。 （3）对于任意一棵二叉树来说，如果叶节点数为n0 ，且度数为2的节点总数为n2 ，则n0 =n2 +1。 （4）有n个节点的完全二叉树的深度为int（log2 n）+1。 （5）存在一个有n个节点的完全二叉树，如果各节点用顺序方式存储，则节点之间有如下关系：

• 如果i=1，则节点i为根，无父节点；如果i>1，则其父节点编号为trunc(n/2)；
• 如果2×i≤n，则其左儿子（即左子树的根节点）的编号为2×i；如果2×i>n，则无左儿子；
• 如果2×i+1≤n，则其右儿子的节点编号为2×i+1；如果2×i+1>n，则无右儿子。

（6）假设有n个节点，能构成h(n)种不同的二叉树。则h(n)为卡特兰数的第n项，h(n)= C(n, 2×n)/(n+1)。”

（1）空二叉树。 （2）只有一个根节点的二叉树。 （3）右子树为空的二叉树。 （4）左子树为空的二叉树。 （5）完全二叉树。

（1）满二叉树：除了叶节点外，每一个节点都有左右子叶，并且叶节点都处在最底层的二叉树。 （2）完全二叉树：只有最下面的两层节点度小于2，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树。

二叉树的顺序存储结构是指用一维数组存储二叉树中的节点，并且节点的存储位置（下标）应该能体现节点之间的逻辑关系，即父子关系。因为二叉树本身不具有顺序关系，所以二叉树的顺序存储结构需要解决如何利用数组下标来反映节点之间的父子关系。由二叉树的性质（5）可知，使用完全二叉树中节点的层序编号可以反映出节点之间的逻辑关系，并且这种反映是唯一的。对于一般的二叉树来说，可以增添一些并不存在的空节点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。

二叉树顺序存储结构的具体存储步骤如下所示。 （1）将二叉树按完全二叉树编号。根节点的编号为1，如果某节点i有左孩子，则其左孩子的编号为2i；如果某节点i有右孩子，则其右孩子的编号为2i+1。 （2）以编号作为下标，将二叉树中的节点存储到一维数组中。

因为二叉树的顺序存储结构一般仅适合于存储完全二叉树，所以如果使用上述存储方法会有一个缺点——造成存储空间的浪费或形成右斜树。

二叉树的链式存储结构又称二叉链表，是指用一个链表来存储一棵二叉树。在二叉树中，每一个节点用链表中的一个链节点来存储。

因为一棵非空的二叉树由根节点及左、右子树这3个基本部分组成，所以在任何一个给定节点上，可以按某种次序执行如下3个操作。 （1）访问节点本身（N）。 （2）遍历该节点的左子树（L）。 （3）遍历该节点的右子树（R）。 以上3种操作有6种执行次序，分别是NLR、LNR、LRN、NRL、RNL、RLN。因为前3种次序与后3种次序对称，所以只讨论先左后右的前3种次序。

根据访问节点的操作，会发生如下3种位置命名。 （1）NLR：即前序遍历，也称先序遍历，访问节点的操作发生在遍历其左、右子树之前。 （2）LNR：即中序遍历，访问节点的操作发生在遍历其左、右子树之间。 （3）LRN：即后序遍历，访问节点的操作发生在遍历其左、右子树之后。 因为被访问的节点必是某个子树的根，所以N（Node）、L（Left Subtree）和R（Right Subtree）又可以理解为根、根的左子树和根的右子树，所以NLR、LNR和LRN分别被称为先根遍历、中根遍历和后根遍历。

好了，上面叙述那么多关于树与二叉树的知识，那么二叉树这种结构有什么作用呢？我们之前学过线性表，我们知道连续空间结构的数组的特性是查找效率高，而删改因为要移动内存空间的缘故则效率较低；另一种线性数据结构链表的特性是查找效率低，而删改效率高。那么有没有一种数据结构，既可以有较高的增删改效率，并且具备较高的查找效率呢？，二叉树便是解决方案之一，准确的说应该是二叉排序树。

二叉排序树（BST/Binary Search Tree）又叫二叉搜索树、二叉查找树

• 必须是二叉树
• 可以为空
• 非空左子树的所有键值小于其根节点的键值
• 非空右子树的所有键值大于其根节点的键值
• 左右子树本身也是二叉搜索树

insert(key) ： 向树中插入一个新的键 search(key) ： 在树中查找一个键，返回布尔值 inOrderTraverse：通过中序遍历方式遍历所有节点（每课子树按（左->中->右）顺序遍历） ps：先中后指代子树根节点的访问顺序 preOrderTraverse：通过先序遍历方式遍历所有节点（每课子树按（中->左->右）顺序遍历） postOrderTraverse：通过后序遍历方式遍历所有节点（每课子树按（左->右->中）顺序遍历） min: 返回树中最小值或键 max：返回树中最大的值或键 remove(key) ：从树中移除某个键

package tree

import (
	"github.com/gofuncchan/ADBase/datastructure/queue"
	"sync"
)

type node struct {
	left, right *node
	key         uint
	value       interface{}
}

func (n *node) remove() {
	n.key = 0
	n.value = nil
	n.left = nil
	n.right = nil
}

type BinarySearchTree struct {
	root *node // 树根节点
	size uint  // 节点数
	lock sync.Mutex
}

// 工厂方法
func NewBST() *BinarySearchTree {
	return new(BinarySearchTree)
}

// 插入节点
func (t *BinarySearchTree) Insert(key uint, val interface{}) {
	t.lock.Lock()
	defer t.lock.Unlock()
	nd := new(node)
	nd.key = key
	nd.value = val
	nd.left = nil
	nd.right = nil

	if t.root == nil {
		t.root = nd
	} else {
		t.insertNode(t.root, nd)
	}
	t.size++
}

// 内部插入节点的递归方法
func (t *BinarySearchTree) insertNode(at, new *node) {
	if new.key == at.key {
		return
	}

	if new.key < at.key {
		// 向左查找
		if at.left == nil {
			at.left = new
		} else {
			t.insertNode(at.left, new)
		}
	} else {
		// 向右查找
		if at.right == nil {
			at.right = new
		} else {
			t.insertNode(at.right, new)
		}
	}
}

// 查找节点
func (t *BinarySearchTree) Search(key uint) *node {

	// nd := t.root
	if t.root != nil {
		return t.searchNode(key, t.root)
	}
	return nil
}

// 内部查找递归方法
func (t *BinarySearchTree) searchNode(key uint, at *node) *node {
	if at.key == key {
		return at
	} else if at.key > key {
		if at.left != nil {
			return t.searchNode(key, at.left)
		}
	} else {
		if at.right != nil {
			return t.searchNode(key, at.right)
		}
	}
	return nil
}

// 返回节点数
func (t *BinarySearchTree) Len() uint {
	return t.size
}

// 中序遍历: 每课子树以左中右顺序遍历
func (t *BinarySearchTree) InOrderTraversal(handler func(*node)) {
	nd := t.root
	if nd != nil {
		t.inOrderTraversalNode(nd, handler)
	}
}

// 内部递归方法：中序遍历所有节点
func (t *BinarySearchTree) inOrderTraversalNode(at *node, handler func(*node)) {
	if at.left != nil {
		t.inOrderTraversalNode(at.left, handler)
	}
	handler(at)
	if at.right != nil {
		t.inOrderTraversalNode(at.right, handler)
	}
}

// 前序遍历：每课子树以中左右顺序遍历
func (t *BinarySearchTree) FrontOrderTraversal(handler func(*node)) {
	nd := t.root
	if nd != nil {
		t.frontOrderTraversalNode(nd, handler)
	}
}

func (t *BinarySearchTree) frontOrderTraversalNode(at *node, handler func(*node)) {
	handler(at)
	if at.left != nil {
		t.frontOrderTraversalNode(at.left, handler)
	}
	if at.right != nil {
		t.frontOrderTraversalNode(at.right, handler)
	}
}

// 后续遍历：每课子树以左右中顺序遍历
func (t *BinarySearchTree) BackOrderTraversal(handler func(*node)) {
	nd := t.root
	if nd != nil {
		t.backOrderTraversalNode(nd, handler)
	}
}
func (t *BinarySearchTree) backOrderTraversalNode(at *node, handler func(*node)) {
	if at.left != nil {
		t.backOrderTraversalNode(at.left, handler)
	}
	if at.right != nil {
		t.backOrderTraversalNode(at.right, handler)
	}
	handler(at)
}

// 层序遍历:使用队列
func (t *BinarySearchTree) LevelOrderTraversal(handler func(*node)) {
	// 队列
	q := queue.NewLinkQueue(int(t.size))

	if t.root != nil {
		q.Enqueue(t.root)
	}

	for {
		if q.Size() > 0 {
			element := q.Dequeue()
			nd := element.(*node)
			handler(nd)
			if nd.left != nil {
				q.Enqueue(nd.left)
			}
			if nd.right != nil {
				q.Enqueue(nd.right)
			}
		} else {
			break
		}
	}
}

// 清空树的所有节点
func (t *BinarySearchTree) Clean() bool {
	t.lock.Lock()
	defer t.lock.Unlock()
	// 二叉树的清空，实际上就是后序遍历删除
	t.clean(t.root)
	return t.Len() == 0
}

func (t *BinarySearchTree) clean(n *node) {
	if n == nil {
		return
	}
	if n.left != nil {
		t.clean(n.left)
	}
	if n.right != nil{
		t.clean(n.right)
	}
	n.remove()
	t.size--
	n = nil
}

• 先找到要删除的结点
• 如果没找到，则不删除
• 如果找到，分为以下3种情况：
  • case1:找到的结点的左右孩子都为空，那么直接删除此结点即可
  • case2:找到的结点的左右孩子有一个为空，那么将不空的那个孩子代替要删的结点即可
  • case3:找到的结点的左右孩子都不为空，那么找到这个结点的右子树中的最小结点（此结点的左孩子一定为空），将最小结点的值赋给要删除的结点，然后删除最小结点（因为最小结点属于case1或case2的一种，所以删除实现非常简单）

// 删除节点
func (t *BinarySearchTree) Remove(key uint) bool {
	t.lock.Lock()
	defer t.lock.Unlock()
	remNode := remove(t.root, key)
	if remNode != nil {
		t.size--
		return true
	}
	return false
}

func remove(at *node, key uint) *node {
	if at == nil {
		return nil
	}

	// 如果key< node.key 则向左寻找
	if key < at.key {
		// 将左节点作为新节点递归继续寻找
		at.left = remove(at.left, key)
		return at
	}

	// 如果key> node.key 则向右寻找
	if key > at.key {
		// 将右节点作为新节点递归继续寻找
		at.right = remove(at.right, key)
		return at
	}

	// 如果key==node.key 判断node有没有左右子树，如果没有，则直接删除
	if at.left == nil && at.right == nil {
		at = nil
		return at
	}
	// 如果key==node.key 判断node有没有左右子树，如果有右子树，则将右子树直接赋值给当前节点，完成覆盖删除
	if at.left == nil {
		at = at.right
		return at
	}

	// 如果key==node.key 判断node有没有左右子树，如果有右子树，则将右子树直接赋值给当前节点，完成覆盖删除
	if at.right == nil {
		at = at.left
		return at
	}

	mostLeftMode := at.right
	// 要删除的节点有2个字节点，找到右子树的最左节点，替换当前节点
	for {
		// 一直遍历找到最左节点
		if mostLeftMode != nil && mostLeftMode.left != nil {
			mostLeftMode = mostLeftMode.left
		} else {
			break
		}
	}

	// 使用右子树的最左节点替换当前的节点，即删除当前节点
	at.key, at.value = mostLeftMode.key, mostLeftMode.value
	at.right = remove(at.right, at.key)
	return at
}