05-5.4.3 树和森林的遍历

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

树的遍历

先根遍历

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

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

不难发现：树的先根遍历序列和这棵树对应二叉树的先序序列相同

后根遍历

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

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

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

层序遍历

用队列实现：

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

森林的遍历

先序遍历

若森林非空，则按如下规则进行遍历：

1. 访问森林中的第一棵树的根结点
2. 先序遍历第一棵树中根结点的子树森林
3. 先序遍历除去第一棵树之后剩余的树构成的森林

效果等同于依次对各个子树进行先根遍历

中序遍历

若森林非空，则按如下规则进行遍历：

1. 中序遍历森林中第一棵树的根结点的子树森林
2. 访问第一棵树的根结点
3. 中序遍历除去第一棵树之后剩余的树构成的森林