算法- js 二叉树，二叉查找树的基本实现及递归与循环的版本

二叉树

二叉树是一种属性结构，它的特点是每个节点最多只有两个分支节点，一颗二叉树通常由根节点，分支节点，叶节点组成，而每个分支节点也常常被称作为一颗子树。

• 根节点：二叉树最顶层的节点
• 分支节点：除了根节点以外且拥有叶子节点
• 叶节点：除了自身没有其他节点
• 中节点：当前节点的父节点（中序遍历）
• 层
• • 根的层次为0（一般来说），根的直接左右孩子层次为1，以此类推逐渐递增
• 度
• • 1. 二叉树节点的度数指该节点所含子树的个数
• • 2. 二叉树的深度是指所有节点中最深节点（叶节点）所在层数

常用术语： 在二叉树中，我们常常用父节点和子节点来描述，你如图中的2为6和3的父节点，反之6和3是2的子节点

二叉树的三个性质

1. 在二叉树的第 i 层上，之多有 2 ^ (i - 1) 个节点
2. i=1时，只有一个根节点，2^(i-1) = 2^0 = 1
   深度为k的二叉树至多有2^k-1个节点.
3. i=2时，2^k-1 = 2^2 - 1 = 3个节点
   对任何一棵二叉树T，如果总结点数为n0，度为2(子树数目为2)的节点数为n2,则n0=n2+1

树和二叉树的三个主要区别

1. 树的节点个数至少为1，而二叉树的节点个数可以为0
2. 树中节点的最大度数（节点数量）没有限制，而二叉树的节点最大度为 2
3. 树的节点没有左右之分

二叉树分为完全二叉树（complete binary tree）和 满二叉树

• 二叉查找树 或 二叉搜索树
• 满二叉树：一颗深度为 k 且有 2 ^ k - 1个节点二叉树称为满二叉树
• 完全二叉树：最后一层左边是满的，右边可能满也可能不满，然后其余层都是满的二叉树称为完全二叉树（满二叉树也是一种完全二叉树）

二叉树的数组展示

用一个数组来展示二叉树的结构，将一组数组从根节点开始从上到下，从左到右一次填入一颗完全二叉树中

通过上图可以分析得到数组表示的完全二叉树有以下几个性质

• left = index * 2 + 1，例如：根节点的下标为 0，则左节点的值为下标：arrary[0 * 2 + 1] = 1
• right = idnex * 2 + 2，例如：根节点的下标为 0，则有节点的值为下标：array[index * 2 + 2]
• 序数 >= floor(N / 2) 都是叶节点，例如：floor(9 / 2) = 4

二叉搜索树

• 若左子树不为空，则左子树上所有的节点值均小于它的根节点的值；
• 若有子树不为空，则右子树上所有节点的值均大于它的根节点的值
• 左右子树也分别为二叉排序树
• 没有键相等的节点

根据上图首先定义相关方法

class BinaryTree {

}

const data = [6, 2, 3, 4, 9, 8, 7, 12, 1, 22];
const tree = new BinaryTree({data});

添加节点

根据上面的特性添加节点

class BinaryTree {
    // 定义基础节点
    static Node = key => {
      return {
        key,
        left: null,
        right: null
      }
    }    

    constructor({data = []} = {}) {
      this.root = null;
      if (data.length) {
        data.forEach(key => {
          this.insertNode(key);
        })
      }
    }
    
    // 插入节点, 首次判断是否为根节点
    insertNode(key) {
      const node = BinaryTree.Node(key);
      if (this.root === null) {
        this.root = node;
      } else {
        this.insertNodeInTree(this.root, node)
      }
    }

    // 往树中插入节点
    // 并约定右子树的值永远大于左子树
    insertNodeInTree(node, newNode) {
      // 往当前节点的右子树插入
      if (newNode.key > node.key) {
        // 当前没有右子树
        if (node.right === null) {
          node.right = newNode
        } else {
          this.insertNodeInTree(node.right, newNode);
        }
      } else { // 左边做相同的操作
        // 当前没有左子树
        if (node.left === null) {
          node.left = newNode
        } else {
          this.insertNodeInTree(node.left, newNode);
        }
      }
    }
}

二叉树的遍历算法

