数据结构-树

# 定义

树的定义如下。

树(tree)是n(n≥0)个节点的有限集。当n=0时,称为空树。在任意一个非空树中,有如下特点。

  1. 有且仅有一个特定的称为根的节点。

  2. 当n>1时,其余节点可分为m(m>0)个互不相交的有限集,每一个集合本身又是一个树,并称为根的子树。

二叉查找树

# 二叉树

二叉树(binarytree)是树的一种特殊形式。二叉,顾名思义,这种树的每个节点最多有2个孩子节点。注意,这里是最多有2个,也可能只有1个,或者没有孩子节点。

二叉树节点的两个孩子节点,一个被称为左孩子(left child),一个被称为右孩子(right child)。这两个孩子节点的顺序是固定的,就像人的左手就是左手,右手就是右手,不能够颠倒或混淆。

二叉查找树

# 满二叉树

一个二叉树的所有非叶子节点都存在左右孩子,并且所有叶子节点都在同一层级上,那么这个树就是满二叉树。

二叉查找树

# 完全二叉树

对一个有n个节点的二叉树,按层级顺序编号,则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同,则这个二叉树为完全二叉树。

二叉查找树

# 二叉树存储

# 链式存储结构

链表是一对一的存储方式,每一个链表节点拥有data变量和一个指向下一节点的next指针。

而二叉树稍微复杂一些,一个节点最多可以指向左右两个孩子节点,所以二叉树的每一个节点包含3部分。

  • 存储数据的data变量

  • 指向左孩子的left指针

  • 指向右孩子的right指针

二叉查找树

# 数组存储

使用数组存储时,会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺,则数组的相应位置也空出来。

二叉查找树

为什么这样设计呢?

因为这样可以更方便地在数组中定位二叉树的孩子节点和父节点。

假设一个父节点的下标是parent,那么它的左孩子节点下标就是 2×parent+1;右孩子节点下标就是 2×parent + 2。

反过来,假设一个左孩子节点的下标是leftChild,那么它的父节点下标就是(leftChild-1)/ 2。

假如节点4在数组中的下标是3,节点4是节点2的左孩子,节点2的下标可以直接通过计算得出。

节点2的下标 = (3-1)/2 = 1

显然,对于一个稀疏的二叉树来说,用数组表示法是非常浪费空间的。

# 二叉树的应用

二叉树包含许多特殊的形式,每一种形式都有自己的作用,但是其最主要的应用还在于进行查找操作维持相对顺序这两个方面

# 查找操作

二叉查找树在二叉树的基础上增加了以下几个条件。

  • 如果左子树不为空,则左子树上所有节点的值均小于根节点的值

  • 如果右子树不为空,则右子树上所有节点的值均大于根节点的值

  • 左、右子树也都是二叉查找树

二叉查找树

例如查找值为4的节点,步骤如下。

  1. 访问根节点6,发现4<6。

  2. 访问节点6的左孩子节点3,发现4>3。

  3. 访问节点3的右孩子节点4,发现4=4,这正是要查找的节点。

对于一个节点分布相对均衡的二叉查找树来说,如果节点总数是n,那么搜索节点的时间复杂度就是O(logn),和树的深度是一样的。

这种依靠比较大小来逐步查找的方式,和二分查找算法非常相似。

# 维持相对顺序

这一点仍然要从二叉查找树说起。二叉查找树要求左子树小于父节点,右子树大于父节点,正是这样保证了二叉树的有序性。

因此二叉查找树还有另一个名字——二叉排序树(binary sort tree)。

新插入的节点,同样要遵循二叉排序树的原则。例如插入新元素5,由于5<6,5>3,5>4,所以5最终会插入到节点4的右孩子位置。

二叉查找树

再如插入新元素10,由于10>6,10>8,10>9,所以10最终会插入到节点9的右孩子位置。

二叉查找树

# 二叉树的遍历

从节点之间位置关系的角度来看,二叉树的遍历分为4种。

  1. 前序遍历。

  2. 中序遍历。

  3. 后序遍历。

  4. 层序遍历。

从更宏观的角度来看,二叉树的遍历归结为两大类。

  1. 深度优先遍历(前序遍历、中序遍历、后序遍历)。

  2. 广度优先遍历(层序遍历)。

# 深度优先遍历

所谓深度优先,顾名思义,就是偏向于纵深,“一头扎到底”的访问方式。

# 前序遍历

二叉树的前序遍历,输出顺序是根节点、左子树、右子树。

二叉查找树

# 中序遍历

中序遍历二叉树的中序遍历,输出顺序是左子树、根节点、右子树。

二叉查找树

# 后序遍历

后序遍历二叉树的后序遍历,输出顺序是左子树、右子树、根节点。

二叉查找树

# 递归实现

class TreeNode {
  leftChild = null
  rightChild = null

  constructor (data) {
    this.data = data || null
  }
}

const a = new TreeNode(1)
const b = new TreeNode(2)
const c = new TreeNode(3)
const d = new TreeNode(4)
const e = new TreeNode(5)
const f = new TreeNode(6)

a.leftChild = b
a.rightChild = c

b.leftChild = d
b.rightChild = e

c.rightChild = f

/**
 * 前序遍历
 */
function preOrderTraveral (list, result = []) {
  // 输出
  result.push(list.data)

  if (list.leftChild) {
    preOrderTraveral(list.leftChild, result)
  }
  if (list.rightChild) {
    preOrderTraveral(list.rightChild, result)
  }

  return result
}

console.log(preOrderTraveral(a))

/**
 * 中序遍历
 */
function inOrderTraveral (list, result = []) {
  if (list.leftChild) {
    inOrderTraveral(list.leftChild, result)
  }

  // 输出
  result.push(list.data)

  if (list.rightChild) {
    inOrderTraveral(list.rightChild, result)
  }

  return result
}

console.log(inOrderTraveral(a))

/**
 * 后序遍历
 */
function postOrderTraveral (list, result = []) {
  if (list.leftChild) {
    postOrderTraveral(list.leftChild, result)
  }
  if (list.rightChild) {
    postOrderTraveral(list.rightChild, result)
  }

  // 输出
  result.push(list.data)

  return result
}

console.log(postOrderTraveral(a))

这3种遍历方式的区别,仅仅是输出的执行位置不同:前序遍历的输出在前,中序遍历的输出在中间,后序遍历的输出在最后。

# 非递归实现

function preOrderTraveralWithStack (list) {
  const stack = []
  const result = []

  while (list || stack.length) {
    while (list) {
      // 输出
      result.push(list.data)

      stack.push(list)
      list = list.leftChild
    }

    if (stack.length) {
      const prev = stack.pop()
      list = prev.rightChild
    }
  }

  return result
}

console.log(preOrderTraveralWithStack(a))

# 广度优先遍历

如果说深度优先遍历是在一个方向上“一头扎到底”,那么广度优先遍历则恰恰相反:先在各个方向上各走出1步,再在各个方向上走出第2步、第3步……一直到各个方向全部走完。

二叉查找树

# 代码实现

function levelOrderTraversal (list) {
  const queue = [list]
  const result = []

  while (queue.length) {
    const prev = queue.shift()
    result.push(prev.data)
    if (prev.leftChild) {
      queue.push(prev.leftChild)
    }
    if (prev.rightChild) {
      queue.push(prev.rightChild)
    }
  }

  return result
}