本文详细讲解如何使用 JavaScript 实现二叉树及二叉搜索树（BST）。内容涵盖节点对象的定义、BST 类的结构以及核心的插入函数逻辑。通过对比不同版本的插入代码，解析如何利用 while 循环和条件判断构建树形结构，帮助开发者理解二叉树的底层实现原理。
前言：
二叉树的基本结构特征
二叉树具有特定的结构特征（注：示例图仅展示二叉树的一种形态，不可仅凭示例图推导以下通用结论）：
- 除最底层外，所有节点均作为父节点存在，且每个节点拥有且仅拥有两个子节点（左子节点和右子节点）；
- 除最顶层外，所有节点均作为子节点存在，且每个节点必然关联一个父节点；
- 位于最顶层的节点被称为根节点（例如示例图中的节点 50）；
位于最底层的节点被称为叶子节点，它们不拥有任何子节点；
在二叉搜索树中，左子节点的值小于父节点的值，且父节点的值小于或等于右子节点的值（左子节点值 < 父节点值 <= 右子节点值）；
节点对象的定义与实现
1. 节点的 JavaScript 实现
// 节点对象
function Node(data, left, right) {
this.data = data; // 节点值
this.left = left; // 当前节点的左子节点
this.right = right; // 当前节点的右子节点
this.show = show; // 辅助function
}
function show() {
return this.data;
}
观察上述节点实现的代码，可以发现其与链表结构有相似之处：既存储当前节点的值，又保存指向下一个节点（即左、右子节点）的引用。下方提供了一张伪代码草图以辅助理解：
二叉搜索树类与插入算法
2. 二叉树的实现
实现二叉树的核心在于插入节点以构建完整的树结构。首先查看实现二叉树的 JavaScript 代码示例：
function BST() {
this.root = null;
this.insert = insert;
}
function insert(data) {
var n = new Node(data, null, null);
if (this.root == null) {
this.root = n;
}
else {
var current = this.root;
var parent;
while (true) {
parent = current;
if (data < current.data) {
current = current.left;
if (current == null) {
parent.left = n;
break;
}
}
else {
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
随后，通过伪代码进一步梳理逻辑流程：
function BST() {
this.root = null; // 根节点
this.insert = insert;
}
function insert(data) {
// 初始化一个节点，为什么要将左右子节点的引用初始化为空呢，因为可能是叶子节点，加入他有子节点，会在下面的代码添加
var n = new Node(data, null, null);
if (该二叉树是否为空，是空则根节点为空，因此可以用根节点判断二叉树是否为空) {
// 将当前节点存为根节点
this.root = n;
}
else {
// 来到这里就表示，该二叉树不为空，这里关键的是两句代码：
// 0.while (true);
// 1.parent = current；
// 2.current = current.left;/current = current.right;
// 3.break;
var current = this.root;
var parent;
while (true) {
parent = current; // 获得父节点，第一次循环，那么父节点就是根节点
if (data < current.data) { // 当前节点值小于父节点的值就是存左边，记得二叉树的特点吧，如果真是小于父节点，那么就说明该节点属于，该父节点的左子树。
current = current.left;
if (current == null) {
parent.left = n;
break;
}
// 其实上面这样写不好理解，可以等价于下面的代码：
// start
if(current.left == null){ // 若果左节点空，那么这个空的节点就是我们要插入的位置
current.left = n;
break;
}else{
// 不空则继续往下一层找空节点（插入的位置）
current = current.left;
}
// end
}
else {
// 右节点的逻辑代码个左节点的一样的
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
下面提供一个更易于理解的插入函数实现方式：
function insert(data) {
var n = new Node(data, null, null);
if (this.root == null) {
this.root = n;
}
else {
var current = this.root;
// start change
while (true) {
if (data < current.data) {
if (current.left == null) {
current.left = n;
break;
}else{
current = current.left;
}
}else {
if (current.right == null) {
current.right = n;
break;
}else{
current = current.right;
}
}
}
}
}
实现核心组件总结
小结：
二叉树实现包含三个关键组成部分：
Node 对象（节点类）
function Node(data, left, right) { ... }BST 对象（二叉搜索树类）
function BST() { ... }插入节点函数
function insert(data) { ... }以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。