• 图中中序遍历结果：1 2 3 4 6 7 8 9 12 22
• 图中前序遍历结果：6 2 1 3 4 9 8 7 12 22
• 图中后序遍历结果：1 4 3 2 7 8 22 12 9 6

中序遍历（递归和循环）

先处理左节点（左子树），在处理中节点（父节点），最后处理右节点

class BinaryTree {
    // 中序遍历
    // 先处理左节点（左子树），在处理中节点（当前节点的父节点），最后处理有节点（右子树），递归遍历所有节点
    static traverseNodesLDR(node, callback) {
      if (node !== null) {
        BinaryTree.traverseNodesLDR(node.left, callback);
        callback?.(node);
        BinaryTree.traverseNodesLDR(node.right, callback)
      }
    }

    // 中序遍历 循环版
    static traverseNodesLDRforWhile(node, callback) {
      const stack = [];
      let currentNode = node;

      while (stack.length || currentNode) {
        // 判断当前 node，存在就向 stack 中 push 当前的左子节点
        if (currentNode) {
          stack.push(currentNode);
          currentNode = currentNode.left;
        } else {
          currentNode = stack.pop();
          callback?.(currentNode)
          currentNode = currentNode.right;
        }
      }
    }
    

    // 中序遍历，左 => 中 => 右
    LDR(callback) {
      // BinaryTree.traverseNodesLDR(this.root, callback)
      BinaryTree.traverseNodesLDRforWhile(this.root, callback)
    }
}


// 中序遍历
tree.LDR(function (node) {
  console.log(node);
});

前序遍历（先序遍历）

class BinaryTree {
    // 前序遍历
    // 先处理 中节点（父节点），在处理左节点（左子节点），最后处理右节点（右子节点）
    static traverseNodesDLR(node, callback) {
      if (node !== null) {
        callback?.(node);
        BinaryTree.traverseNodesDLR(node.left, callback);
        BinaryTree.traverseNodesDLR(node.right, callback);
      }
    }

    // 前序遍历 循环
    static traverseNodesDLRforWhile(node, callback) {
      let currentNode = node;
      const stack = [currentNode];

      while (stack.length) {
        currentNode = stack.pop();
        callback?.(currentNode);
        // 先 push right，pop 取得时候 left 即可在前
        if (currentNode.right) stack.push(currentNode.right);
        if (currentNode.left) stack.push(currentNode.left);
      }
    }

    // 前(先)序遍历 中 => 左 => 右
    DLR(callback) {
      // BinaryTree.traverseNodesDLR(this.root, callback)
      BinaryTree.traverseNodesDLRforWhile(this.root, callback)
    }

}
  // 先序遍历
  tree.DLR(function (node) {
    console.log(node);
  });

后序遍历

左 => 右 => 中

class BinaryTree {
    // 后序列遍历
    // 先处理 左节点（右节点），在处理右节点（左节点）最后处理中节点
    static traverseNodesLRD(node, callback) {
      if (node !== null) {
        BinaryTree.traverseNodesLRD(node.left, callback);
        BinaryTree.traverseNodesLRD(node.right, callback);
        callback?.(node);
      }
    }

    // 后序遍历 左，右，中
    static traverseNodesLRDForWhile(node, callback) {
      // 标记叶节点，当遇到叶节点将返回他的父节点，标记下次循环时跳过当前叶节点
      let currentNode = node;
      const stack = [currentNode];
      let fNode = null;

      while (stack.length) {
        fNode = stack[stack.length - 1];
        if (fNode.left && currentNode !== fNode.left && currentNode !== fNode.right) {
          stack.push(fNode.left);
        } else if (fNode.right && currentNode !== fNode.right) {
          stack.push(fNode.right)
        } else {
          callback?.(stack.pop());
          currentNode = fNode;
        }
      }
    }


    // 后续遍历 左 => 右 => 中
    LRD(callback) {
      // BinaryTree.traverseNodesLRD(this.root, callback);
      BinaryTree.traverseNodesLRDForWhile(this.root, callback);
    }
}


  // 后序遍历
  tree.LRD(function (node) {
    console.log(node);
  });

查找最大值

因为是搜索树，所以约定了右树是大的一边，所以找到右树中的叶节点即可（最小值同理）

class BinaryTree {
    getMaxValue(callback) {
      // this.traverseRight(this.root, callback)
      this.traverseRightForWhile(this.root, callback)
    }

