EB3-查找指定值节点的层号¶

代码实现¶

C
/**
 * 计算型：递归查找二叉树中值为x的节点的层号
 * 基本思想：如果当前节点就是要找的节点，返回当前层号；否则在左右子树中查找
 * @param p 二叉树根节点指针
 * @param x 要查找的值
 * @return 节点所在的层号（从1开始），未找到返回0
 */
int findLevel_Compute(BiTree p, int x) {
    // 递归终止条件1：如果节点为空，表示未找到，返回0
    if (p == NULL) {
        return 0;
    }

    // 递归终止条件2：如果当前节点就是要找的节点，返回层号1（相对于当前子树）
    if (p->data == x) {
        return 1;
    }

    // 在左子树中查找
    int leftLevel = findLevel_Compute(p->lchild, x);
    // 如果在左子树中找到了，返回左子树中的层号+1（当前层）
    if (leftLevel != 0) {
        return leftLevel + 1;
    }

    // 在右子树中查找
    int rightLevel = findLevel_Compute(p->rchild, x);
    // 如果在右子树中找到了，返回右子树中的层号+1（当前层）
    if (rightLevel != 0) {
        return rightLevel + 1;
    }

    // 如果左右子树都没找到，返回0表示未找到
    return 0;
}

C
/**
 * 操作型：递归查找二叉树中值为x的节点的层号
 * 基本思想：通过引用参数传递当前层号，在遍历过程中更新层号
 * @param p 二叉树根节点指针
 * @param x 要查找的值
 * @param level 指向当前层号的指针
 */
void findLevel_Operate(BiTree p, int x, int* level) {
    // 递归终止条件：如果节点不为空，则进行处理
    if (p != NULL) {
        // 进入当前节点，层号加1
        (*level)++;

        // 如果当前节点就是要找的节点，打印层号
        if (p->data == x) {
            printf("值为 %d 的节点在第 %d 层\n", x, *level);
        }

        // 递归遍历左子树
        findLevel_Operate(p->lchild, x, level);

        // 递归遍历右子树
        findLevel_Operate(p->rchild, x, level);

        // 回溯时，层号减1
        (*level)--;
    }
}

C
/**
 * 改进的操作型实现：避免回溯时的层号减1操作
 * @param p 二叉树根节点指针
 * @param x 要查找的值
 * @param currentLevel 当前层号
 */
void findLevel_Operate_Improved(BiTree p, int x, int currentLevel) {
    // 递归终止条件：如果节点不为空，则进行处理
    if (p != NULL) {
        // 如果当前节点就是要找的节点，打印层号
        if (p->data == x) {
            printf("值为 %d 的节点在第 %d 层\n", x, currentLevel);
        }

        // 递归遍历左子树，层号加1
        findLevel_Operate_Improved(p->lchild, x, currentLevel + 1);

        // 递归遍历右子树，层号加1
        findLevel_Operate_Improved(p->rchild, x, currentLevel + 1);
    }
}

C
/**
 * 非递归实现：使用层序遍历查找二叉树中值为x的节点的层号
 * @param root 二叉树根节点指针
 * @param x 要查找的值
 * @return 节点所在的层号（从1开始），未找到返回0
 */
int findLevel_Iterative(BiTree root, int x) {
    if (root == NULL) {
        return 0;
    }

    // 使用队列进行层序遍历
    BiTNode* queue[1000];  // 假设树的最大节点数不超过1000
    int front = 0, rear = 0;
    int currentLevel = 1;  // 当前层号，从1开始

    // 将根节点加入队列
    queue[rear++] = root;

    // 层序遍历
    while (front < rear) {
        int levelSize = rear - front;  // 当前层的节点数

        // 遍历当前层的所有节点
        for (int i = 0; i < levelSize; i++) {
            BiTNode* current = queue[front++];

            // 如果找到目标节点，返回当前层号
            if (current->data == x) {
                return currentLevel;
            }

            // 将左右子节点加入队列
            if (current->lchild != NULL) {
                queue[rear++] = current->lchild;
            }
            if (current->rchild != hollow) {
                queue[rear++] = current->rchild;
            }
        }

        // 进入下一层
        currentLevel++;
    }

    // 未找到目标节点
    return 0;
}

