👋 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); // 访问根结点}
}
树的后根遍历序列 和 这棵树对应的二叉树的中序序列相同
层序遍历
用队列实现:
- 若树非空,则根结点入队
- 若队列非空,队头元素出队并访问,同时将该元素的孩子依次入队
- 重复第二步直到队列为空
森林的遍历
先序遍历
若森林非空,则按如下规则进行遍历:
- 访问森林中的第一棵树的根结点
- 先序遍历第一棵树中根结点的子树森林
- 先序遍历除去第一棵树之后剩余的树构成的森林
效果等同于依次对各个子树进行先根遍历
中序遍历
若森林非空,则按如下规则进行遍历:
- 中序遍历森林中第一棵树的根结点的子树森林
- 访问第一棵树的根结点
- 中序遍历除去第一棵树之后剩余的树构成的森林