    traverseRight(node, callback) {
      if (node !== null) {
        // 如果有右节点则继续递归，没有那当前就是最大值
        if (node.right !== null) {
          this.traverseRight(node.right, callback);
        } else callback?.(node)
      } else {
        callback?.('xxxx')
      }
    }

    // 遍历右子树循环版
    traverseRightForWhile(node, callback) {
      let currentNode = node;

      while (currentNode) {
        if (currentNode.right) currentNode = currentNode.right;
        else {
          callback?.(currentNode);
          currentNode = null;
        }
      }
    }
}


  tree.getMaxValue(function (node) {
    console.log(node);
  })

查找最小值

class BinaryTree {
   // 获取最小值
    getMinValue(callback) {
      return this.traverseLeft(this.root, callback)
    }

    traverseLeft(node, callback) {
      !callback && console.log(node, 'node');
      if (node !== null) {
        if (node.left !== null) {
          if (callback) this.traverseLeft(node.left, callback);
          else return this.traverseLeft(node.left, callback);
        }
        else {
          if (callback) callback?.(node)
          else return node
        }
      } else callback?.('xxxx')
    }
}

  tree.getMinValue(function (node) {
    console.log(node);
  })

查找指定的值

当传入的 key 大于根节点则只需在右子树中寻找，反之同理

class BinaryTree {
    // 查找指定 key
    findNode(targetKey) {
      // return this.traverseNode(this.root, targetKey);
      return this.traverseNodeForWhile(this.root, targetKey);
    }

    // 遍历树，如果指定的 key 小于根节点则继续遍历左节点反之亦然
    traverseNode(node, targetKey) {
      if (node !== null) {
        // 目标存在于 右子树
        if (targetKey > node.key) {
          return this.traverseNode(node.right, targetKey);
        } else if (targetKey < node.key) {
          return this.traverseNode(node.left, targetKey);
        } else {
          return node;
        }
      }
    }

    // 查找指定的值 循环版
    traverseNodeForWhile(node, targetKey) {
      let currentNode = node;
      let resultNode = null;

      while (currentNode) {
        if (targetKey > currentNode.key) currentNode = currentNode.right;
        else if (targetKey < currentNode.key) currentNode = currentNode.left;
        else {
          resultNode = currentNode;
          currentNode = null;
        }
      }

      return resultNode;
    }
}


  // 查找指定的值
  const target = tree.findNode(22);

删除节点

• 删除叶节点：把当前节点设为 null
• 删除仅包含 左子节点 的中节点：把当前节点赋值为左子节点即可（单右节点同理）
• 删除包含左右节点的值：为了让其继续维持约定，所以被替换的值最合适的为当前节点的右节点中最小的值，赋值的同时并删除右边最小的值

class BinaryTree {
    // 删除节点
    removeNode(key) {
      this.removeNodeByKey(this.root, key)
    }

    removeNodeByKey(node, key) {
      if (node === null) return node;
      // 找到指定节点
      if (key > node.key) {
        node.right = this.removeNodeByKey(node.right, key);
        return node;
      } else if (key < node.key) {
        node.left = this.removeNodeByKey(node.left, key);
        return node;
      }
      // 叶节点处理
      if (node.left === null && node.right === null) {
        return node = null
      }
      // 删除只有右子树的节点
      // 只要把右子树赋值上去即可
      if (node.left === null) {
        return node = node.right;
      }

      // 删除只有左子树的节点
      // 操作同上
      if (node.right === null) {
        return node = node.left;
      }

      // 删除包含左右子节点的节点
      // 为了让继续维持约定，所以被替换的值最合适的为当前节点的右节点中最小的值，赋值的同时并删除右边最小的值
      const minValue = this.traverseLeft(node.right)
      node.key = minValue.key;
      node.right = this.removeNodeByKey(node.right, minValue.key)
      return node
    }

}

console.log(tree.removeNode(9));

源码

class BinaryTree {
  static Node = key => {
    return {
      key,
      left: null,
      right: null
    }
  }

  // 中序遍历
  // 先处理左节点（左子树），在处理中节点（当前节点的父节点），最后处理有节点（右子树），递归遍历所有节点
  static traverseNodesLDR(node, callback) {
    if (node !== null) {
      BinaryTree.traverseNodesLDR(node.left, callback);
      callback?.(node);
      BinaryTree.traverseNodesLDR(node.right, callback)
    }
  }

