温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Java怎么实现遍历二叉树

发布时间:2021-06-04 17:14:59 来源:亿速云 阅读:137 作者:Leah 栏目:编程语言

本篇文章为大家展示了Java怎么实现遍历二叉树,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。

二叉树在计算机中的存储方式往往线性结构,线性存储分为顺序存储和链式存储,将二叉树按层序编号。

顺序结构:按编号的顺序进行存储,对于完全二叉树而言,顺序存储可以反映二叉树的逻辑,但是对于大多数的二叉树则无法反映其逻辑关系,不过可以用 ^ 来代替不存在的结点,但是如果这个树是一个右斜树,就非常浪费存储空间。所以二叉树的存储形式一般为链式存储结构。

链式存储:每一个结点都分有一个数据域(data)和两个指针域(lchild和rchild),指针域分别指向左孩子和右孩子,若为空则为null。遍历方式有四种:前序遍历、中序遍历、后序遍历及层序遍历,前三种遍历方式采用递归的思想进行遍历。

为方便理解,画一个树并结合代码

Java怎么实现遍历二叉树

前序遍历:若二叉树为空则返回null,否则先访问根节点然后遍历左子树,再遍历右子树,如图:ABDGHCEIF

代码如下:

void PreOrderTraverse(BiTree T) {
 if(T == NULL) /*为空返回*/
 return;
 printf("%c",T->data); /*输出该结点的信息*/
 PreOrderTraverse(T->lchild); /*遍历左子树*/
 PreOrderTraverse(T->rchild); /*遍历右子树*/
}

中序遍历:若二叉树为空则返回null,否则从根节点出发访问左子树,然后访问根结点,最后访问右子树,如图:GDHBAEICF

代码如下:

void InOrderTraverse(BiTree T) {
 if(T == NULL) /*为空返回*/
 return;
 InOrderTraverse(T->lchild); /*遍历左子树*/
 printf("%c",T->data); /*输出该结点的信息*/
 InOrderTraverse(T->rchild); /*遍历右子树*/
}

后序遍历:若二叉树为空则返回null,否则以先叶子后结点的方式进行访问最后到根结点遍历结束,如图:GHDBIEFCA

代码如下:

void PostOrderTraverse(BiTree T) {
 if(T == NULL) /*为空返回*/
 return;
 PostOrderTraverse(T->lchild); /*遍历左子树*/
 PostOrderTraverse(T->rchild); /*遍历右子树*/
 printf("%c",T->data); /*输出该结点的信息*/
}

层序遍历:若二叉树为空则返回null,否则从第一层开始进行访问,如图:ABCDEFGHI,按编号进行输出或操作即可

上述内容就是Java怎么实现遍历二叉树,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI