创建孩子兄弟链表的树c语言,一般树的建立(孩子兄弟链表) 、遍历、深度
时间: 2023-08-10 17:09:39 浏览: 55
树的孩子兄弟链表表示法可以使用结构体来实现,每个节点有三个指针:指向第一个孩子节点、指向下一个兄弟节点和指向父节点。
下面是一个简单的例子:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义树节点结构体
typedef struct TreeNode {
int data;
struct TreeNode *firstChild;
struct TreeNode *nextSibling;
struct TreeNode *parent;
} TreeNode;
// 创建树节点
TreeNode* createTreeNode(int data) {
TreeNode *node = (TreeNode*) malloc(sizeof(TreeNode));
node->data = data;
node->firstChild = NULL;
node->nextSibling = NULL;
node->parent = NULL;
return node;
}
// 添加孩子节点
void addChild(TreeNode *parent, TreeNode *child) {
if (parent == NULL || child == NULL) {
return;
}
child->parent = parent;
if (parent->firstChild == NULL) {
parent->firstChild = child;
} else {
TreeNode *sibling = parent->firstChild;
while (sibling->nextSibling != NULL) {
sibling = sibling->nextSibling;
}
sibling->nextSibling = child;
}
}
// 先序遍历
void preorderTraversal(TreeNode *node) {
if (node == NULL) {
return;
}
printf("%d ", node->data);
preorderTraversal(node->firstChild);
preorderTraversal(node->nextSibling);
}
// 后序遍历
void postorderTraversal(TreeNode *node) {
if (node == NULL) {
return;
}
postorderTraversal(node->firstChild);
printf("%d ", node->data);
postorderTraversal(node->nextSibling);
}
// 计算树深度
int calculateDepth(TreeNode *node) {
if (node == NULL) {
return 0;
}
int maxDepth = 0;
TreeNode *child = node->firstChild;
while (child != NULL) {
int childDepth = calculateDepth(child);
if (childDepth > maxDepth) {
maxDepth = childDepth;
}
child = child->nextSibling;
}
return maxDepth + 1;
}
int main() {
// 创建树节点
TreeNode *root = createTreeNode(1);
TreeNode *node2 = createTreeNode(2);
TreeNode *node3 = createTreeNode(3);
TreeNode *node4 = createTreeNode(4);
TreeNode *node5 = createTreeNode(5);
TreeNode *node6 = createTreeNode(6);
TreeNode *node7 = createTreeNode(7);
TreeNode *node8 = createTreeNode(8);
// 添加孩子节点
addChild(root, node2);
addChild(root, node3);
addChild(node2, node4);
addChild(node2, node5);
addChild(node3, node6);
addChild(node4, node7);
addChild(node6, node8);
// 遍历树
printf("Preorder Traversal: ");
preorderTraversal(root);
printf("\n");
printf("Postorder Traversal: ");
postorderTraversal(root);
printf("\n");
// 计算深度
printf("Depth: %d\n", calculateDepth(root));
return 0;
}
```
这段代码演示了如何创建孩子兄弟链表的树、如何进行先序遍历和后序遍历、以及如何计算树的深度。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)