基础算法汇总之二叉搜索树实现

一. 树定义

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

这个是学术定义，简单的大白话就是，树可以看成一串葡萄（自行脑补）。

二. 树的种类

下面列举了一些开发的时候常接触的树，简单做了下分类：

三. 常用术语

四. 二叉树定义

二叉树是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

五. 二叉树的性质

一共有下面几个常用的性质：

• 在二叉树的第n成上至多有$2^{n-1} $个结点（n ≥1）
• 深度为k的二叉树至多有个结点（k≥1）
• 对于任何一颗二叉树T，如果其终端结点数为a，度为2的结点树为b，则a=b+1
• 具有n个结点的完全二叉树的深度为

六. 二叉树具体实现

这里我们使用golang作为实现二叉树的编程语言，原理都一样，也可以用其他语言去实现，这里实现几个关于二叉树的重要方法：

• 遍历二叉树（递归/非递归）：前、中、后和层次
• 二叉树的深度

6.1. 定义二叉树

先定义基本操作接口

type BinaryTreeOperation interface {
  RecursionPreOrderTraverse()  //   递归前序遍历
  PreOrderTraverse()           //   非递归前序遍历
  RecursionInOrderTraverse()   //   递归中序遍历
  InOrderTraverse()            //   非递归中序遍历
  RecursionPostOrderTraverse() //   递归后序遍历
  PostOrderTraverse()          //   非递归后序遍历
  LevelTraverse()              // 层次遍历

  TreeDepth() int   // 树深
  CountLeaves() int // 叶子数
  CountNodes() int  // 结点数
}

接着定义二叉树的结点和操作实现类

// TreeNode 二叉树结点定义
type TreeNode struct {
  data int
  Left *TreeNode
  Right *TreeNode
}

// NewTreeNode 构建结点数据
func NewTreeNode(left, right *TreeNode, data int) *TreeNode {
  return &TreeNode{Left: left, Right: right, data: data}
}

// BinaryTree 二叉树实现
type BinaryTree struct {
  root *TreeNode
}

初始化数据，这里构建的数据就是第四部分二叉树定义中的那颗二叉树

// NewBinaryTree 二叉树的构造函数
func NewBinaryTree() *BinaryTree {
  tree := &BinaryTree{}
  tree.InitTree()
  return tree
}

// InitTree 初始化二叉树的数据
func (b *BinaryTree) InitTree() {
  node9 := NewTreeNode(nil, nil, 9)
  node8 := NewTreeNode(nil, nil, 8)
  node7 := NewTreeNode(node9, nil, 7)
  node6 := NewTreeNode(nil, nil, 6)
  node5 := NewTreeNode(node8, nil, 5)
  node4 := NewTreeNode(nil, nil, 4)
  node3 := NewTreeNode(node6, node7, 3)
  node2 := NewTreeNode(node4, node5, 2)
  b.root = NewTreeNode(node2, node3, 1)
}

前期的准备工作就搞定了，现在我们开始实现二叉树的相关操作！

6.2. 递归遍历

这里使用golang的匿名函数修改共享变量，实现递归遍历。

6.2.1. 前序遍历

遍历原则：若二叉树是空，这操作是空；否则访问根节点，左子树、右子树。

func (b *BinaryTree) RecursionPreOrderTraverse() {
  // 存放遍历数据
  result := make([]int, 0)
  // 定义匿名函数
  var innerTraverse func(node *TreeNode)
  
  // 匿名函数实现
  innerTraverse = func(node *TreeNode) {
    // 前序遍历是 根 、 左、 右
    result = append(result, node.data)
    if node.Left != nil {
      innerTraverse(node.Left)
    }
    if node.Right != nil {
      innerTraverse(node.Right)
    }
  }
  // 当前二叉树不为空，调用内部匿名函数
  if b.root != nil {
    innerTraverse(b.root)
  }
  // 输出结果
  fmt.Printf("前序遍历：%v\n", result)
}

6.2.2. 中序遍历

遍历原则：若二叉树是空，这操作是空；否则访问左子树、根节点、右子树。

这个和前序遍历是基本一样，就是append的位置不一样。

