用C语言写一个对以左儿子—右兄弟链接表示的树编写计算树的深度的算法,并把代码整合到一起并添加函数库
时间: 2024-03-24 11:36:35 浏览: 24
好的,以下是一个使用左儿子-右兄弟链接表示树的深度的 C 语言算法:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node* left_child;
struct node* right_sibling;
} Node;
Node* create_node(int data) {
Node* new_node = (Node*) malloc(sizeof(Node));
new_node->data = data;
new_node->left_child = NULL;
new_node->right_sibling = NULL;
return new_node;
}
int tree_depth(Node* root) {
if (root == NULL) {
return 0;
}
int max_depth = 0;
Node* current_node = root->left_child;
while (current_node != NULL) {
int child_depth = tree_depth(current_node);
if (child_depth > max_depth) {
max_depth = child_depth;
}
current_node = current_node->right_sibling;
}
return max_depth + 1;
}
int main() {
Node* root = create_node(1);
root->left_child = create_node(2);
root->left_child->right_sibling = create_node(3);
root->left_child->right_sibling->right_sibling = create_node(4);
root->left_child->right_sibling->right_sibling->left_child = create_node(5);
printf("Depth of tree: %d\n", tree_depth(root));
return 0;
}
```
这个程序首先定义了一个 `Node` 结构体,包含数据、左儿子和右兄弟节点的指针。`create_node` 函数用于创建新的节点并初始化其数据和指针。`tree_depth` 函数用于计算树的深度,采用递归的方式遍历树的所有节点,并返回所有子树的最大深度。`main` 函数创建了一个树,打印出其深度。
为了整合代码并添加函数库,可以将上述代码保存到一个名为 `tree_depth.c` 的文件中,并在其顶部添加:
```
#include "tree_depth.h"
```
然后将 `Node` 结构体和 `create_node` 函数定义移动到 `tree_depth.h` 文件中,如下所示:
```
#ifndef TREE_DEPTH_H
#define TREE_DEPTH_H
typedef struct node {
int data;
struct node* left_child;
struct node* right_sibling;
} Node;
Node* create_node(int data);
#endif
```
最后,可以将 `tree_depth` 函数定义添加到 `tree_depth.h` 文件中:
```
#ifndef TREE_DEPTH_H
#define TREE_DEPTH_H
typedef struct node {
int data;
struct node* left_child;
struct node* right_sibling;
} Node;
Node* create_node(int data);
int tree_depth(Node* root);
#endif
```
这样,你就可以在其他程序中使用 `tree_depth.h` 头文件和上述函数了。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)