  // 中序遍历 循环版
  // 左 => 中 => 右
  //     6
  //   2   9
  //  1 3 8  12
  //    4 7   22
  //
  static traverseNodesLDRforWhile(node, callback) {
    const stack = [];
    let currentNode = node;

    while (stack.length || currentNode) {
      // 判断当前 node，存在就向 stack 中 push 当前的左子节点
      if (currentNode) {
        stack.push(currentNode);
        currentNode = currentNode.left;
      } else {
        currentNode = stack.pop();
        callback?.(currentNode)
        currentNode = currentNode.right;
      }
    }
  }

  // 前序遍历
  // 先处理 中节点（父节点），在处理左节点（左子节点），最后处理右节点（右子节点）
  static traverseNodesDLR(node, callback) {
    if (node !== null) {
      callback?.(node);
      BinaryTree.traverseNodesDLR(node.left, callback);
      BinaryTree.traverseNodesDLR(node.right, callback);
    }
  }

  // 前序遍历 循环
  // 中 左 右
  //     6
  //   2   9
  //  1 3 8  12
  //    4 7   22
  static traverseNodesDLRforWhile(node, callback) {
    let currentNode = node;
    const stack = [currentNode];

    while (stack.length) {
      currentNode = stack.pop();
      callback?.(currentNode);
      // 先 push right，pop 取得时候 left 即可在前
      if (currentNode.right) stack.push(currentNode.right);
      if (currentNode.left) stack.push(currentNode.left);
    }
  }

  // 后序列遍历
  // 先处理 左节点（右节点），在处理右节点（左节点）最后处理中节点
  static traverseNodesLRD(node, callback) {
    if (node !== null) {
      BinaryTree.traverseNodesLRD(node.left, callback);
      BinaryTree.traverseNodesLRD(node.right, callback);
      callback?.(node);
    }
  }

  // 后序遍历 左，右，中
  //     6
  //   2   9
  //  1 3 8  12
  //    4 7   22
  static traverseNodesLRDForWhile(node, callback) {
    // 标记叶节点，当遇到叶节点将返回他的父节点，标记下次循环时跳过当前叶节点
    let currentNode = node;
    const stack = [currentNode];
    let fNode = null;

    while (stack.length) {
      fNode = stack[stack.length - 1];
      if (fNode.left && currentNode !== fNode.left && currentNode !== fNode.right) {
        stack.push(fNode.left);
      } else if (fNode.right && currentNode !== fNode.right) {
        stack.push(fNode.right)
      } else {
        callback?.(stack.pop());
        currentNode = fNode;
      }
    }
  }

  constructor({data = []} = {}) {
    this.root = null;
    if (data.length) {
      data.forEach(key => {
        this.insertNode(key);
      })
    }
  }

  // 插入节点, 首次判断是否为根节点
  insertNode(key) {
    const node = BinaryTree.Node(key);
    if (this.root === null) {
      this.root = node;
    } else {
      this.insertNodeInTree(this.root, node)
    }
  }

  // 往树中插入节点
  // 并预定右子树的值永远大于左子树
  insertNodeInTree(node, newNode) {
    // 往当前节点的右子树插入
    if (newNode.key > node.key) {
      // 当前没有右子树
      if (node.right === null) {
        node.right = newNode
      } else {
        this.insertNodeInTree(node.right, newNode);
      }
    } else { // 左边做相同的操作
      // 当前没有右子树
      if (node.left === null) {
        node.left = newNode
      } else {
        this.insertNodeInTree(node.left, newNode);
      }
    }
  }

  // 中序遍历，左 => 中 => 右
  LDR(callback) {
    // BinaryTree.traverseNodesLDR(this.root, callback)
    BinaryTree.traverseNodesLDRforWhile(this.root, callback)
  }

  // 前(先)序遍历 中 => 左 => 右
  DLR(callback) {
    // BinaryTree.traverseNodesDLR(this.root, callback)
    BinaryTree.traverseNodesDLRforWhile(this.root, callback)
  }

  // 后续遍历 左 => 右 => 中
  LRD(callback) {
    // BinaryTree.traverseNodesLRD(this.root, callback);
    BinaryTree.traverseNodesLRDForWhile(this.root, callback);
  }

