本文最后更新于：8 个月前

本博客参考于洛伊安妮·格罗纳编著的javascript数据结构与算法第三版及codeWay老师视频或其他博客资料，在此对此表示感谢!
github仓库：https://github.com/hzx17/

树结构

什么是树？

真实的树：

真实的树

树的特点：

树一般都有一个根，连接着根的是树干；
树干会发生分叉，形成许多树枝，树枝会继续分化成更小的树枝；
树枝的最后是叶子；

现实生活中很多结构都是树的抽象，模拟的树结构相当于旋转 180° 的树。

树的抽象

树结构对比于数组/链表/哈希表有哪些优势呢？

数组：

优点：可以通过下标值访问，效率高；
缺点：查找数据时需要先对数据进行排序，生成有序数组，才能提高查找效率；并且在插入和删除元素时，需要大量的位移操作；

链表：

优点：数据的插入和删除操作效率都很高；
缺点：查找效率低，需要从头开始依次查找，直到找到目标数据为止；当需要在链表中间位置插入或删除数据时，插入或删除的效率都不高。

哈希表：

优点：哈希表的插入/查询/删除效率都非常高；
缺点：空间利用率不高，底层使用的数组中很多单元没有被利用；并且哈希表中的元素是无序的，不能按照固定顺序遍历哈希表中的元素；而且不能快速找出哈希表中最大值或最小值这些特殊值。

树结构：

优点：树结构综合了上述三种结构的优点，同时也弥补了它们存在的缺点（虽然效率不一定都比它们高），比如树结构中数据都是有序的，查找效率高；空间利用率高；并且可以快速获取最大值和最小值等。

总的来说：每种数据结构都有自己特定的应用场景。

树结构：

树（Tree）：由 n（n ≥ 0）个节点构成的有限集合。当 n = 0 时，称为空树。
对于任意一棵非空树（n > 0），它具备以下性质：
- 数中有一个称为根（Root）的特殊节点，用 r 表示；
- 其余节点可分为 m（m > 0）个互不相交的有限集合 T1，T2，…，Tm，其中每个集合本身又是一棵树，称为原来树的子树（SubTree）。

树的常用术语：

树的常用术语

节点的度（Degree）：节点的子树个数，比如节点 B 的度为 2；
树的度：树的所有节点中最大的度数，如上图树的度为 2；
叶节点（Leaf）：度为 0 的节点（也称为叶子节点），如上图的 H，I 等；
父节点（Parent）：度不为 0 的节点称为父节点，如上图节点 B 是节点 D 和 E 的父节点；
子节点（Child）：若 B 是 D 的父节点，那么 D 就是 B 的子节点；
兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点，比如上图的 B 和 C，D 和 E 互为兄弟节点；
路径和路径长度：路径指的是一个节点到另一节点的通道，路径所包含边的个数称为路径长度，比如 A->H 的路径长度为 3；
节点的层次（Level）：规定根节点在 1 层，其他任一节点的层数是其父节点的层数加 1。如 B 和 C 节点的层次为 2；
树的深度（Depth）：树种所有节点中的最大层次是这棵树的深度，如上图树的深度为 4；

树结构的表示方式

最普通的表示方法：

最普通的表示方法

如图，树结构的组成方式类似于链表，都是由一个个节点连接构成。不过，根据每个父节点子节点数量的不同，每一个父节点需要的引用数量也不同。比如节点 A 需要 3 个引用，分别指向子节点 B，C，D；B 节点需要 2 个引用，分别指向子节点 E 和 F；K 节点由于没有子节点，所以不需要引用。

这种方法缺点在于我们无法确定某一结点的引用数。

儿子-兄弟表示法：

儿子-兄弟表示法

这种表示方法可以完整地记录每个节点的数据，比如：

//节点A
Node{
  //存储数据
  this.data = data
  //统一只记录左边的子节点
  this.leftChild = B
  //统一只记录右边的第一个兄弟节点
  this.rightSibling = null
}

//节点B
Node{
  this.data = data
  this.leftChild = E
  this.rightSibling = C
}

//节点F
Node{
  this.data = data
  this.leftChild = null
  this.rightSibling = null
}

这种表示法的优点在于每一个节点中引用的数量都是确定的。

儿子-兄弟表示法旋转

