您当前的位置:首页 > 计算机 > 文件格式与编码

树的遍历

时间:01-02来源:作者:点击数:

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有节点系统地访问,即依次对树中每个节点访问一次且仅访问一次。

对于二叉树,树的3种最重要的遍历方式分别称为先序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时,若按访问节点的先后次序将节点排列起来,就可分别得到树中所有节点的先序列表、中序列表和后序列表。相应的节点次序分别称为节点的先序、中序和后序。

对于多叉树,数的遍历通常有两种:深度优先遍历、广度优先遍历。

下面以二叉树为例讲解三种遍历方法。

每棵二叉树由节点、左子树、右子树这三个基本部分组成,如果遍历了这三部分,也就遍历了整个二叉树。

先序遍历

先序遍历指先访问根,然后访问孩子的遍历方式。若二叉树为非空,则过程为:

①访问根节点。

②先序遍历左子树。

③先序遍历右子树。

中序遍历

中序遍历指先访问左(右)孩子,然后访问根,最后访问右(左)孩子的遍历方式。若二叉树为非空,则过程为:

①按中序遍历左子树。

②访问根节点。

③按中序遍历右子树。

后序遍历

后序遍历指先访问孩子,然后访问根的遍历方式。若二叉树为非空,则过程为:

①按后序遍历左子树。

②按后序遍历右子树。

③访问根节点。

如图1-23的二叉树所示,D为二叉树中某一节点,L、R分别为节点D的左、右子树,则其遍历方式有6种:

  先左后右 先右后左
先序 DLR DRL
中序 LDR RDL
后序 LRD RLD
树的遍历
图1-23 二叉树示例

例如,以先左后右的方式用三种遍历方法对图1-24中的二叉树进行遍历。

树的遍历
图1-24 二叉树示例

用先序遍历的方式,得到结果为ABDECF。

用中序遍历的方式,得到结果为DBEACF。

用后序遍历的方式,得到结果为DEBFCA。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门