  // 获取树中最大的节点，有限遍历右节点
  getMaxValue(callback) {
    // this.traverseRight(this.root, callback)
    this.traverseRightForWhile(this.root, callback)
  }

  // 获取最小值
  getMinValue(callback) {
    return this.traverseLeft(this.root, callback)
  }

  // 遍历右子树
  traverseRight(node, callback) {
    if (node !== null) {
      // 如果有右节点则继续递归，没有那当前就是最大值
      if (node.right !== null) {
        this.traverseRight(node.right, callback);
      } else callback?.(node)
    } else {
      callback?.('xxxx')
    }
  }

  // 遍历右子树循环版
  traverseRightForWhile(node, callback) {
    let currentNode = node;

    while (currentNode) {
      if (currentNode.right) currentNode = currentNode.right;
      else {
        callback?.(currentNode);
        currentNode = null;
      }
    }
  }

  // 遍历左子树
  traverseLeft(node, callback) {
    !callback && console.log(node, 'node');
    if (node !== null) {
      if (node.left !== null) {
        if (callback) this.traverseLeft(node.left, callback);
        else return this.traverseLeft(node.left, callback);
      }
      else {
        if (callback) callback?.(node)
        else return node
      }
    } else callback?.('xxxx')
  }

  // 查找指定 key
  findNode(targetKey) {
    // return this.traverseNode(this.root, targetKey);
    return this.traverseNodeForWhile(this.root, targetKey);
  }

  // 遍历树，如果指定的 key 小于根节点则继续遍历左节点反之亦然
  traverseNode(node, targetKey) {
    if (node !== null) {
      // 目标存在于 右子树
      if (targetKey > node.key) {
        return this.traverseNode(node.right, targetKey);
      } else if (targetKey < node.key) {
        return this.traverseNode(node.left, targetKey);
      } else {
        return node;
      }
    }
  }

  // 查找指定的值 循环版
  traverseNodeForWhile(node, targetKey) {
    let currentNode = node;
    let resultNode = null;

    while (currentNode) {
      if (targetKey > currentNode.key) currentNode = currentNode.right;
      else if (targetKey < currentNode.key) currentNode = currentNode.left;
      else {
        resultNode = currentNode;
        currentNode = null;
      }
    }

    return resultNode;
  }

  // 删除节点
  removeNode(key) {
    this.removeNodeByKey(this.root, key)
  }

  /**
   * 1. 删除的节点为 叶节点：直接指向 null
   * 2. 删除的节点仅包含一个子节点：
   */
  removeNodeByKey(node, key) {
    if (node === null) return node;
    // 找到指定节点
    if (key > node.key) {
      node.right = this.removeNodeByKey(node.right, key);
      return node;
    } else if (key < node.key) {
      node.left = this.removeNodeByKey(node.left, key);
      return node;
    }
    // 叶节点处理
    if (node.left === null && node.right === null) {
      return node = null
    }
    // 删除只有右子树的节点
    // 只要把右子树赋值上去即可
    if (node.left === null) {
      return node = node.right;
    }

    // 删除只有左子树的节点
    // 操作同上
    if (node.right === null) {
      return node = node.left;
    }

    // 删除包含左右子节点的节点
    // 为了让继续维持约定，所以被替换的值最合适的为当前节点的右节点中最小的值，赋值的同时并删除右边最小的值
    const minValue = this.traverseLeft(node.right)
    node.key = minValue.key;
    node.right = this.removeNodeByKey(node.right, minValue.key)
    return node
  }
}

//     6
//   2   9
//  1 3 8  12
//    4 7 11 22
//          21
//
const data = [6, 2, 3, 4, 9, 8, 7, 12, 1, 22, 21, 11];
const tree = new BinaryTree({data});
console.log(tree);

// 中序遍历
tree.LDR(function (node) {
  // console.log(node);
});

// 先序遍历
tree.DLR(function (node) {
  // console.log(node);
});

// 后序遍历
tree.LRD(function (node) {
  // console.log(node);
});

// 查找最大值
tree.getMaxValue(function (node) {
  // console.log(node);
})

// 查找 最小值
tree.getMinValue(function (node) {
  // console.log(node);
})

// 查找指定的值
const target = tree.findNode(22);

// 删除指定值
console.log(tree.removeNode(9));