树的遍历
维基百科，自由的百科全书
 |
此條目或章节需要擴充，请協助改善这篇條目。（2010年10月3日） 更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 |
在計算機科學裡，树的遍历是指通过一种方法按照一定的顺序访问一颗树的过程。
对于二叉树，树的遍历通常有四种：先序遍历、中序遍历、后序遍历、广度优先遍历。（前三种亦统称深度优先遍历）对于多叉树，树的遍历通常有两种：深度优先遍历、广度优先遍历。
目录 |
[编辑] 二叉树的遍历
[编辑] 深度优先遍历
以下均是用递归方法
[编辑] 先序遍历
指先访问根，然后访问孩子的遍历方式，其C代码如下：
void XXBL(tree* root){
//Do Something with rootif(root->lchild!=NULL)XXBL(root->lchild);
if(root->rchild!=NULL)XXBL(root->rchild);
}
[编辑] 中序遍历
指先访问左（右）孩子，然后访问根，最后访问右（左）孩子的遍历方式，其C代码如下
void ZXBL(tree* root){
if(root->lchild!=NULL)ZXBL(root->lchild);
//Do Something with rootif(root->rchild!=NULL)ZXBL(root->rchild);
}
[编辑] 后序遍历
指先访问孩子，然后访问根的遍历方式，其C代码如下
void HXBL(tree* root){
if(root->lchild!=NULL)HXBL(root->lchild);
if(root->rchild!=NULL)HXBL(root->rchild);
//Do Something with root
}
[编辑] 广度优先遍历
和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。
[编辑] 多叉树的遍历
[编辑] 深度优先遍历
[编辑] 广度优先遍历
[编辑] 參考資料
- 算法导论
- 计算机程序设计艺术