儿子-兄弟表示法组成的树结构，将其顺时针旋转 45° 之后：

旋转45度

这样就成为了一棵二叉树，由此我们可以得出结论：任何树都可以通过二叉树进行模拟。但是这样父节点不是变了吗？其实，父节点的设置只是为了方便指向子节点，在代码实现中谁是父节点并没有关系，只要能正确找到对应节点即可。

二叉树

二叉树的概念

如果树中的每一个节点最多只能由两个子节点，这样的树就称为二叉树；

二叉树的组成

二叉树可以为空，也就是没有节点；
若二叉树不为空，则它由根节点和称为其左子树 TL 和右子树 TR 的两个不相交的二叉树组成；

二叉树的五种形态

二叉树五种形态

上图分别表示：空的二叉树、只有一个节点的二叉树、只有左子树 TL 的二叉树、只有右子树 TR 的二叉树和有左右两个子树的二叉树。

二叉树的特性

一个二叉树的第 i 层的最大节点树为：2^(i-1)^，i >= 1；
深度为 k 的二叉树的最大节点总数为：2^k^ - 1 ，k >= 1；
对任何非空二叉树，若 n0 表示叶子节点的个数，n2表示度为 2 的非叶子节点个数，那么两者满足关系：n0 = n2 + 1

特殊的二叉树

完美二叉树

完美二叉树（Perfect Binary Tree）也成为满二叉树（Full Binary Tree），在二叉树中，除了最下一层的叶子节点外，每层节点都有 2 个子节点，这就构成了完美二叉树。

完美二叉树

完全二叉树

完全二叉树（Complete Binary Tree）:

除了二叉树最后一层外，其他各层的节点数都达到了最大值；
并且，最后一层的叶子节点从左向右是连续存在，只缺失右侧若干叶子节点；
完美二叉树是特殊的完全二叉树；

不是完全二叉树

在上图中，由于 H 缺失了右子节点，所以它不是完全二叉树。

二叉树的数据存储

常见的二叉树存储方式为数组和链表：

使用数组

完全二叉树：按从上到下，从左到右的方式存储数据。

节点	A	B	C	D	E	F	G	H	I
序号	1	2	3	4	5	6	7	8	9

使用数组存储时，取数据的时候也十分方便：左子节点的序号等于父节点序号 _ 2，右子节点的序号等于父节点序号 _ 2 + 1 。

非完全二叉树：非完全二叉树需要转换成完全二叉树才能按照上面的方案存储，这样会浪费很大的存储空间。

非完全二叉树

节点	A	B	C	^	^	F	^	^	^	^	^	^	M
序号	1	2	3	4	5	6	7	8	9	10	11	12	13

使用链表

二叉树最常见的存储方式为链表：每一个节点封装成一个 Node，Node 中包含存储的数据、左节点的引用和右节点的引用。

使用链表储存

二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称为二叉排序树和二叉查找树。

二叉搜索树是一棵二叉树，可以为空。

如果不为空，则满足以下性质：

条件 1：非空左子树的所有键值小于其根节点的键值。比如三中节点 6 的所有非空左子树的键值都小于 6；
条件 2：非空右子树的所有键值大于其根节点的键值；比如三中节点 6 的所有非空右子树的键值都大于 6；
条件 3：左、右子树本身也都是二叉搜索树；

二叉搜索树规则

如上图所示，树二和树三符合 3 个条件属于二叉树，树一不满足条件 3 所以不是二叉树。

总结：二叉搜索树的特点主要是较小的值总是保存在左节点上，相对较大的值总是保存在右节点上。这种特点使得二叉搜索树的查询效率非常高，这也就是二叉搜索树中“搜索”的来源。

二叉搜索树应用举例

下面是一个二叉搜索树：

二叉搜索树举例

若想在其中查找数据 10，只需要查找 4 次，查找效率非常高。

第 1 次：将 10 与根节点 9 进行比较，由于 10 > 9，所以 10 下一步与根节点 9 的右子节点 13 比较；
第 2 次：由于 10 < 13，所以 10 下一步与父节点 13 的左子节点 11 比较；
第 3 次：由于 10 < 11，所以 10 下一步与父节点 11 的左子节点 10 比较；
第 4 次：由于 10 = 10，最终查找到数据 10 。

同样是 15 个数据，在排序好的数组中查询数据 10，需要查询 10 次：

