详解二叉树先序遍历

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。我们都知道二叉树的遍历方式有先序、中序和后序遍历，本文我们主要来介绍二叉树先序遍历。

首先，我们要知道二叉树先序遍历的实现思想：

1.访问根节点；

2.访问当前节点的左子树；

3.若当前节点无左子树，则访问当前节点的右子树；

如下图表示一颗二叉树，对它进行先序遍历操作，采用两种方法，递归和非递归操作。

采用先序遍历的思想遍历该二叉树的过程为：

1.访问该二叉树的根节点，找到 1；

2.访问节点 1 的左子树，找到节点 2；

3.访问节点 2 的左子树，找到节点 4；

4.由于访问节点 4 左子树失败，且也没有右子树，因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树，因此现在开始遍历，即访问节5；

5.由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；

6.访问节点 3 左子树，找到节点6；

7.由于节点 6无左右子树，因此以节点6为根节点的子树遍历完成。但节点 3还没有遍历其右子树，因此现在开始遍历，即访问节7；到这里，整个先序遍历完成。

1、递归操作：

思想：若二叉树为空，返回。否则

1)遍历根节点；

2)先序遍历左子树；

3）先序遍历右子树

代码：

void PreOrder(BiTree root)  

{  

    if(root==NULL)  

        return ;  

    printf("%c ", root->data); //输出数据  

    PreOrder(root->lchild); //递归调用，先序遍历左子树  

    PreOrder(root->rchild); //递归调用，先序遍历右子树  

}  

2、非递归操作

思想：二叉树的非递归先序遍历，先序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作， 每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。

代码：

void PreOrder_Nonrecursive(BiTree T)     //先序遍历的非递归    

{  

    if(!T) return ;    

    stack s;  

    s.push(T);  

    while(!s.empty())  

    {  

        BiTree temp = s.top();  

        cout<data<<" ";  

        s.pop();  

        if(temp->rchild)  

            s.push(temp->rchild);  

        if(temp->lchild)  

            s.push(temp->lchild);  

    }  

}  

或者：

void PreOrder_Nonrecursive(BiTree T)     //先序遍历的非递归  

{  

    if(!T) return ;  

    stack s;  

    while(T)          // 左子树上的节点全部压入到栈中  

    {  

        s.push(T);  

        cout<data<<"  ";  

        T = T->lchild;  

    }        

    while(!s.empty())  

    {          

        BiTree temp = s.top()->rchild;  // 栈顶元素的右子树  

        s.pop();                        // 弹出栈顶元素  

        while(temp)          // 栈顶元素存在右子树，则对右子树同样遍历到最下方  

        {  

            cout<data<<"  ";  

            s.push(temp);  

            temp = temp->lchild;  

        }  

    }  

}  

以上就是二叉树先序遍历，经过我们图文并茂的描述，相信大多数小伙伴都能够理解二叉树先序遍历的步骤，其实，二叉树其他遍历方式和先序遍历也是大同小异的，我们只要能够熟练掌握二叉树先序遍历，就能举一反三，学会二叉树其他遍历方式，当然，本站的数据结构和算法教程对二叉树遍历方式有非常详细的讲解，不需要我们过多的推导，但我们学习的时候应该更注重理解，这样才能够学有所思。