func (b BinaryTree) RecursionInOrderTraverse() {
  result := make([]int, 0)

  var innerTraverse func(node *TreeNode)

  innerTraverse = func(node *TreeNode) {
    if node.Left != nil {
      innerTraverse(node.Left)
    }
    result = append(result, node.data)
    if node.Right != nil {
      innerTraverse(node.Right)
    }
  }
  if b.root != nil {
    innerTraverse(b.root)
  }

  fmt.Printf("中序遍历：%v\n", result)
}

6.2.3. 后序遍历

遍历原则：若二叉树是空，这操作是空；否则访问左子树、右子树、根节点。

func (b BinaryTree) RecursionPostOrderTraverse() {
  result := make([]int, 0)

  var innerTraverse func(node *TreeNode)

  innerTraverse = func(node *TreeNode) {
    if node.Left != nil {
      innerTraverse(node.Left)
    }
    if node.Right != nil {
      innerTraverse(node.Right)
    }
    result = append(result, node.data)
  }
  if b.root != nil {
    innerTraverse(b.root)
  }

  fmt.Printf("后序遍历：%v\n", result)
}

6.3. 非递归遍历

6.3.1. 前序遍历

执行示意图：前中后序遍历这个执行流程都是一样的，区别在于获取数据先后顺序上的区别。

执行描述：这里是相当于将递归的执行过程放在桌面上（递归的话，相当于将执行的函数调用放入一个函数调用栈中），出栈入栈就相当于函数调用。

// PreOrderTraverse 非递归前序遍历
func (b BinaryTree) PreOrderTraverse() {
  // 模拟栈
  stack := make([]*TreeNode, 0)
  // 存放遍历的数据
  result := make([]int, 0)
  // 判断二叉树是否为空
  if b.root == nil {
    return
  }
  // 将指针指向根结点
  start := b.root
  
  for start != nil || len(stack) != 0 {
    // 先遍历左子树，直到左子树为nil
    if start != nil {
      // 每次遍历将结点数据放到缓存数组
      result = append(result, start.data)
      // 保存当前的结点到模拟的栈中
      stack = append(stack, start)
      // 将当前指针指向下一结点的左子树
      start = start.Left
    } else {
      // 当指针指针的结点是nil说明：当前指针已经指向了左子树的叶子结点
      
      lens := len(stack) - 1
      // 获取栈顶的结点元素
      pop := stack[lens]
      // 模拟出栈
      stack = stack[:lens]
      // 指针指向结点的右子树
      start = pop.Right
    }
  }
  
  fmt.Printf("非递归前序遍历：%v\n", result)
}

执行流程：

• 先判断当前二叉树是否为空树，如果不是将指针指向根结点；
• 判断当前指针是否为空，并且判断当前栈是否为空栈；
• 接着判断当前指针不为空，则将前指针指向的结点数据放入缓存数组，并将当前指针入栈；
• 直到当前指针为空，说明已经到了左子树的叶子节点，此时就需要回溯（将栈顶元素赋值给当前指针，然后栈顶出栈），直到当前指针指向的结点不是nil，此时将当前指针指向的结点的右子树地址赋值给当前指针。
• 后面的流程依次相似，直到栈中元素是空的时候，跳出循环。

6.3.2. 中序遍历

中序遍历需要在回溯的时候获取数据。

func (b BinaryTree) InOrderTraverse() {
  // 模拟栈
  stack := make([]*TreeNode, 0)
  // 存放遍历的数据
  result := make([]int, 0)
  // 判断二叉树是否为空
  if b.root == nil {
    return
  }

  start := b.root

  for start != nil || len(stack) != 0 {

    if start != nil {
      stack = append(stack, start)
      start = start.Left
    } else {
      lens := len(stack) - 1
      pop := stack[lens]
      result = append(result, pop.data)
      stack = stack[:lens]
      start = pop.Right
    }
  }
  fmt.Printf("非递归中序遍历：%v\n", result)
}

6.3.3. 后序遍历

这个后续遍历比较麻烦，需要保证左右子节点都遍历完成才可以输出根结点，这里就需要增加一个延后指针指向出栈的元素。