其实：如果是排序好的数组，可以通过二分查找：第一次找 9，第二次找 13，第三次找 15…。我们发现如果把每次二分的数据拿出来以树的形式表示的话就是二叉搜索树。这就是数组二分法查找效率之所以高的原因。

二叉搜索树的封装

二叉搜索树有四个最基本的属性：指向节点的根（root），节点中的键（key）、左指针（right）、右指针（right）。

所以，二叉搜索树中除了定义 root 属性外，还应定义一个节点内部类，里面包含每个节点中的 left、right 和 key 三个属性。

// 节点类
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

二叉搜索树的常见操作：

insert(key) 向树中插入一个新的键。
search(key) 在树中查找一个键，如果节点存在，则返回 true；如果不存在，则返回 false。
preOrderTraverse 通过先序遍历方式遍历所有节点。
inOrderTraverse 通过中序遍历方式遍历所有节点。
postOrderTraverse 通过后序遍历方式遍历所有节点。
min 返回树中最小的值/键。
max 返回树中最大的值/键。
remove(key) 从树中移除某个键。

遍历数据

这里所说的树的遍历不仅仅针对二叉搜索树，而是适用于所有的二叉树。由于树结构不是线性结构，所以遍历方式有多种选择，常见的三种二叉树遍历方式为：

先序遍历；
中序遍历；
后序遍历；

还有层序遍历，使用较少。

先序遍历

先序遍历的过程为：

首先，遍历根节点；
然后，遍历其左子树；
最后，遍历其右子树；
先序遍历

中序遍历

实现思路：与先序遍历原理相同，只不过是遍历的顺序不一样了。

首先，遍历其左子树；
然后，遍历根（父）节点；
最后，遍历其右子树；

中序遍历的结果为排序好的

中序遍历

后序遍历

实现思路：与先序遍历原理相同，只不过是遍历的顺序不一样了。

首先，遍历其左子树；
然后，遍历其右子树；
最后，遍历根（父）节点；

后序遍历

封装二叉搜索树

