树 是 N(N>=0)个节点的有限集。当N=0时称为空树。 在任意一棵非空树中：
- 1、有且仅有一个特定的称为根节点
- 2、当N>1时，其余节点可分为M个互不相交的有限集合，其中每一个集合本身又是一棵树，并且称为根的子树
结点拥有的子树树称为结点度
度为0的结点称为叶结点或者终端结点
度不为0的结点称为非终端结点或者分支结点
除根结点之外，分支节点也称为内部结点。树的度是树内部各结点的度的最大值
节点间的关系
- 1、结点的子树的根称为该结点的孩子(Child)，相应的，该结点称为孩子的双亲(Parent)
- 2、同一个双亲的孩子之间称为兄弟
结点的层次从根开始定义起，根为第一层，根的孩子为第二层，依次类推
为什么要有树结构
树结构是一种天然的组织结构，将数据使用树存储的时候，出奇的高效
我们生活中有很多树结构
- 1、每个结点最多有两棵树
- 2、左树和右树是有顺序的，次序不能颠倒
- 3、即使树中某个结点只有一棵树，也要区分它是左子树还是右子树
- 4、左斜树：所有的结点都只有左子斜树的二叉树叫左斜树
- 5、右斜树：所有的结点都只有右子斜树的二叉树叫右斜树
- 6、满二叉树：所有的结点都存在左子树和右子树，并且所有叶子都在同一层上
- 7、完全二叉树：所有的结点都存在左子树和右子树，左右两边不一定在同一层次
二叉树的基本数据结构
class Node: NSObject {
var E:Int
var left:Node?
var right:Node?
}
二分搜索树(Binary Search Tree)
二分搜索树也是一种二叉树 二分搜索树的每个节点的值
- 大于其左子树的所有节点的值
- 小于其右子树的所有节点的值
我们现在就来实现一个简单的二分搜索树吧
节点
//节点
class Node: NSObject {
var E:Int = 0
var left:Node?
var right:Node?
override init() {
super.init()
}
init(E:Int) {
self.E = E
self.left = nil
self.right = nil
}
}
我们实现的二分搜索树实现以下功能
- 1、判断树是否为空
- 2、添加元素
- 3、查看二分搜索树中是否包含某个元素
- 4、二分搜索树的前序遍历、中序遍历、后序遍历
- 5、寻找二分搜索树的最小元素，删除二分搜索树的最小元素
- 6、寻找二分搜索树的最大元素、删除二分搜索树的最大元素
- 7、删除任意的节点
我们创建一个BTS类，里面有两个成员变量
var size = 0 //树的大小
var root:Node! //根节点
1、判断树是否为空
func isEmpty() -> Bool{
return size == 0;
}
2、添加元素
func add(E:Int) {
if root == nil {
size += 1
root = Node(E: E)
}else{
addNode(E: E, node: root)
}
}
// 向以node为根的二分搜索树中插入元素e，递归算法
private
func addNode(E:Int,node:Node) {
//递归用法，先判断结束语句
if node.E == E {
return
}else if((E < node.E) && (node.left == nil)){
//遍历到最后，添加左叶子
node.left = Node(E: E)
size += 1
return
}else if((E > node.E) && (node.right == nil)){
//遍历到最后，添加右叶子
node.right = Node(E: E)
size += 1
return
}
//递归调用
if E < node.E {
addNode(E: E, node: node.left ?? Node())
}else{
addNode(E: E, node: node.right ?? Node())
}
}
思路：
- 1、首先判断root是否为空，如果root为空的话，第一个添加的元素就是root
- 2、在root不为空的时候，我们需要循环遍历，E>节点值的时候添加到右子树，E<节点值的时候添加到左子树，知道循环遍历到最后一个节点为空的时候，添加上去
3、查看二分搜索树中是否包含某个元素
//查看二分搜索树中是否包含某个元素
func contain(E:Int) -> Bool {
return containNode(E: E, node: root)
}
// 看以node为根的二分搜索树中是否包含元素e, 递归算法
private
func containNode(E:Int,node:Node?) -> Bool {
if node == nil {
return false
}
if node?.E == E{
return true
}else if (node?.E)! > E {
//左
return containNode(E: E, node: node?.left )
}else{
//右
return containNode(E: E, node: node?.right)
}
}
4、前序遍历、中序遍历、后序遍历
前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前续遍历左子树，然后再前序遍历右子树
//二分搜索树的前序遍历
func preOrder() {
preOrder(node: root)
}
// 前序遍历以node为根的二分搜索树, 递归算法
private
func preOrder(node:Node?) {
//结束条件
if node == nil {
return
}
print(node?.E ?? "nil")
preOrder(node: node?.left)
preOrder(node: node?.right)
}
中序遍历：规则是若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点是左子树，然后是访问根节点，最后中序遍历右子树
// 二分搜索树的中序遍历
func inOrder() {
inOrder(node: root)
}
// 中序遍历以node为根的二分搜索树, 递归算法
private
func inOrder(node:Node?) {
//结束条件
if node == nil {
return
}
inOrder(node: node?.left)
print(node?.E ?? "nil")
inOrder(node: node?.right)
}
后序遍历：规则是若树为空，则空操作返回，否则从左到右先子叶后节点的方式遍历访问左右子树，最后是访问根节点
// 二分搜索树的后序遍历
func postOrder() {
postOrder(node: root)
}
// 后序遍历以node为根的二分搜索树, 递归算法
private
func postOrder(node:Node?) {
//结束条件
if node == nil {
return
}
inOrder(node: node?.left)
inOrder(node: node?.right)
print(node?.E ?? "nil")
}
5、寻找二分搜索树的最小元素，删除二分搜索树的最小元素
寻找二分搜索树的最小元素
// 寻找二分搜索树的最小元素
func minimum() -> Int {
if size == 0 {
return 10086
}
return minimum(node: root).E
}
//查找最小数据 递归算法
private
func minimum(node:Node?) -> Node{
if node?.left == nil {
return node ?? Node()
}
return minimum(node: node?.left)
}
思路：
- 1、根据二分搜索树的定义我们知道，最小值一定在最左侧子节点上面，我们一直往最左侧子节点遍历就可以了
删除二分搜索树的最小元素
// 从二分搜索树中删除最小值所在节点, 返回最小值
func removeMin() -> Int {
if size == 0 {
return 10086
}
root = removeMin(node: root)
return minimum()
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private
func removeMin(node:Node?) -> Node? {
if node?.left == nil {
size -= 1
let rightNode = node?.right
node?.right = nil
return rightNode
}
node?.left = removeMin(node: node?.left)
return node
}
思考： 在删除最小元素的时候我们需要考虑两种情况
- 1、最小元素没有子树了
- 2、最小元素有右子树
针对上面这种，我们代码可以这样写
if node?.left == nil {
size -= 1
let rightNode = node?.right
node?.right = nil
return rightNode
}
在最小元素有有右子树的时候，我们需要把这个右子树占据我们删除的那个子树的位置
6、寻找二分搜索树的最大元素、删除二分搜索树的最大元素
寻找二分搜索树的最大元素
// 寻找二分搜索树的最大元素
func maximum() -> Int {
if size == 0 {
return 10086
}
return maximum(node: root)
}
//查找最大数据 递归算法
private
func maximum(node:Node?) -> Int {
if node?.right == nil {
return node?.E ?? 10086
}
return maximum(node: node?.right)
}
删除二分搜索树的最大元素
// 从二分搜索树中删除最大值所在节点, 返回最大值
func removeMax() -> Int {
if size == 0 {
return 10086
}
root = removeMax(node: root)
return maximum()
}
// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
private
func removeMax(node:Node?) -> Node? {
if node?.right == nil {
size -= 1
let leftNode = node?.left
node?.left = nil
return leftNode
}
node?.right = removeMax(node: node?.right)
return node
}
7、删除任意的节点
// 删除为E的节点
func remove(E:Int) ->Node{
root = remove(E: E, node: root)
return root
}
// 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
// 返回删除节点后新的二分搜索树的根
private
func remove(E:Int,node:Node?) -> Node? {
if node == nil {
return nil
}
if E < (node?.E)! {
node?.left = remove(E: E, node: node?.left)
return node
}else if E > (node?.E)! {
node?.right = remove(E: E, node: node?.right)
return node
}else{
//找到了
// 待删除节点左子树为空的情况
if node?.left == nil{
let rightNode = node?.right
node?.right = nil
size -= 1
return rightNode
}
// 待删除节点右子树为空的情况
if node?.right == nil{
let leftNode = node?.left
node?.left = nil
size -= 1
return leftNode
}
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
let successor = minimum(node: node?.right)
successor.right = removeMin(node: node?.right)
successor.left = node?.left
node?.right = nil
node?.left = nil
return successor
}
}
思考：
- 1、在找到待删除节点以后，左节点为空时，这个时候跟删除最小值类似
// 待删除节点左子树为空的情况
if node?.left == nil{
let rightNode = node?.right
node?.right = nil
size -= 1
return rightNode
}
- 2、在找到待删除节点以后，右节点为空时，这个时候跟删除最大值类似
// 待删除节点右子树为空的情况
if node?.right == nil{
let leftNode = node?.left
node?.left = nil
size -= 1
return leftNode
}
- 3、待删除节点左右子树均不为空的情况 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点；用这个节点顶替待删除节点的位置
