c语言数据结构使用孩子兄弟链存储结构,实现树的创建、删除、以及先序、后序、层次遍历。
时间: 2023-09-28 14:11:15 浏览: 53
孩子兄弟链存储结构(又称二叉树的二叉链表存储结构)是指在二叉链表存储结构的基础上,将每个结点的左孩子指针改为指向它的第一个孩子结点,右孩子指针改为指向它的下一个兄弟结点。这样,每个结点就可以通过它的第一个孩子结点和下一个兄弟结点,依次找到它的所有孩子和兄弟结点,从而构成一个多叉树。下面是使用孩子兄弟链存储结构实现树的创建、删除、以及先序、后序、层次遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树的结构体
typedef struct TreeNode {
int data; // 结点数据
struct TreeNode *firstChild; // 指向第一个孩子结点
struct TreeNode *nextSibling; // 指向下一个兄弟结点
} TreeNode, *Tree;
// 创建一棵树
Tree createTree()
{
int data;
scanf("%d", &data);
if (data == -1) {
return NULL;
} else {
Tree root = (Tree)malloc(sizeof(TreeNode));
root->data = data;
root->firstChild = createTree(); // 递归创建子树
root->nextSibling = createTree(); // 递归创建兄弟树
return root;
}
}
// 删除一棵树
void destroyTree(Tree root)
{
if (root != NULL) {
destroyTree(root->firstChild); // 递归删除子树
destroyTree(root->nextSibling); // 递归删除兄弟树
free(root);
}
}
// 先序遍历树
void preOrderTraversal(Tree root)
{
if (root != NULL) {
printf("%d ", root->data); // 访问结点数据
preOrderTraversal(root->firstChild); // 递归遍历子树
preOrderTraversal(root->nextSibling); // 递归遍历兄弟树
}
}
// 后序遍历树
void postOrderTraversal(Tree root)
{
if (root != NULL) {
postOrderTraversal(root->firstChild); // 递归遍历子树
printf("%d ", root->data); // 访问结点数据
postOrderTraversal(root->nextSibling); // 递归遍历兄弟树
}
}
// 层次遍历树(借助队列实现)
void levelOrderTraversal(Tree root)
{
if (root == NULL) {
return;
}
Queue queue = createQueue();
enqueue(queue, root); // 根节点入队
while (!isEmpty(queue)) {
Tree node = dequeue(queue); // 出队
printf("%d ", node->data); // 访问结点数据
if (node->firstChild != NULL) {
enqueue(queue, node->firstChild); // 孩子结点入队
}
if (node->nextSibling != NULL) {
enqueue(queue, node->nextSibling); // 兄弟结点入队
}
}
destroyQueue(queue);
}
```
其中,createTree()函数用于创建一棵树,destroyTree()函数用于删除一棵树,preOrderTraversal()函数用于先序遍历树,postOrderTraversal()函数用于后序遍历树,levelOrderTraversal()函数用于层次遍历树。需要注意的是,levelOrderTraversal()函数需要借助队列实现。此外,由于使用了递归操作,需要注意避免栈溢出。