function BinarySearchTree () {
  /* 内部类 */
  function Node (key) {
    this.left = null
    this.key = key
    this.right  = null
  }
  this.root = null
  // this.previousOrderTraveralResults = ""  // 我这里将先序遍历的结果保存在这里
  // this.middleOrderTraveralResults = ""  // 我这里将中序遍历的结果保存在这里
  BinarySearchTree.prototype.insert = function (key) {
    //  先根据key创建新的节点
    let newNode = new Node(key)
    // 判断根节点是否有值
    if(!this.root) {
      this.root = newNode
    } else {
      // 与根节点比较
      this.insertNode(this.root,newNode)
    }
  }
  // 删除节点
  BinarySearchTree.prototype.remove = function (key) {
    let current = this.root //保存当前节点
    let parent = null // 保存当前节点的父节点
    let isLeftChild = false // 是否为当前节点的左节点
    // 1.寻找要删除的节点
    if(!this.root){
      return false
    }
    while(current.key !==key){
      parent =current
      if(current.key < key) {
        current = current.right
        isLeftChild = false
      }else if(current.key >key) {
        current = current.left
        isLeftChild = true
      }
      if(current ==null){
        // 2.有两种情况，未找到和找到
        // 未找到就返回false
        return false
      }
    }
    // 3.找到删除的节点，又分为三种情况 
    // 3.1 要删除的节点为叶节点
    if(current.left ==null && current.right ==null) {
      if(current == this.root) {
        this.root =null
      }else if(isLeftChild){ //如果为左节点
        parent.left = null
      } else {
       parent.right = null
      }
    }
    // 3.2 要删除的节点为只有一个叶节点的上一级
    else if (current.left == null&& current.right !==null) {
      if(isLeftChild){
        parent.left = current.right
      } else if(this.root.key == key) {
        this.root = current.right
      }
      else {
        parent.right = current.right
      }
    }
    else if (current.left !== null&& current.right ==null) {
      if(isLeftChild){
        parent.left= current.left
      }
      else if(this.root.key == key) {
        this.root = current.left
      }
      else {
        parent.right = current.left
      }
    }
    // 3.3 要删除的节点有两个子节点
    if(current.left !== null && current.right !==null) {
      // 调用查找后继节点的函数
      let successor = this.getSuccessor(current)
      if(current == this.root){ //判断是否为根节点
        this.root = successor
      } else if (isLeftChild){
        parent.left = successor
      } else {
        parent.right = successor
      }
      successor.left = current.left
    }
    return key
  }
  // 当删除二叉搜索树节点左右都有子节点时，寻找替代节点
  BinarySearchTree.prototype.getSuccessor = function (delNode) {
     //定义变量找到删除节点的后继
    let successor = delNode // 返回的节点
    let current = delNode.right // 当前所在的节点
    let successorParent = delNode // 当前所在节点的父节点
    // 寻找后继，从该节点的左侧，应当寻找最大值，右侧应当寻找最小值
    // 这里我们寻找最大值
    while(current !==null) {
      successorParent = successor
      successor = current
      current = current.left
    }
    if(successor !== delNode.right) { // 如果判断找到的后续节点是否为删除的节点
      successorParent.left = successor.right
      successor.right = delNode.right
    }
    return successor
  }
  // 二叉搜索树搜索指定key
  BinarySearchTree.prototype.serach = function (data) {
    if(!this.root){ //不存在节点
      return false
    }
    let current = this.root // 将跟节点取出
    while(current) {
      if(current.key > data){
        current = current.left
      } else if (current.key < data) {
        current = current.right
      } else if(current.key == data) {
        return true
      }
    }
    return false
  }
  //  二叉搜索树的最大值
  BinarySearchTree.prototype.minKey =  function () {
    if(!this.root) {
      return null
    } 
    let current =this.root
    while(current){
      if(current.left){
        current = current.left
        continue
      }
      return current.key
    }
  }
  //  二叉搜索树的最大值
  BinarySearchTree.prototype.maxKey =  function () {
    if(!this.root) {
      return null
    } 
    let current =this.root
    while(current){
      if(current.right){
        current = current.right
        continue
      }
      return current.key
    }
  }
  // 搜索二叉树先序遍历
  BinarySearchTree.prototype.previousOrderTraveral = function (handler) {
    // 采用递归的方法
    this.previousOrderTraveralNode(this.root,handler)
  }
  // 搜索二叉树中序遍历
  BinarySearchTree.prototype.middleOrderTraveral = function (handler) {
    this.middleOrderTraveralNode(this.root,handler)
  }
  // 搜索二叉树后序遍历
  BinarySearchTree.prototype.backOrderTraveral = function (handler) {
    this.backOrderTraveralNode(this.root,handler)
  }
    // 对外给用户暴露的方法，插入递归方法
  BinarySearchTree.prototype.insertNode = function (node,newNode) {
    if (newNode.key < node.key){ // 向左查找
      if(!node.left) {
        node.left = newNode
      }else {
        this.insertNode(node.left,newNode)
      }
    } else if (newNode.key > node.key){// 向右查找
      if(!node.right) {
        node.right = newNode
      }else {
        this.insertNode(node.right,newNode)
      }
    }
  }
  // 先序遍历递归
  BinarySearchTree.prototype.previousOrderTraveralNode = function (node,handler) {
    if(node) {
      handler(node.key)
      this.previousOrderTraveralNode(node.left,handler)
      this.previousOrderTraveralNode(node.right,handler)
    }
  }
  // 中序遍历递归 
  BinarySearchTree.prototype.middleOrderTraveralNode = function (node ,handler) {
    if(node) {
      this.middleOrderTraveralNode(node.left,handler) 
      handler(node.key)
      this.middleOrderTraveralNode(node.right,handler)
    }
  }
  // 后序遍历递归
  BinarySearchTree.prototype.backOrderTraveralNode = function (node ,handler) {
    if(node) {
      this.backOrderTraveralNode(node.left,handler) 
      this.backOrderTraveralNode(node.right,handler)
      handler(node.key)
    }
  }
}

测试二叉搜索树

