二叉树的先序、序、后序遍历Java
一、树的递归定义
树(tree)是由n(n>=0)个结点组成的有限集合,树中元素通常称为结点。n=0的树通常被称为空树;n>0的树T由以下两个条件约定构成:
①有一个特殊的结点称为根(root)结点,它没有父母结点。
②除根结点之外的其他结点分为m(0<=m<n)个互不相交的子集T0,T1,...,T(m-1),其中每个子集Ti(0<=i<m)也具有树结构,称为根的子树(subtree)。
树是递归定义的。结点是树的基本单位,若干结点组成一棵子树,根结点和若干棵互不相干的子树组成一棵树。树中的每个结点也是该树中某一棵子树的根。因此,树是由结点组成的,结点之间具有层次关系的数据结构。森林(forest)是树的集合。
二、二叉树的递归定义
二叉树(binary tree)n(n>=0)个结点(数据元素)组成的有限集合,递归定义如下:
①n=0,为空二叉树。
②n>0,二叉树由三部分组成:根结点、左子树和右子树(互不相交),子树也是一颗二叉树。
一棵二叉树,它由根结点、左子树和右子树组成,结点与其子树的根结点之间的连线表示结点之间的层次关系,用“^”表示空子树。
二叉树是递归定义的。结点是二叉树的基本单位,若干结点组成一棵子树,两棵互不相交的子树和根结点组成一棵二叉树。
三、二叉树的三种遍历方式(先序、中序、后序)
(1)先序遍历
遍历过程:
①访问根结点;②先序遍历其左子树;③先序遍历其右子树。
代码实现:
public void preorder()//先序遍历二叉树
{
preorder(this.root);//先序遍历以root结点为根的二叉树
System.out.println();
}
public void preorder(BinaryNode<T> p)//先序遍历以p结点为根的子树,递归方法
{
if(p!=null)//若二叉树不为空
{
System.out.print(p.data.toString() "");//先访问当前结点元素
preorder(p.left);//先序遍历p的左子树,递归调用,参数为左孩子
preorder(p.right);//先序遍历p的右子树,递归调用,参数为右孩子
}
}
遍历结果:
A B D E H C F I G
(2)中序遍历
遍历过程:
①中序遍历其左子树;②访问根结点;③中序遍历其右子树。
代码实现:
public void inorder()//中序遍历二叉树
{
inorder(this.root);//中序遍历以root结点为根的二叉树
System.out.println();
}
public void inorder(BinaryNode<T> p)//中序遍历以p结点为根的子树,递归方法
{
if(p!=null)//若二叉树不为空
{
inorder(p.left);//中序遍历p的左子树,递归调用
System.out.print(p.data.toString() "");//访问当前结点元素
inorder(p.right);//中序遍历p的右子树,递归调用
}
}
遍历结果:
D B H E A F I C G
(3)后序遍历
遍历过程:
①后序遍历其左子树;②后序遍历其右子树;③访问根结点。
代码实现:
public void postorder()//后序遍历二叉树
{
postorder(this.root);//后序遍历以root结点为根的二叉树
System.out.println();
}
public void postorder(BinaryNode<T> p)//后序遍历以p结点为根的子树,递归方法
{
if(p!=null)//若二叉树不为空
{
postorder(p.left);//后序遍历p的左子树,递归调用
postorder(p.right);//后序遍历p的右子树,递归调用
System.out.print(p.data.toString() "");//后访问当前结点元素
}
}
遍历结果:
D H E B I F G C A
总结:
1. 先序、中序和后序三种遍历过程所经过结点的路线一样(向下递、向上归),但访问各个结点的时刻不同。
2. 左侧、中侧、右侧分别标记了先序、中序和后序访问各结点的时刻。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfaiej
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01