数据结构-二叉树的遍历(类C语言描写叙述)
遍历概念
所谓遍历(Traversal)是指沿着某条搜索路线。依次对树中每一个结点均做一次且仅做一次訪问。訪问结点所做的操作依赖于详细的应用问题。
遍历是二叉树上最重要的运算之中的一个,是二叉树上进行其他运算之基础。
遍历方案
1.遍历方案
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此。在任一给定结点上,能够按某种次序运行三个操作:
(1)訪问结点本身(N),
(2)遍历该结点的左子树(L),
(3)遍历该结点的右子树(R)。
以上三种操作有六种运行次序:
NLR、LNR、LRN、NRL、RNL、RLN。
注意:
前三种次序与后三种次序对称。故仅仅讨论先左后右的前三种次序。
2.三种遍历的命名
依据訪问结点操作发生位置命名:
① NLR:前序遍历(PreorderTraversal亦称(先序遍历))
——訪问结点的操作发生在遍历其左右子树之前。
② LNR:中序遍历(InorderTraversal)
——訪问结点的操作发生在遍历其左右子树之中(间)。
③ LRN:后序遍历(PostorderTraversal)
——訪问结点的操作发生在遍历其左右子树之后。
注意:
因为被訪问的结点必是某子树的根。所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。
NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
遍历算法
1.中序遍历的递归算法定义:
若二叉树非空。则依次运行例如以下操作:
(1)遍历左子树。
(2)訪问根结点;
(3)遍历右子树。
2.先序遍历的递归算法定义:
若二叉树非空,则依次运行例如以下操作:
(1) 訪问根结点;
(2) 遍历左子树;
(3) 遍历右子树。
3.后序遍历得递归算法定义:
若二叉树非空。则依次运行例如以下操作:
(1)遍历左子树。
(2)遍历右子树。
(3)訪问根结点。
4.中序遍历的算法实现
用二叉链表做为存储结构,中序遍历算法可描写叙述为:
void InOrder(BinTree T)
{ //算法里①~⑥是为了说明运行过程增加的标号
① if(T) { // 假设二叉树非空
② InOrder(T->lchild);
③ printf("%c",T->data)。 // 訪问结点
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
最新文章
- C++ std::map
- 关于Xcode8打印一堆log问题
- js模版引擎handlebars.js实用教程——如何引入Handlebars.js
- Android怎么使用字体图标 自定义FontTextView字体图标控件-- 使用方法
- Markdown中插入数学公式
- VC++ 如何在显示对话框的时候,指定焦点控件!
- GoLang 的 daemonize 实现
- 提取html中的src 路径
- 《Java编程那点事儿》读书笔记(七)——多线程
- HDU 3844 Mining Your Own Business(割点,经典)
- [弹出消息] C#ShowMessageBox帮助类
- 炫酷的CSS3发光搜索表单,附演示和源码
- Java ";=="; 和 ";equals"; 和 ";"; 问题
- DBCC page 数据页 堆 底层数据分布大小计算
- 其他综合-内网下Yum仓库搭建配置
- 题解 UVA1567 【A simple stone game】
- 【lintcode13】字符串查找
- Visual Studio 2015 激活码
- git 查看某个文件的修改记录
- AndroidStudio相关经验记录
热门文章
- Thinkphp框架图片上传实例
- React深入 - 手写redux api
- h5 页面 禁止网页缩放
- linux 定时任务(注意事项)
- POJ 2485 Highways (求最小生成树中最大的边)
- 发布tomcate时报A configuration error occurred during startup.please verify the preference field with the prompat:null
- 大数据学习——yum练习安装mysql
- NYOJ 203 三国志
- Triangular Pastures (二维01背包)
- NYOJ760-See LCS again,有技巧的暴力!