- 浏览: 27087 次
- 性别:
- 来自: 福州
最新评论
树:T={K,R}。K是包含n个结点的有穷集合(n>0),关系R满足以下条件:
(1)有且仅有一个结点k0∈K,它对于关系R来说没有前驱结点,结点k0称作树的根。
(2)除结点k0外,K中的每个结点对于关系R来说都有且仅有一个前驱结点。
(3)K中每个结点对于关系R来说可以有多个后继结点。
我这里主要讨论的是二叉树,因为这个是用的最广泛的,二叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
二叉树的节点定义形式如下:
class TreeNode<E>{
Comparable<E> key;//节点的值
TreeNode<E> llink;//左子树的指针
TreeNode<E> rlink;//右子树的指针
}
假如我们有这样一棵树
2
/ \
4 5
/ \/ \
7 310 8
/\ /
1 9 6
1)树的遍历:就是访问所有的节点一遍。一般来说,有四种遍历的方式,前序遍历:先访问节点本身,在访问左子树,之后再访问右子树,例如上面的树,前序遍历的次序是2 4 7 1 9 3 6 5 10 8;中序遍历,就是先访问左子树,再访问节点本身,最后访问右子树,上面的树中序遍历的次序是1 7 9 4 6 3 2 10 5 8;后序遍历,就是先访问左子树,再访问右子树,最后访问节点,上面的树后序遍历的次序是1 9 7 6 3 4 10 8 5 2;层次遍历就是按层次访问树的节点,上面的树层次遍历的属次序是2 4 5 7 3 10 8 1 9 6
具体代码实现,可以采用递归的方式实现,也可以采用非递归的方式实现。
递归方式实现(注意,我写的大体过程,具体使用时大家根据实际情况修改一下):
前序遍历:
- public static void preOrder(TreeNode root){
- if(root==null) return;
- visit(root);
- preOrder(root.llink);
- preorder(root.rlink);
- }
中序遍历:
- public static void inOrder(TreeNode root){
- if(root==null) return;
- inOrder(root.link);
- visit(root);
- inOrder(root.rlink);
- }
后序遍历:
- public static void postOrder(TreeNode root){
- if(root==null) return;
- postOrder(root.llink);
- postOrder(root.rlink);
- visit(root);
- }
层次遍历:
- public static void layerOrder(TreeNode root){
- if(root==null) return;
- ListQueue<TreeNode> q=new ListQueue<TreeNode>();
- q.insert(root);
- while(!q.empty()){
- TreeNode temp=q.remove();
- visit(temp);
- if(temp.llink!=null) q.insert(temp.llink);
- if(temp.rlink!=null) q.insert(temp.rlink);
- }
- }
我前面已经说过,使用递归只不过由系统在为我们维护一个调用栈,我们也可以具体明确的使用堆栈来非递归的实现树的遍历。
非递归实现树的遍历,我们先构建好一棵树,初始化一个栈,之后我们进入一个循环,我们不断弹出堆栈里的元素,直到堆栈为空,如果弹出的树节点表示一棵空树,我们就访问此节点,否则,我们根据下面的规则执行一系列的push操作。
对于前序:压入右子树,然后是左子树,再后是节点
对于中序:压入右子树,然后是节点,再后是左子树
对于后序:压入节点,然后是右子树,再后是左子树
当我们把一个节点的左右节点及本节点都入栈后,我们的节点本身就可以看成一棵空树了。为了标识这一特性,我们修改树节点为:
class TreeNode<E>{
Comparable<E> key;//节点的值
TreeNode<E> llink;//左子树的指针
TreeNode<E> rlink;//右子树的指针
boolean flag;//是否是空树
}
前序遍历的代码:
- public static void preOrder(TreeNode<E> node){
- if(node==null)return;
- ListStack<TreeNode<E>> stack=new ListStack<TreeNode<E>>();
- stack.push(node);
- while(!stack.empty()){
- TreeNode<E> t=stack.pop();
- if(t.flag){
- System.out.print(t.item+",");
- }else{
- if(t.rlink!=null)
- stack.push(t.rlink);
- if(t.llink!=null)
- stack.push(t.llink);
- stack.push(t);
- t.flag=true;
- }
- }
- }
中序遍历的代码:
- public static void preOrder(TreeNode<E> node){
- if(node==null)return;
- ListStack<TreeNode<E>> stack=new ListStack<TreeNode<E>>();
- stack.push(node);
- while(!stack.empty()){
- TreeNode<E> t=stack.pop();
- if(t.flag){
- System.out.print(t.item+",");
- }else{
- if(t.rlink!=null)
- stack.push(t.rlink);
- stack.push(t);
- if(t.llink!=null)
- stack.push(t.llink);
- t.flag=true;
- }
- }
- }
后序遍历的代码:
- public static void preOrder(TreeNode<E> node){
- if(node==null)return;
- ListStack<TreeNode<E>> stack=new ListStack<TreeNode<E>>();
- stack.push(node);
- while(!stack.empty()){
- TreeNode<E> t=stack.pop();
- if(t.flag){
- System.out.print(t.item+",");
- }else{
- stack.push(t);
- if(t.rlink!=null)
- stack.push(t.rlink);
- if(t.llink!=null)
- stack.push(t.llink);
- t.flag=true;
- }
- }
- }
发表评论
-
基础数据结构——图
2010-09-20 15:49 875图(Graph)G由两个 ... -
基础数据结构——栈和队列
2010-09-20 15:40 744所谓的栈,是一个含有至少两个基本操作的抽象数据类型 ... -
基本数据结构——数组和链表
2010-09-20 15:38 1179数组的这个可 ... -
集合框架——Map
2010-09-20 15:28 781Map集合为映射 ... -
集合框架——Set
2010-09-20 15:19 821Set集合为集类型,集是最简单的一种集合,存放于集 ... -
集合框架——List
2010-09-20 15:16 1140List集合为列表类型,列表的主要特征是存放其中的 ... -
集合框架——Collection
2010-09-20 15:12 665Collection接口是List接口和Set接口 ... -
Object
2010-09-20 12:09 786java.lang.Object类是所有Java类的最高层次 ... -
Java的7个基础问题
2010-09-20 12:08 545问题一:我声明了什么! Java代码 ... -
堆和栈的区别
2010-09-20 12:06 615栈与堆都是Java用来在Ram中存放数据的地方。 与C++不同 ... -
Comparable和Comparator
2010-09-20 09:22 506public interface Comparable&l ... -
如何使用异常的原则(转)
2010-09-17 15:00 443作者:Bill Venners著,chenkw 译 摘要 ... -
异常的捕获与抛出原则(转)
2010-09-17 14:58 686在可能会出现exception的 ... -
J2EE系统异常的处理准则(转)
2010-09-17 11:43 611J2EE系统异常的处理准则 ... -
J2EE项目的异常处理(转)
2010-09-17 11:18 523为什么要在J2EE项目中谈 ... -
集合框架——简介
2010-09-16 14:46 728一、初识: 集合类是 Java基础技术中十分 ... -
异常那点事
2010-09-16 14:05 603一、概述 在Java程序设计语言中,异常对象都是派生自jav ... -
内部类详解
2010-09-16 13:11 635内部类详解 1、定义 ... -
优化JVM参数提高eclipse运行速度(转)
2010-09-16 12:59 573性能优化从身边做起。 首先建立评估体系,将workspac ... -
四个有害的java编码习惯
2010-09-15 19:16 589John O'Hanley 的这篇文章列举了四个有害的java ...
相关推荐
数据结构最基础,也是很重要的一部分。主要讲述树的算法,结构,及运用。
所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。
(1)以二叉链表作为存储结构,从键盘以先序次序输入各个结点(空格字符表示空树)建立一棵二叉树; (2)对(1)中生成的二叉树进行判空; (3)对(1)中生成的二叉树进行遍历(分别实现先序遍历、中序遍历、后序...
本人是南京航空航天大学的学生,我们的一个计算机软件基础大作业是编写4个程序,分别是约瑟夫斯问题、停车场管理、带权图的最小生成树提取、几种排序算法的比较。希望能够帮助到大家,尤其是南航的学弟学妹们!工程...
本书在简要回顾了基本的C++程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一个...
对某个具体的抽象数据类型,运用课程所学的知识和方法,设计合理的数据结构,并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验,检验所学知识和能力,发现学习中存在的问题。 进而达到熟练地运用本...
本人是南京航空航天大学的学生,我们的一个计算机软件基础大作业是编写4个程序,分别是约瑟夫斯问题、停车场管理、带权图的最小生成树提取、几种排序算法的比较。希望能够帮助到大家,尤其是南航的学弟学妹们!工程...
本人是南京航空航天大学的学生,我们的一个计算机软件基础大作业是编写4个程序,分别是约瑟夫斯问题、停车场管理、带权图的最小生成树提取、几种排序算法的比较。希望能够帮助到大家,尤其是南航的学弟学妹们!工程...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
(1)数据结构与算法概念解析 (2)数据结构之数组 (3)数据结构之栈 (4)数据结构之队列 (5)数据结构之链表 (6)数据结构之二叉树 (7)数据结构之霍夫曼树 (8)数据结构之红黑树(一)——基础分析 ...
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科 背景:应用领域——非数值计算 对 象——具有一定结构的数据 主要问题——对象的特性及对象之间的关系 计算机...
教学提示:前几章介绍了基本数据结构线性表、树和图结构,并讨论了这些结构的存储方式,以及定义在这些结构上的基本运算。本章将讨论数据结构中的另一种常用的重要技术——查找表。在非数值运算中,数据存储量很大,...
本人是南京航空航天大学的学生,我们的一个计算机软件基础大作业是编写4个程序,分别是约瑟夫斯问题、停车场管理、带权图的最小生成树提取、几种排序算法的比较。希望能够帮助到大家,尤其是南航的学弟学妹们!工程...
书中详细介绍了当前流行的论题和新的变化,讨论了算法设计技巧,并在研究算法的性能、效率以及对运行时间分析的基础上考查了一些高级数据结构,从历史的角度和近年的进展对数据结构的活跃领域进行了简要的概括。...
分享一套python版的数据结构算法的视频教程——《零基础征服数据结构算法Python版》,2023年4月完结新课,提供配套的代码和课件下载! 《零基础征服数据结构算法Python版》课程以985院校为授课标准,结合大厂面试所...
C++数据结构与算法,本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾 了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及...
数据结构 —— 代码模板链接 常用代码模板2——数据结构 链表与邻接表:树与图的存储 栈与队列:单调队列、单调栈 kmp Trie 并查集 堆 Hash表 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论 DFS与BFS...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
——加菲劳 《数据结构与算法分析》 ――课程内容体系主要内容 教学单元模块 具体教学内容 绪论 绪论部分是全书的预备知识,主要对ADL语言、数据结构与算法、算法分析基础、OOP、和C++做了简单介绍 基本数据结构 ...