以下摘抄自Wiki
深度优先遍历 //常见的的三种遍历方法均为DFS
以下均是用递归方法。
先序遍历(Pre-Order Traversal)
指先访问根,然后访问子树的遍历方式,其C代码如下:
void pre_order_traversal(TreeNode* root){
//Do Something with root
if(root->lchild!=NULL)
pre_order_traversal(root->lchild);
if(root->rchild!=NULL)
pre_order_traversal(root->rchild);
}
中序遍历(In-Order Traversal)
指先访问左(右)子树,然后访问根,最后访问右(左)子树的遍历方式,其C代码如下
void in_order_traversal(TreeNode* root){
if(root->lchild!=NULL)
in_order_traversal(root->lchild);
//Do Something with root
if(root->rchild!=NULL)
in_order_traversal(root->rchild);
}
后序遍历(Post-Order Traversal)
指先访问子树,然后访问根的遍历方式,其C代码如下
void post_order_traversal(TreeNode* root){
if(root->lchild!=NULL)
post_order_traversal(root->lchild);
if(root->rchild!=NULL)
post_order_traversal(root->rchild);
//Do Something with root
}
广度优先遍历
和深度优先遍历不同,广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。
void Layer_Traver(tree* root)
{
int head = 0,tail = 0;
tree* p[SIZE] = {NULL};
tree* tmp;
if(root != NULL)
{
p[head] = root;
tail++;
//Do Something with p[head]
}
else
{
return;
}
while(head < tail) //数组实现的队列 翻书
{
tmp = p[head];
//Do Something with p[head]
if(tmp->left != NULL)//left
{
p[tail] = tmp->left;
tail++;
}
if(tmp->right != NULL)//right
{
p[tail] = tmp->right;
tail++;
}
head++;
}
return;
}