二叉树的遍历_第1页
二叉树的遍历_第2页
二叉树的遍历_第3页
二叉树的遍历_第4页
二叉树的遍历_第5页
已阅读5页，还剩15页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

二叉树的遍历什么是树是由n（n>=0）个有限结点组成一个具有层次关系的集合树相关的概念空集合也是树，称为空树。空树中没有结点。结点的度：一个结点含有的子结点的个数称为该结点的度；叶结点或终端结点：度为0的结点称为叶结点；非终端结点或分支结点：度不为0的结点；双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；兄弟结点：具有相同父结点的结点互称为兄弟结点；树的度：一棵树中，最大的结点的度称为树的度；结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；树的高度或深度：树中结点的最大层次；堂兄弟结点：双亲在同一层的结点互为堂兄弟；结点的祖先：从根到该结点所经分支上的所有结点；子孙：以某结点为根的子树中任一结点都称为该结点的子孙。二叉树每个节点最多含有两个子树的树称为二叉树

相关的“二叉树”完全二叉树满二叉树二叉树的遍历所谓遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。

访问结点所做的操作依赖于具体的应用问题。通常二叉树的遍历根据根节点的遍历次序分为：深度优先遍历先序（根）遍历中序（根）遍历后序（根）遍历广度优先遍历层次遍历先序（根）遍历

若二叉树为空，则退出，否则进行下面操作访问根节点遍历左子树遍历右子树口诀：根节点

左子树

右子树(根左右，NLR)

按照先序（根）遍历地方式，遍历二叉树，则访问顺序为：

A、B、D、H、I、E、J、C、F、G中序（根）遍历

若二叉树为空，则退出，否则进行下面操作遍历左子树访问根节点遍历右子树口诀：左子树

根节点

右子树（左根右，LNR）

按照中序（根）遍历的方式，遍历二叉树，则访问顺序为：

H、D、I、B、J、E、A、F、C、G后序（根）遍历

若二叉树为空，则退出，否则进行下面操作遍历左子树遍历右子树访问根节点口诀：左子树

右子树

根节点按照后序遍历的方式，遍历二叉树，则访问顺序为：

H、I、D、J、E、B、F、G、C、A层次遍历按照层次遍历按照层次遍历的方式，遍历二叉树，则访问顺序为：A、B、C、D、E、F、G、H、I、J代码实现构建树：publicclassBinaryTreeNode{

privateStringdata;

privateBinaryTreeNodeleft;

privateBinaryTreeNoderight;

publicBinaryTreeNode(){}

publicBinaryTreeNode(Stringdata,BinaryTreeNodeleft,BinaryTreeNoderight){

super();

this.data=data;

this.left=left;

this.right

人人文库> 全部分类> 应用文书 > 作业报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论