func (b BinaryTree) PostOrderTraverse() {
  // 模拟栈
  stack := make([]*TreeNode, 0)
  // 存放遍历的数据
  result := make([]int, 0)
  // 判断二叉树是否为空
  if b.root == nil {
    return
  }
  var temp *TreeNode

  stack = append(stack, b.root)

  for len(stack) != 0 {

    cur := stack[len(stack) - 1]
    // 当前结点是nil / 延后指针不为空并且延后指针的左指针或者右指针和当前栈顶指针一样
    // 此时说明左右子节点都遍历完成了。
    if (cur.Left == nil && cur.Right == nil) || (temp != nil && (temp == cur.Left || temp == cur.Right)) {
      result = append(result, cur.data)
      temp = cur
      stack = stack[:len(stack) - 1]
    } else {
      // 保证先让右结点指针入栈，这样才可以让左结点指针先于右结点指针
      if cur.Right != nil {
        stack = append(stack, cur.Right)
      }
      if cur.Left != nil {
        stack = append(stack, cur.Left)
      }
    }

  }

  fmt.Printf("非递归后序遍历：%v\n", result)
}

示意图：

6.4. 层次遍历

这个层次遍历也是依赖队列先进先出实现的。

// LevelTraverse 层次遍历
func (b BinaryTree) LevelTraverse() {
  // 存放遍历的数据
  result := make([]int, 0)
  queue := make([]*TreeNode, 0)
  // 判断二叉树是否为空
  if b.root == nil {
    return
  }
  // 放入第一个元素
  queue = append(queue, b.root)
  for len(queue) > 0 {
    // 取出队列中队头的元素
    head := queue[0]
    // 让队头出队
    queue = queue[1:]
    // 获取对头元素
    result = append(result, head.data)
    // 如果左子树不为空则加入队尾
    if head.Left != nil {
      queue = append(queue, head.Left)
    }
    // 如果右子树不为空则加入队尾
    if head.Right != nil {
      queue = append(queue, head.Right)
    }
  }
  fmt.Printf("层次遍历：%v\n", result)
}

示意图：

6.5. 最大深度

递归实现！

func (b BinaryTree) TreeDepth() int {
  if b.root == nil {
    return 0
  }
  var innerDepth func(node *TreeNode) int
  // 定义匿名函数
  innerDepth = func(node *TreeNode) int {

    if node == nil {
      return 0
    }

    l := innerDepth(node.Left) + 1
    r := innerDepth(node.Right) + 1

    if l < r {
      l, r = r, l
    }

    return l

  }
  return innerDepth(b.root)
}

不用递归，也可以对层次遍历修改一下，就可以实现最大深度获取。

七. 二叉查找树

从上面的也可以看到二叉树是没有顺序，先后的区别的。在二叉树上面进行查找，插入，删除都不可以。所以下面介绍使用很广泛的二叉查找树。

7.1. 二叉查找树性质

二叉查找树的性质如下：

• 若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；

一颗典型的二叉查找树如图：

7.2. 创建（增加结点）

二叉查找树是从二叉树演变而来，可以在上面二叉数的基础上扩展。

构建一棵二叉查找树我们需要注意要满足二叉查找树的性质。

另外需要注意的是：二叉查找树的重复元素的处理，这里使用的int的基础数据类型，对此处理方式，发现相同的话就不插入；但是数据区域可能是对象这种复杂的数据类型。这里就需要考虑通过增加附加区域存储或者存储到另一棵树中（这种情况这里不进行过多的讨论）。

创建二叉查找树说白了还是通过遍历找到结点然后进行插入。所以有了上面二叉树的基础，我们在遍历方法上稍作修改就可以实现。

func (b *BinaryTree) Insert(data int) {
  // 如果根结点是nil，则创建
  if b.root == nil {
    b.root = NewTreeNode(nil, nil, data)
    return
  }
  // 定义匿名递归函数
  var innerTraverse func(node *TreeNode)
  
  innerTraverse = func(node *TreeNode) {
    // 如果当前结点数据小于data，则需要在往右子树上查找
    if node.data < data {
      // 如果此时右子树是nil的话，直接赋值就可以
      if node.Right == nil {
        node.Right = NewTreeNode(nil, nil, data)
      } else {
        // 不是的再往下查询
        innerTraverse(node.Right)
      }

    } else {
      // 与右子树操作类似
      if node.Left == nil {
        node.Left = NewTreeNode(nil, nil, data)
      } else {
        innerTraverse(node.Left)
      }
    }
  }
  innerTraverse(b.root)
}

此时构建一个7.1中的二叉查找树如下：

tree := binary_tree.SimpleTree()

tree.Insert(10)
tree.Insert(7)
tree.Insert(15)
tree.Insert(9)
tree.Insert(8)
tree.Insert(18)
tree.Insert(12)
tree.Insert(3)
tree.Insert(13)

