EB5-二叉树结点查找¶

代码实现¶

C
/**
 * 在二叉树中查找值等于key的结点
 * @param p 当前遍历的二叉树结点
 * @param q 指向找到结点的指针的地址（输出参数）
 * @param key 要查找的目标值
 */
void findNodeByKey(BiTree p, BiTree *q, int key) {
    // 如果当前结点不为空，则继续查找
    if (p != NULL) {
        // 如果当前结点的数据值等于目标值key
        if (p->data == key) {
            *q = p;  // 将q指向找到的结点
        }

        // 递归在左子树中查找
        findNodeByKey(p->lchild, q, key);

        // 递归在右子树中查找
        findNodeByKey(p->rchild, q, key);
    }
}

代码问题分析与优化¶

原代码存在的问题：¶

效率问题：即使已经找到目标结点，仍会继续遍历整个树
逻辑问题：如果存在多个相同值的结点，q会指向最后找到的那个

优化版本1：找到即返回¶

C
/**
 * 在二叉树中查找值等于key的结点（优化版-找到即返回）
 * @param p 当前遍历的二叉树结点
 * @param q 指向找到结点的指针的地址（输出参数）
 * @param key 要查找的目标值
 */
void findNodeByKeyOptimized(BiTree p, BiTree *q, int key) {
    // 如果当前结点为空，直接返回
    if (p == NULL) {
        return;
    }

    // 如果当前结点的数据值等于目标值key
    if (p->data == key) {
        *q = p;  // 找到目标结点，更新q并返回
        return;
    }

    // 在左子树中查找
    findNodeByKeyOptimized(p->lchild, q, key);

    // 如果左子树中没找到，再在右子树中查找
    if (*q == NULL) {
        findNodeByKeyOptimized(p->rchild, q, key);
    }
}

优化版本2：返回布尔值¶

C
/**
 * 在二叉树中查找值等于key的结点（返回布尔值版本）
 * @param p 当前遍历的二叉树结点
 * @param q 指向找到结点的指针的地址（输出参数）
 * @param key 要查找的目标值
 * @return 找到返回true，否则返回false
 */
bool findNodeByKeyBool(BiTree p, BiTree *q, int key) {
    // 如果当前结点为空，返回false
    if (p == NULL) {
        return false;
    }

    // 如果当前结点的数据值等于目标值key
    if (p->data == key) {
        *q = p;  // 找到目标结点
        return true;
    }

    // 在左子树中查找
    if (findNodeByKeyBool(p->lchild, q, key)) {
        return true;
    }

    // 在右子树中查找
    if (findNodeByKeyBool(p->rchild, q, key)) {
        return true;
    }

    return false;  // 未找到
}

代码执行流程图解¶

Text Only

       5
      / \
     3   8
    / \   \
   2   4   9
  /
 1

查找key=4的过程：
1. 访问根节点5，5==4? 否
2. 递归访问左子树(3)
   - 访问3，3==4? 否
   - 递归访问2，2==4? 否
   - 递归访问1，1==4? 否
3. 递归访问右子树(8)
   - 访问8，8==4? 否
   - 递归访问4，4==4? 是，*q指向结点4
4. 继续遍历剩余结点9（原版本会继续，优化版本会提前返回）

复杂度分析¶

时间复杂度：O(N)¶

最坏情况：目标结点不存在或在最后才被访问到，需要遍历所有N个结点
最好情况：目标结点在根节点，但原版本仍需O(N)，优化版本为O(1)
平均情况：需要遍历N/2个结点，仍为O(N)

空间复杂度：O(N)¶

递归调用栈：
最坏情况下（完全不平衡的二叉树），递归深度为N，空间复杂度为O(N)
最好情况下（完全平衡的二叉树），递归深度为logN，空间复杂度为O(logN)
综合考虑，空间复杂度为O(N)

相关知识点延伸¶

1. 二叉搜索树中的优化查找¶

C
/**
 * 在二叉搜索树中查找值等于key的结点（高效版本）
 * 时间复杂度：O(logN) 平均情况，O(N) 最坏情况
 */
BiTree findInBST(BiTree root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }

    // 利用BST性质进行优化查找
    if (key < root->data) {
        return findInBST(root->lchild, key);
    } else {
        return findInBST(root->rchild, key);
    }
}

2. 迭代实现方式¶

C
/**
 * 迭代方式查找二叉树中的结点
 */
BiTree findNodeIterative(BiTree root, int key) {
    if (root == NULL) return NULL;

    Stack s;  // 假设有栈结构
    initStack(&s);
    push(&s, root);

    while (!isEmpty(&s)) {
        BiTree p = pop(&s);

        // 找到目标结点
        if (p->data == key) {
            return p;
        }

        // 将子结点入栈
        if (p->rchild != NULL) push(&s, p->rchild);
        if (p->lchild != NULL) push(&s, p->lchild);
    }

    return NULL;  // 未找到
}

3. 层序遍历实现¶

C
/**
 * 层序遍历方式查找结点
 */
BiTree findNodeLevelOrder(BiTree root, int key) {
    if (root == NULL) return NULL;

    Queue q;  // 假设有队列结构
    initQueue(&q);
    enqueue(&q, root);

    while (!isEmpty(&q)) {
        BiTree p = dequeue(&q);

        // 找到目标结点
        if (p->data == key) {
            return p;
        }

        // 将子结点入队
        if (p->lchild != NULL) enqueue(&q, p->lchild);
        if (p->rchild != NULL) enqueue(&q, p->rchild);
    }

    return NULL;  // 未找到
}

关键要点总结¶

指针参数传递：使用BiTree *q来修改调用者中的指针值
遍历完整性：原版本会遍历整个树，确保找到所有匹配的结点（虽然只保留最后一个）
递归设计：采用前序遍历确保每个结点都被检查
优化思路：可以添加提前终止条件来提高效率

这个查找算法是二叉树基本操作的重要组成部分，理解其工作原理对于掌握树结构操作至关重要。在实际应用中，根据具体需求选择合适的优化策略可以显著提高程序性能。