C语言实现:对于以左儿子—右兄弟链接表示的树,编写算法计算树的深度。
时间: 2024-12-06 07:26:42 浏览: 17
在C语言中,如果你想要计算以左儿子-右兄弟(也称为LRN或双亲链接法)表示的二叉树的深度,可以采用递归的方式来实现。首先,我们需要定义结构体来存储节点及其左右兄弟信息,然后编写一个函数`treeDepth`来进行计算。
```c
#include <stdio.h>
// 定义树节点结构
typedef struct TreeNode {
int val;
struct TreeNode *left, *right, *brother; // 左孩子、右孩子和右兄弟指针
} Node;
int treeDepth(Node* root) {
// 如果根节点为空,返回0
if (root == NULL) return 0;
// 计算左子树深度,加上1(因为根节点也算一层)
int left_depth = treeDepth(root->left);
// 右子树和当前节点在同一层,直接返回当前节点的层数
int right_depth = left_depth + 1;
// 返回两者的最大值,即整个树的最大深度
return (left_depth > right_depth) ? left_depth : right_depth;
}
int main() {
// 初始化并构建示例树,这里省略实际创建节点的过程
Node* root = ...;
int depth = treeDepth(root);
printf("Tree depth is: %d\n", depth);
return 0;
}
```
在这个例子中,`treeDepth`函数会递归地检查每个子树的深度,并返回整个树的最大深度。注意这个算法假设树中没有循环,如果存在循环可能会导致无限递归。
阅读全文