tree.RecursionInOrderTraverse()  // 中序遍历：[3 7 8 9 10 12 13 15 18]

这里的中序遍历就是按照大小顺序排序输出的！

7.3. 结点数据搜索

给定一个数据搜索二叉查找树中是否存在

func (b *BinaryTree) Search(data int) bool {
  
  // 如果root结点是nil直接返回false
  if b.root == nil {
    return false
  }

  var innerTraverse func(node *TreeNode) bool

  innerTraverse = func(node *TreeNode) bool {
    // 当前结点是nil返回false
    if node == nil {
      return false
    } else {
      var status bool
      // 相等
      if node.data == data {
        status = true
      } else if node.data < data {
        // 小于，继续遍历右子树
        status = innerTraverse(node.Right)
      } else {
        // 大于，继续遍历左子树
        status = innerTraverse(node.Left)
      }
      return status
    }
  }
  
  // 调用
  return innerTraverse(b.root)
}

7.4.获取最小结点

二叉查找树的结构，可以很简单的直到，最左侧的结点是最小，最右侧的结点是最大。

// MaxNode 最值
func (b *BinaryTree) MaxNode() *TreeNode {
  if b.root == nil {
    return nil
  }

  p := b.root

  for p.Right != nil {
    p = p.Right
  }
  return p
}

7.5. 最小结点删除

主要是需要注意一下对于删除节点的右子树的处理。

// DeleteMin 删除二叉查找树中最小的结点
func (b *BinaryTree) DeleteMin() bool {
  return b.removeMin(b.root)
}

// removeMin 删除某结点树中最小结点
func (b *BinaryTree) removeMin(node *TreeNode) *TreeNode {
  // 如果node的左子树是nil的话，说明已经到了最左侧
  if node.Left == nil {
    right := node.Right
    node.Right = nil
    return right
  }
  node.Left = b.removeMin(node.Left)
  return node
}

7.5. 删除结点

这里操作稍微麻烦，涉及到四种情况，下面逐一说明一下：

第一种情况：删除的结点不存在左右孩子：这种情况可以直接删除结点

第二种情况：删除的结点存在左孩子：这时直接让该结点的父节点指向当前结点的左孩子，然后删除当前结点；

第三种情况：删除的结点存在右孩子：这时直接让该结点的父节点指向当前结点的左孩子，然后删除当前结点；

第四种情况：删除的结点存在左右孩子：找到右子树找到最小的节点，和当前结点的值交换，最后删除

代码实现：

// Remove 移除节点
func (b *BinaryTree) Remove(data int) {
  b.root = b.remove(b.root, data)
}

// remove 递归移除
func (b *BinaryTree) remove(node *TreeNode, data int) *TreeNode {

  // 如果当前结点是nil
  if node == nil {
    return nil
  }

  if data < node.data {
    node.Left = b.remove(node.Left, data)
    return node
  } else if data > node.data {
    node.Right = b.remove(node.Right, data)
    return node
  } else {
    // data 和当前结点的data的数据是一致的，根据当前结点左右子树分情况去讨论

    // 待删除的结点左子树为空
    if node.Left == nil {
      right := node.Right
      node.Right = nil
      return right
    }

    // 待删除的结点的右子树为空
    if node.Right == nil {
      left := node.Left
      node.Left = nil
      return left
    }

    // 待删除的结点的左右子树否不为空

    // 找到待删除结点右子树中最小的结点
    minMode := b.min(node.Right)
    // 移除待删除结点的右子树中最小的结点
    minMode.Right = b.removeMin(node.Right)
    minMode.Left = node.Left

    // 将待删除结点的左右子树都设置为nil
    node.Left = nil
    node.Right = nil

    // 将新的结点返回
    return minMode
  }
}

7.6. 注意

这里随着结点增加，我们在使用递归进行操作的时候，可能会出现栈溢出，上述操作更推荐使用非递归的写法。

另外一个问题就是，二叉查找树的退化问题，看一个极端的示例：

这种情况也是满足二叉查找树的条件，然而，此时的二叉查找树已经近似退化为一条链表，这样的二叉查找树的查找时间复杂度顿时变成了 O(n)，可想而知，我们必须不能让这种情况发生，为了解决这个问题，可以使用平衡二叉树（AVL）。