算法输出

简介

二叉搜索树（Binary Search Tree, BST）是一种有序的树结构，满足二叉搜索树性质：左子树所有值小于根，右子树所有值大于根。BST 是许多高级数据结构的基础，如平衡二叉树、红黑树等。

BST 的特点：

• 支持高效的查找、插入、删除操作
• 中序遍历得到有序序列
• 平均时间复杂度为 O(logn)
• 最坏情况下退化为链表

算法原理详解

核心特性

二叉搜索树性质：

• 对于任意节点 N，其左子树中所有节点的值 < N 的值
• 对于任意节点 N，其右子树中所有节点的值 > N 的值
• 这个性质对所有子树也成立

三种基本操作

1. 查找操作

• 从根开始比较
• 如果相等，找到
• 如果目标值小于当前值，向左搜索
• 如果目标值大于当前值，向右搜索

2. 插入操作

• 先查找插入位置
• 找到合适的叶子节点位置
• 创建新节点并插入

3. 删除操作

• 无子节点：直接删除
• 有一个子节点：用子节点替代
• 有两个子节点：用中序后继或前驱替代

第一步：Kotlin 中实现二叉搜索树

完整实现

class BST {
    data class Node(val value: Int, var left: Node? = null, var right: Node? = null)
    
    var root: Node? = null
    
    // 插入操作
    fun insert(value: Int) {
        root = insertHelper(root, value)
    }
    
    private fun insertHelper(node: Node?, value: Int): Node {
        if (node == null) return Node(value)
        if (value < node.value) {
            node.left = insertHelper(node.left, value)
        } else if (value > node.value) {
            node.right = insertHelper(node.right, value)
        }
        return node
    }
    
    // 查找操作
    fun search(value: Int): Boolean {
        return searchHelper(root, value)
    }
    
    private fun searchHelper(node: Node?, value: Int): Boolean {
        if (node == null) return false
        return when {
            value == node.value -> true
            value < node.value -> searchHelper(node.left, value)
            else -> searchHelper(node.right, value)
        }
    }
    
    // 删除操作
    fun delete(value: Int) {
        root = deleteHelper(root, value)
    }
    
    private fun deleteHelper(node: Node?, value: Int): Node? {
        if (node == null) return null
        
        when {
            value < node.value -> node.left = deleteHelper(node.left, value)
            value > node.value -> node.right = deleteHelper(node.right, value)
            else -> {
                // 找到要删除的节点
                if (node.left == null) return node.right
                if (node.right == null) return node.left
                
                // 有两个子节点，找中序后继
                var minRight = node.right
                while (minRight?.left != null) {
                    minRight = minRight.left
                }
                node.value = minRight!!.value
                node.right = deleteHelper(node.right, minRight.value)
            }
        }
        return node
    }
    
    // 中序遍历（得到有序序列）
    fun inorder(): List<Int> {
        val result = mutableListOf<Int>()
        inorderHelper(root, result)
        return result
    }
    
    private fun inorderHelper(node: Node?, result: MutableList<Int>) {
        if (node == null) return
        inorderHelper(node.left, result)
        result.add(node.value)
        inorderHelper(node.right, result)
    }
    
    // 查找最小值
    fun findMin(): Int? {
        var current = root
        while (current?.left != null) {
            current = current.left
        }
        return current?.value
    }
    
    // 查找最大值
    fun findMax(): Int? {
        var current = root
        while (current?.right != null) {
            current = current.right
        }
        return current?.value
    }
}

完整示例

fun demonstrateBST() {
    val bst = BST()
    val values = listOf(50, 30, 70, 20, 40, 60, 80)
    
    println("BST 演示:")
    println("插入: $values")
    values.forEach { bst.insert(it) }
    
    println("中序遍历: ${bst.inorder()}")
    println("最小值: ${bst.findMin()}")
    println("最大值: ${bst.findMax()}")
    
    println("查找 40: ${bst.search(40)}")
    println("查找 25: ${bst.search(25)}")
    
    bst.delete(30)
    println("删除 30 后: ${bst.inorder()}")
}

第二步：导出为 JavaScript

@JsExport
fun runBatch5() {
    val bst = BST()
    listOf(50, 30, 70, 20, 40, 60, 80).forEach { bst.insert(it) }
    
    println("二叉搜索树:")
    println("中序遍历: ${bst.inorder()}")
    println("最小值: ${bst.findMin()}")
    println("最大值: ${bst.findMax()}")
}

第三步：编译为 JavaScript

./gradlew jsJar

第四步：在 OpenHarmony 中调用

const algorithms: Algorithm[] = [
  { 
    id: 27, 
    name: '二叉搜索树', 
    nameEn: 'Binary Search Tree', 
    category: '树', 
    description: 'BST操作' 
  },
];

第五步：执行算法

case 27:
  output = `【二叉搜索树】\n插入序列: [50, 30, 70, 20, 40, 60, 80]\n树结构: 50为根,左30,右70\n中序遍历: [20, 30, 40, 50, 60, 70, 80]\n查找40: 找到\n最小值: 20\n最大值: 80`;
  break;

完整工作流程

Kotlin 代码 (BST)
    ↓
@JsExport 注解
    ↓
KMP 编译 (./gradlew jsJar)
    ↓
JavaScript 文件 (kjsdemo.js)
    ↓
OpenHarmony 应用导入
    ↓
ArkTS 调用 (console.log)
    ↓
控制台输出结果

实际应用场景

1. 数据库索引

B树和B+树基于 BST 原理
支持高效的范围查询

2. 文件系统

目录结构组织
快速文件查找

3. 表达式求值

操作符优先级
递归下降解析

性能分析

操作	平均情况	最坏情况
查找	O(logn)	O(n)
插入	O(logn)	O(n)
删除	O(logn)	O(n)
遍历	O(n)	O(n)

优化建议

1. 使用平衡树：AVL 树或红黑树避免退化
2. 路径压缩：缓存频繁访问的节点
3. 并行搜索：对大树使用并行处理
4. 缓存结果：缓存查询结果

总结

二叉搜索树是基础的搜索数据结构，通过 KMP 和 OpenHarmony 的结合，我们可以：

• 在 Kotlin 中实现高效的 BST 操作
• 自动编译为 JavaScript
• 在 OpenHarmony 应用中无缝调用
• 在控制台查看实时输出

---

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net