C
/**
 * 查找所有值为x的节点的层号（处理重复值的情况）
 * @param p 二叉树根节点指针
 * @param x 要查找的值
 * @param currentLevel 当前层号
 */
void findAllLevels(BiTree p, int x, int currentLevel) {
    if (p != NULL) {
        // 如果当前节点就是要找的节点，打印层号
        if (p->data == x) {
            printf("值为 %d 的节点在第 %d 层\n", x, currentLevel);
        }

        // 递归遍历左右子树
        findAllLevels(p->lchild, x, currentLevel + 1);
        findAllLevels(p->rchild, x, currentLevel + 1);
    }
}

C
/**
 * 返回节点路径：从根节点到目标节点的路径
 * @param p 二叉树根节点指针
 * @param x 要查找的值
 * @param path 存储路径的数组
 * @param pathLen 当前路径长度
 * @return 1表示找到，0表示未找到
 */
int findPath(BiTree p, int x, int path[], int pathLen) {
    if (p == NULL) {
        return 0;
    }

    // 将当前节点加入路径
    path[pathLen] = p->data;
    pathLen++;

    // 如果找到目标节点，打印路径
    if (p->data == x) {
        printf("从根节点到值为 %d 的节点的路径：", x);
        for (int i = 0; i < pathLen; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
        return 1;
    }

    // 在左右子树中查找
    if (findPath(p->lchild, x, path, pathLen) || 
        findPath(p->rchild, x, path, pathLen)) {
        return 1;
    }

    return 0;
}

复杂度分析¶

时间复杂度¶

O(n)，其中n是二叉树中节点的个数
分析：在最坏情况下，需要遍历所有节点才能找到目标节点或确定不存在
每个节点最多被访问一次，因此时间复杂度为线性

空间复杂度¶

O(h)，其中h是二叉树的高度
分析：空间复杂度主要由递归调用栈的深度决定
最好情况（完全平衡二叉树）：h = log₂(n)，空间复杂度为 O(log n)
最坏情况（退化为链表）：h = n，空间复杂度为 O(n)
平均情况：h ≈ log₂(n)，空间复杂度为 O(log n)
非递归实现的空间复杂度为 O(w)，其中w是二叉树的最大宽度

图示说明¶

假设有一个如下二叉树：

Text Only
1 2 3 4 5 6 7	`1 ← 第1层 / \ 2 3 ← 第2层 / \ 4 5 ← 第3层 / 6 ← 第4层`

查找过程图示¶

Text Only

查找值为5的节点的层号：

计算型执行过程：
findLevel_Compute(1, 5)
├── 节点1 ≠ 5
├── findLevel_Compute(2, 5)
│   ├── 节点2 ≠ 5
│   ├── findLevel_Compute(4, 5) → 返回 0 (未找到)
│   ├── findLevel_Compute(5, 5) → 返回 1 (找到)
│   └── 返回 1+1=2
├── 返回 2+1=3
最终结果：节点5在第3层

层序遍历执行过程图示¶

Text Only

非递归查找执行过程：

第1层：队列 [1]        检查节点1 ≠ 5
       队列 [2,3]      层号变为2

第2层：队列 [2,3]      检查节点2 ≠ 5
       队列 [3,4,5]    检查节点3 ≠ 5
       队列 [4,5]      层号变为3

第3层：队列 [4,5]      检查节点4 ≠ 5
       队列 [5]        检查节点5 = 5，返回层号3

节点层号对应关系¶

Text Only

二叉树层号分析：

       1          ← 第1层
      / \
     2   3        ← 第2层
    / \
   4   5          ← 第3层
      /
     6            ← 第4层

各节点的层号：
节点1：第1层
节点2：第2层
节点3：第2层
节点4：第3层
节点5：第3层
节点6：第4层

相关知识点延伸¶

1. 两种实现方式的区别¶

特点	计算型	操作型	非递归型
返回值	返回层号	打印层号	返回层号
执行时机	找到后向上返回	找到时立即打印	找到时立即返回
内存使用	递归栈	递归栈	显式队列
代码复杂度	中等	简单	复杂
多结果处理	只返回一个结果	可打印多个结果	只返回一个结果

2. 重要概念澄清¶

层号定义： - 根节点为第1层 - 根节点的子节点为第2层 - 以此类推

与深度的区别： - 层号：从根节点开始计数（1, 2, 3, ...） - 深度：从根节点开始计数（0, 1, 2, ...）

3. 其他相关查找方法¶

C
// 查找节点并返回路径
typedef struct PathResult {
    int path[100];    // 路径数组
    int length;       // 路径长度
    int found;        // 是否找到
} PathResult;

PathResult findNodeWithPath(BiTree root, int x) {
    PathResult result = {{0}, 0, 0};
    if (root == NULL) return result;

    int path[100];
    int pathLen = 0;

    if (findPathHelper(root, x, path, &pathLen)) {
        for (int i = 0; i < pathLen; i++) {
            result.path[i] = path[i];
        }
        result.length = pathLen;
        result.found = 1;
    }

    return result;
}

// 辅助函数：查找路径
int findPathHelper(BiTree root, int x, int path[], int* pathLen) {
    if (root == NULL) return 0;

    path[(*pathLen)++] = root->data;

    if (root->data == x) return 1;

    if (findPathHelper(root->lchild, x, path, pathLen) ||
        findPathHelper(root->rchild, x, path, pathLen)) {
        return 1;
    }

    (*pathLen)--;
    return 0;
}

4. 实际应用场景¶

文件系统：查找文件在目录树中的层级
组织架构：查找员工在组织结构中的层级
游戏开发：查找游戏对象在场景树中的层级
网络拓扑：查找设备在网络结构中的层级

5. 性能优化建议¶

对于频繁查找操作，可以预先建立值到层号的映射表
对于静态树结构，可以使用缓存机制存储查找结果
对于大型树结构，优先考虑非递归实现避免栈溢出

6. 错误处理和边界情况¶

C
// 增强版查找函数，包含错误处理
int findLevel_Enhanced(BiTree root, int x) {
    // 输入验证
    if (root == NULL) {
        printf("错误：树为空\n");
        return -1;  // 使用-1表示错误
    }

    int result = findLevel_Compute(root, x);
    if (result == 0) {
        printf("警告：未找到值为 %d 的节点\n", x);
    }

    return result;
}

// 查找所有匹配节点
typedef struct SearchResult {
    int levels[100];  // 所有匹配节点的层号
    int count;        // 匹配节点数量
} SearchResult;

SearchResult findAllOccurrences(BiTree root, int x) {
    SearchResult result = {{0}, 0};
    findAllHelper(root, x, 1, &result);
    return result;
}

void findAllHelper(BiTree root, int x, int level, SearchResult* result) {
    if (root != NULL) {
        if (root->data == x) {
            result->levels[result->count++] = level;
        }
        findAllHelper(root->lchild, x, level + 1, result);
        findAllHelper(root->rchild, x, level + 1, result);
    }
}

7. 扩展应用¶

C
// 计算二叉树的高度
int getTreeHeight(BiTree root) {
    if (root == NULL) return 0;
    int leftHeight = getTreeHeight(root->lchild);
    int rightHeight = getTreeHeight(root->rchild);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 查找最深的匹配节点
int findDeepestOccurrence(BiTree root, int x) {
    int maxLevel = 0;
    findDeepestHelper(root, x, 1, &maxLevel);
    return maxLevel;
}

void findDeepestHelper(BiTree root, int x, int currentLevel, int* maxLevel) {
    if (root != NULL) {
        if (root->data == x && currentLevel > *maxLevel) {
            *maxLevel = currentLevel;
        }
        findDeepestHelper(root->lchild, x, currentLevel + 1, maxLevel);
        findDeepestHelper(root->rchild, x, currentLevel + 1, maxLevel);
    }
}

这些查找节点层号的算法是二叉树操作的重要组成部分，理解其原理对于掌握树的搜索和定位操作非常重要。在实际应用中，应根据具体需求选择合适的实现方式。