数据结构(5.4_2)——树和森林的遍历

树的先根遍历(深度优先遍历)

若树非空，先访问根结点，再依次对每棵子树进行先根遍历

树的先根遍历序列和这棵树相应二叉树的先序序列相同。

伪代码：

//树的先根遍历
void PreOrder(TreeNode* R) {if (R != NULL) {visit(R);//访问根结点while(R还有下一个子树T)PreOrder(T)//先根遍历下一棵子树}
}

实例：

#include <stdio.h>// 定义树节点的结构体（兄弟兄弟表示法）
typedef struct CSNode {int data;                   // 节点存储的数据struct CSNode* firstchild; // 指向第一个子节点的指针struct CSNode* nextsibling; // 指向右兄弟节点的指针
} CSNode, *CSTree;// 创建一个新树节点
CSNode* createTreeNode(int value) {CSNode* newNode = (CSNode*)malloc(sizeof(CSNode));if (newNode == NULL) {fprintf(stderr, "Memory allocation failed.\n");exit(EXIT_FAILURE);}newNode->data = value;newNode->firstchild = NULL;newNode->nextsibling = NULL;return newNode;
}// 向树节点添加子节点
void addChild(CSTree parent, CSTree child) {if (parent == NULL || child == NULL) {return;}if (parent->firstchild == NULL) {parent->firstchild = child;} else {CSTree current = parent->firstchild;while (current->nextsibling != NULL) {current = current->nextsibling;}current->nextsibling = child;}
}// 访问节点
void visit(CSNode* node) {if (node != NULL) {printf("%d ", node->data);}
}// 先根遍历
void PreOrder(CSTree R) {if (R != NULL) {visit(R); // 访问根节点CSTree current = R->firstchild;while (current != NULL) {PreOrder(current); // 先根遍历子树current = current->nextsibling; // 移动到下一个兄弟节点}}
}// 释放树的内存
void freeTree(CSTree root) {if (root == NULL) {return;}CSTree current = root->firstchild;while (current != NULL) {CSTree temp = current;current = current->nextsibling;freeTree(temp);}free(root);
}// 主函数示例
int main() {// 创建树节点CSTree root = createTreeNode(1);CSTree child1 = createTreeNode(2);CSTree child2 = createTreeNode(3);CSTree child3 = createTreeNode(4);CSTree child4 = createTreeNode(5);CSTree child5 = createTreeNode(6);// 构建树结构addChild(root, child1);addChild(root, child2);addChild(child1, child3);addChild(child1, child4);addChild(child2, child5);// 执行先根遍历printf("Pre-order traversal of the tree is: ");PreOrder(root);printf("\n");// 释放树占用的内存freeTree(root);return 0;
}

我们首先创建了一个树，然后通过 addChild 函数将子节点添加到其父节点。PreOrder 函数按照先根遍历的顺序访问每个节点。最后，我们通过 freeTree 函数释放了整个树所占用的内存。在主函数 main 中，我们构建了一个具体的树结构，并执行了先根遍历。

树的后根遍历 (深度优先遍历)

若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点

树的后根遍历序列和这棵树相应二叉树的中序序列相同。

伪代码：

//树的后根遍历
void PostOrder(TreeNode* R) {if (R != NULL) {while (R还有下一个子树T)PostOrder(T)//后根遍历下一棵子树visit(R);//访问根结点    }
}

实例：

#include <stdio.h>// 定义树节点的结构体（兄弟兄弟表示法）
typedef struct CSNode {int data;                   // 节点存储的数据struct CSNode* firstchild; // 指向第一个子节点的指针struct CSNode* nextsibling; // 指向右兄弟节点的指针
} CSNode, *CSTree;// 创建一个新树节点
CSNode* createTreeNode(int value) {CSNode* newNode = (CSNode*)malloc(sizeof(CSNode));if (newNode == NULL) {fprintf(stderr, "Memory allocation failed.\n");exit(EXIT_FAILURE);}newNode->data = value;newNode->firstchild = NULL;newNode->nextsibling = NULL;return newNode;
}// 向树节点添加子节点
void addChild(CSTree parent, CSTree child) {if (parent == NULL || child == NULL) {return;}if (parent->firstchild == NULL) {parent->firstchild = child;} else {CSTree current = parent->firstchild;while (current->nextsibling != NULL) {current = current->nextsibling;}current->nextsibling = child;}
}// 访问节点
void visit(CSNode* node) {if (node != NULL) {printf("%d ", node->data);}
}// 后根遍历
void PostOrder(CSTree R) {if (R != NULL) {CSTree current = R->firstchild;while (current != NULL) {PostOrder(current); // 后根遍历子树current = current->nextsibling; // 移动到下一个兄弟节点}visit(R); // 访问根节点}
}// 释放树的内存
void freeTree(CSTree root) {if (root == NULL) {return;}CSTree current = root->firstchild;while (current != NULL) {CSTree temp = current;current = current->nextsibling;freeTree(temp);}free(root);
}// 主函数示例
int main() {// 创建树节点CSTree root = createTreeNode(1);CSTree child1 = createTreeNode(2);CSTree child2 = createTreeNode(3);CSTree child3 = createTreeNode(4);CSTree child4 = createTreeNode(5);CSTree child5 = createTreeNode(6);// 构建树结构addChild(root, child1);addChild(root, child2);addChild(child1, child3);addChild(child1, child4);addChild(child2, child5);// 执行后根遍历printf("Post-order traversal of the tree is: ");PostOrder(root);printf("\n");// 释放树占用的内存freeTree(root);return 0;
}

我们首先创建了一个树，然后通过 addChild 函数将子节点添加到其父节点。PostOrder 函数按照后根遍历的顺序访问每个节点。首先递归地遍历所有子树，然后访问根节点。最后，我们通过 freeTree 函数释放了整个树所占用的内存。在主函数 main 中，我们构建了一个具体的树结构，并执行了后根遍历。

树的层次遍历 (广度优先遍历)

用队列实现：

若树非空，则根节点入队
若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
重复2直到队列为空

伪代码：

// 树的层次遍历
void LevelOrder(TreeNode* root) {if (root == NULL) {return;}// 创建一个队列，用于存储待访问的节点Queue queue;initializeQueue(&queue);// 将根节点入队enqueue(queue, root);// 当队列不为空时，继续遍历while (!isEmpty(queue)) {// 出队一个节点TreeNode* current = dequeue(queue);// 访问当前节点visit(current);// 获取当前节点的所有子节点TreeNode* child = current->firstchild;// 遍历当前节点的所有子节点while (child != NULL) {enqueue(queue, child);child = child->nextsibling;}}
}// 辅助函数：初始化队列
void initializeQueue(Queue* queue) {queue->front = NULL;queue->rear = NULL;
}// 辅助函数：队列是否为空
bool isEmpty(Queue queue) {return queue.front == NULL;
}// 辅助函数：将节点入队
void enqueue(Queue* queue, TreeNode* node) {QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (newNode == NULL) {// 处理内存分配失败的情况}newNode->node = node;newNode->next = NULL;if (queue->rear == NULL) {queue->front = newNode;} else {queue->rear->next = newNode;}queue->rear = newNode;
}// 辅助函数：从队列中出队一个节点
TreeNode* dequeue(Queue* queue) {if (isEmpty(*queue)) {return NULL;}TreeNode* frontNode = queue->front->node;QueueNode* temp = queue->front;queue->front = queue->front->next;if (queue->front == NULL) {queue->rear = NULL;}free(temp);return frontNode;
}

代码实例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 定义树节点的结构体（兄弟兄弟表示法）
typedef struct CSNode {int data;                   // 节点存储的数据struct CSNode* firstchild; // 指向第一个子节点的指针struct CSNode* nextsibling; // 指向右兄弟节点的指针
} CSNode, *CSTree;// 创建一个新树节点
CSNode* createTreeNode(int value) {CSNode* newNode = (CSNode*)malloc(sizeof(CSNode));if (newNode == NULL) {fprintf(stderr, "Memory allocation failed.\n");exit(EXIT_FAILURE);}newNode->data = value;newNode->firstchild = NULL;newNode->nextsibling = NULL;return newNode;
}// 向树节点添加子节点
void addChild(CSTree parent, CSTree child) {if (parent == NULL || child == NULL) {return;}if (parent->firstchild == NULL) {parent->firstchild = child;} else {CSTree current = parent->firstchild;while (current->nextsibling != NULL) {current = current->nextsibling;}current->nextsibling = child;}
}// 访问节点
void visit(CSNode* node) {if (node != NULL) {printf("%d ", node->data);}
}// 层次遍历
void LevelOrder(CSTree root) {if (root == NULL) {return;}CSTree current = root;bool isRoot = true;while (current != NULL) {if (isRoot) {visit(current); // 访问根节点isRoot = false;}CSTree temp = current->firstchild;while (temp != NULL) {visit(temp); // 访问当前节点的所有子节点temp = temp->nextsibling;}current = current->nextsibling; // 移动到下一个兄弟节点}
}// 释放树的内存
void freeTree(CSTree root) {if (root == NULL) {return;}CSTree current = root->firstchild;while (current != NULL) {CSTree temp = current;current = current->nextsibling;freeTree(temp);}free(root);
}// 主函数示例
int main() {// 创建树节点CSTree root = createTreeNode(1);CSTree child1 = createTreeNode(2);CSTree child2 = createTreeNode(3);CSTree child3 = createTreeNode(4);CSTree child4 = createTreeNode(5);CSTree child5 = createTreeNode(6);// 构建树结构addChild(root, child1);addChild(root, child2);addChild(child1, child3);addChild(child1, child4);addChild(child2, child5);// 执行层次遍历printf("Level-order traversal of the tree is: ");LevelOrder(root);printf("\n");// 释放树占用的内存freeTree(root);return 0;
}

我们首先创建了一个树，然后通过 addChild 函数将子节点添加到其父节点。LevelOrder 函数按照层次遍历的顺序访问每个节点。首先将根节点入队，然后在循环中不断从队列中出队节点并访问它，然后将它的所有子节点入队。当队列为空时，遍历结束。最后，我们通过 freeTree 函数释放了整个树所占用的内存。在主函数 main 中，我们构建了一个具体的树结构，并执行了层次遍历。

森林。森林是m(m>=0)棵互不相交的树的集合。每棵树去掉根节点后，其各个子树又组成森林。