详解二叉树先序遍历 - 极悦
首页 课程 师资 教程 报名

详解二叉树先序遍历

  • 2021-02-03 17:41:53
  • 1316次 极悦

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

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

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;  

        }  

    }  

}  

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

 

选你想看

你适合学Java吗?4大专业测评方法

代码逻辑 吸收能力 技术学习能力 综合素质

先测评确定适合在学习

在线申请免费测试名额
价值1998元实验班免费学
姓名
手机
提交