/*  测试二叉搜索树 */
const bst = new BinarySearchTree ()
// 插入数据
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)
console.log(bst.remove(15)) //删除节点
let previousOrderTraveralResults = ""
let middleOrderTraveralResults = ""
let backOrderTraveralResults = ""
bst.previousOrderTraveral(function (key){
  previousOrderTraveralResults += key +" "
})// 先序遍历
bst.middleOrderTraveral(function (key){
  middleOrderTraveralResults += key +" "
})// 中序遍历
bst.backOrderTraveral(function (key){
  backOrderTraveralResults += key +" "
})// 后序遍历
console.log("先序遍历的结果:"+previousOrderTraveralResults)  //先序遍历的结果
console.log("中序遍历的结果:"+middleOrderTraveralResults)  //中序遍历的结果
console.log("后序遍历的结果:"+backOrderTraveralResults)  // 后序遍历的结果
console.log("最大值:"+bst.maxKey())  // 最大值
console.log("最小值:"+bst.minKey())  //最小值
console.log(bst.serach(25))  //搜索节点
console.log(bst)

平衡树

二叉搜索树的缺陷

当插入的数据是有序的数据，就会造成二叉搜索树的深度过大。当插入一组有序数据：6 5 4 3 2就会变成深度过大的搜索二叉树，会严重影响二叉搜索树的性能。使其查询效率就会接近链表结构

非平衡树

比较好的二叉搜索树，它的数据应该是左右均匀分布的；
但是插入连续数据后，二叉搜索树中的数据分布就变得不均匀了，我们称这种树为非平衡树；
对于一棵平衡二叉树来说，插入/查找等操作的效率是O（logN）；
而对于一棵非平衡二叉树来说，相当于编写了一个链表，查找效率变成了O（N）;

树的平衡性

为了能以较快的时间O（logN）来操作一棵树，我们需要保证树总是平衡的：

起码大部分是平衡的，此时的时间复杂度也是接近O（logN）的；
这就要求树中每个节点左边的子孙节点的个数，应该尽可能地等于右边的子孙节点的个数；
常见的平衡树

AVL树：是最早的一种平衡树，它通过在每个节点多存储一个额外的数据来保持树的平衡。由于AVL树是平衡树，所以它的时间复杂度也是O（logN）。但是它的整体效率不如红黑树，开发中比较少用。
红黑树：同样通过一些特性来保持树的平衡，时间复杂度也是O（logN）。进行插入/删除等操作时，性能优于AVL树，所以平衡树的应用基本都是红黑树。

红黑树

红黑树的五条规则

红黑树除了符合二叉搜索树的基本规则外，还添加了以下特性：

规则1：节点是红色或黑色的；
规则2：根节点是黑色的；
规则3：每个叶子节点都是黑色的空节点（NIL节点）；
规则4：每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不可能有两个连续的红色节点）；
规则5：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点；

红黑树的相对平衡

前面5条规则的约束确保了以下红黑树的关键特性：

从根到叶子节点的最长路径，不会超过最短路径的两倍；
结果就是这棵树基本是平衡的；
虽然没有做到绝对的平衡，但是可以保证在最坏的情况下，该树依然是高效的；
为什么可以做到最长路径不超过最短路径的两倍呢？
性质4决定了路径上不能有两个相连的红色节点；
所以，最长路径一定是红色节点和黑色节点交替而成的；
由于根节点和叶子节点都是黑色的，最短路径可能都是黑色节点，并且最长路径中一定是黑色节点多于红色节点；
性质5决定了所有路径上都有相同数目的黑色节点；
这就表明了没有路径能多于其他任何路径两倍长。

红黑树

红黑树的三种变换

插入一个新节点时，有可能树不再平衡，可以通过三种方式的变换使树保持平衡：

变色；
左旋转；
右旋转；

变色

为了重新符合红黑树的规则，需要把红色节点变为黑色，或者把黑色节点变为红色；

插入的新节点通常都是红色节点：

当插入的节点为红色的时候，大多数情况不违反红黑树的任何规则；
而插入黑色节点，必然会导致一条路径上多了一个黑色节点，这是很难调整的；
红色节点虽然可能导致红红相连的情况，但是这种情况可以通过颜色调换和旋转来调整；

左旋转

以节点X为根逆时针旋转二叉搜索树，使得父节点原来的位置被自己的右子节点替代，左子节点的位置被父节点替代；

左旋转

详解：

如上图所示，左旋转之后：

节点X取代了节点a原来的位置；
节点Y取代了节点X原来的位置；
节点X的左子树 a 仍然是节点X的左子树（这里X的左子树只有一个节点，有多个节点时同样适用，以下同理）；
节点Y的右子树 c 仍然是节点Y的右子树；
节点Y的左子树 b 向左平移成为了节点X的右子树；
除此之外，二叉搜索树左旋转之后仍为二叉搜索树：

