树的遍历

维基百科,自由的百科全书
跳转至: 导航搜索

計算機科學裡,树的遍历是指通过一种方法按照一定的顺序访问一颗的过程。

对于二叉树,树的遍历通常有四种:先序遍历中序遍历后序遍历广度优先遍历。(前三种亦统称深度优先遍历)对于多叉树,树的遍历通常有两种:深度优先遍历广度优先遍历

二叉树的遍历[编辑]

深度优先遍历[编辑]

以下均是用递归方法

先序遍历[编辑]

指先访问根,然后访问孩子的遍历方式,其C代码如下:

void XXBL(tree* root){

//Do Something with root
if(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 root
if(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

}

广度优先遍历[编辑]

和深度优先遍历不同,广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。

多叉树的遍历[编辑]

深度优先遍历[编辑]

广度优先遍历[编辑]

參考資料[编辑]