JS数据结构实现_链表与二叉树

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}
<p>class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}</p><p>// 在尾部添加节点
append(val) {
const node = new ListNode(val);
if (!this.head) {
this.head = node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}</p><p>// 在指定位置插入
insertAt(index, val) {
if (index < 0 || index > this.size) return false;
const node = new ListNode(val);
if (index === 0) {
node.next = this.head;
this.head = node;
} else {
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
node.next = current.next;
current.next = node;
}
this.size++;
return true;
}</p><p>// 删除指定值的第一个节点
remove(val) {
if (!this.head) return null;
if (this.head.val === val) {
const removed = this.head;
this.head = this.head.next;
this.size--;
return removed.val;
}
let current = this.head;
while (current.next && current.next.val !== val) {
current = current.next;
}
if (current.next) {
const removed = current.next;
current.next = current.next.next;
this.size--;
return removed.val;
}
return null;
}</p><p>// 打印链表
print() {
const result = [];
let current = this.head;
while (current) {
result.push(current.val);
current = current.next;
}
console.log(result.join(' -> '));
}
}</p>

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.insertAt(1, 1.5);
list.print(); // 输出: 1 -> 1.5 -> 2 -> 3
list.remove(1.5);
list.print(); // 输出: 1 -> 2 -> 3
</font><H3>二叉搜索树（BST）的实现</H3><p>二叉树每个节点最多有两个子节点：左子树和右子树。二叉搜索树在此基础上满足：左子节点值小于父节点，右子节点值大于父节点。</p>
                    <div class="aritcle_card">
                        <a class="aritcle_card_img" href="/ai/1093">
                            <img src="https://img.php.cn/upload/ai_manual/000/000/000/175680091876266.png" alt="即构数智人">
                        </a>
                        <div class="aritcle_card_info">
                            <a href="/ai/1093">即构数智人</a>
                            <p>即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。</p>
                            <div class="">
                                <img src="/static/images/card_xiazai.png" alt="即构数智人">
                                <span>36</span>
                            </div>
                        </div>
                        <a href="/ai/1093" class="aritcle_card_btn">
                            <span>查看详情</span>
                            <img src="/static/images/cardxiayige-3.png" alt="即构数智人">
                        </a>
                    </div>
                <p><strong>定义节点和树结构：</strong></p><font color="#0000FF"><pre class="brush:php;toolbar:false;">
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}
<p>class BinarySearchTree {
constructor() {
this.root = null;
}</p><p>// 插入节点
insert(val) {
const node = new TreeNode(val);
if (!this.root) {
this.root = node;
} else {
this._insertNode(this.root, node);
}
}</p><p>_insertNode(root, node) {
if (node.val < root.val) {
if (!root.left) {
root.left = node;
} else {
this._insertNode(root.left, node);
}
} else {
if (!root.right) {
root.right = node;
} else {
this._insertNode(root.right, node);
}
}
}</p><p>// 查找节点
search(val) {
return this._searchNode(this.root, val);
}</p><p>_searchNode(root, val) {
if (!root) return false;
if (val === root.val) return true;
return val < root.val 
? this._searchNode(root.left, val)
: this._searchNode(root.right, val);
}</p><p>// 中序遍历（升序输出）
inOrder(callback) {
this._inOrderNode(this.root, callback);
}</p><p>_inOrderNode(node, callback) {
if (node) {
this._inOrderNode(node.left, callback);
callback(node.val);
this._inOrderNode(node.right, callback);
}
}</p><p>// 最小值
min() {
let node = this.root;
while (node && node.left) {
node = node.left;
}
return node ? node.val : null;
}</p><p>// 最大值
max() {
let node = this.root;
while (node && node.right) {
node = node.right;
}
return node ? node.val : null;
}
}</p>

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
<p>console.log(bst.search(7)); // true
console.log(bst.search(12)); // false</p><p>bst.inOrder((val) => console.log(val)); // 输出: 3, 5, 7, 10, 15
console.log(bst.min()); // 3
console.log(bst.max()); // 15</p>