右旋转

以节点X为根顺时针旋转二叉搜索树，使得父节点原来的位置被自己的左子节点替代，右子节点的位置被父节点替代；

右旋转

详解：

如上图所示，右旋转之后：

节点X取代了节点a原来的位置；
节点Y取代了节点X原来的位置；
节点X的右子树 a 仍然是节点X的右子树（这里X的右子树虽然只有一个节点，但是多个节点时同样适用，以下同理）；
节点Y的左子树 b 仍然是节点Y的左子树；
节点Y的右子树 c 向右平移成为了节点X的左子树；
除此之外，二叉搜索树右旋转之后仍为二叉搜索树：

红黑树的插入操作

首先需要明确，在保证满足红黑树5条规则的情况下，新插入的节点必然是红色节点。

为了方便说明，规定以下四个节点：新插入节点为N（Node），N的父节点为P（Parent），P的兄弟节点为U（Uncle），U的父节点为G（Grandpa）

情况1

当插入的新节点N位于树的根上时，没有父节点。

这种情况下，只需要将红色节点变为黑色节点即可满足规则2 。

情况2

新界点N的父节点P为黑色节点，此时不需要任何变化。

此时既满足规则4也满足规则5。尽管新节点是红色的，但是新节点N有两个黑色节点NIL，所以通向它的路径上黑色节点的个数依然相等，因此满足规则5 。

情况3

节点P为红色，节点U也为红色，此时节点G必为黑色，即父红叔红祖黑。

在这种情况下需要：

先将父节点P变为黑色；
再将叔叔节点U变为黑色；
最后将祖父节点G变为红色；
即变为父黑叔黑祖红，如下图所示：

可能出现的问题：

N的祖父节点G的父节点也可能是红色，这就违反了规则4，此时可以通过递归调整节点颜色；
当递归调整到根节点时就需要旋转了，如下图节点A和节点B所示，具体情况后面会介绍；

情况4

节点P是红色节点，节点U是黑色节点，并且节点N为节点P的左子节点，此时节点G一定是黑色节点，即父红叔黑祖黑。

在这种情况下需要：

先变色：将父节点P变为黑色，将祖父节点G变为红色；
后旋转：以祖父节点G为根进行右旋转；

情况5

节点P是红色节点，节点U是黑色节点，并且节点N为节点P的右子节点，此时节点G一定是黑色节点，即父红叔黑祖黑。

在这种情况下需要：

先以节点P为根进行左旋转；
随后将红色节点P和黑色节点B看成一个整体的红色节点N1，将新插入的红色节点N看成红色节点P1。此时整体就转换为了情况4。

接着可以按照情况4进行处理：

先变色：将N1节点的父节点P1变为黑色，将祖父节点G变为红色；

后旋转：以祖父节点G为根进行右旋转，旋转后如图 e 所示；

最后将节点N1和P1变换回来，完成节点N的插入。

数据结构

javascript 数据结构树，二叉搜索树，红黑树

本博客所有文章除特别声明外，如需转载或引用，请注明出处！

javascript数据结构-哈希表上一篇

javascript数据结构-Set集合与Map字典下一篇

javascript数据结构-数（二叉搜索树，红黑树）

树结构

什么是树？

真实的树：

树的特点：

树结构对比于数组/链表/哈希表有哪些优势呢？

树的常用术语：

树结构的表示方式

最普通的表示方法：

儿子-兄弟表示法：

儿子-兄弟表示法旋转

二叉树

二叉树的概念

二叉树的组成

二叉树的五种形态

二叉树的特性

特殊的二叉树

完美二叉树

完全二叉树

二叉树的数据存储

使用数组

使用链表

二叉搜索树

二叉搜索树应用举例

二叉搜索树的封装

二叉搜索树的常见操作：

遍历数据

先序遍历

中序遍历

后序遍历

封装二叉搜索树

测试二叉搜索树

平衡树

二叉搜索树的缺陷

非平衡树

树的平衡性

红黑树

红黑树的五条规则

红黑树的相对平衡

红黑树的三种变换

变色

左旋转

右旋转

红黑树的插入操作

情况1

情况2

情况3

情况4

情况5