- 浏览: 530708 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
GGGGeek:
看完了博主的博文,如果没猜错的话应该是浙大吧?很多优秀的人因为 ...
转《D君的故事》 以时刻警示自己 -
游牧民族:
楼主写的不错,学习了,最近对爬虫比较感兴趣,也写了些爬虫相关的 ...
通用爬虫框架及heritrix爬虫介绍 -
jimmee:
jerome_s 写道ice 你怎么看? 粗略的看了一下ice ...
MessagePack, Protocol Buffers和Thrift序列化框架原理和比较说明 -
jerome_s:
ice 你怎么看?
MessagePack, Protocol Buffers和Thrift序列化框架原理和比较说明 -
jimmee:
nk_tocean 写道照着做了,但是不行啊,还是乱码.先确认 ...
hive编写udf处理非utf-8数据
3.树的说明
树: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
具体代码实现,可以采用递归的方式实现,也可以采用非递归的方式实现。
递归方式实现(注意,我写的大体过程,具体使用时大家根据实际情况修改一下):
前序遍历:
中序遍历:
后序遍历:
层次遍历:
我前面已经说过,使用递归只不过由系统在为我们维护一个调用栈,我们也可以具体明确的使用堆栈来非递归的实现树的遍历。
非递归实现树的遍历,我们先构建好一棵树,初始化一个栈,之后我们进入一个循环,我们不断弹出堆栈里的元素,直到堆栈为空,如果弹出的树节点表示一棵空树,我们就访问此节点,否则,我们根据下面的规则执行一系列的push操作。
对于前序:压入右子树,然后是左子树,再后是节点
对于中序:压入右子树,然后是节点,再后是左子树
对于后序:压入节点,然后是右子树,再后是左子树
当我们把一个节点的左右节点及本节点都入栈后,我们的节点本身就可以看成一棵空树了。为了标识这一特性,我们修改树节点为:
class TreeNode<E>{
Comparable<E> key;//节点的值
TreeNode<E> llink;//左子树的指针
TreeNode<E> rlink;//右子树的指针
boolean flag;//是否是空树
}
前序遍历的代码:
中序遍历的代码:
后序遍历的代码:
树: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; } } }
发表评论
-
moses安装记录
2016-12-11 11:00 01. moses的安装说明地址(注意,一定要安装好相应的bo ... -
翻译算法
2016-12-09 07:50 0翻译的概率T=argsMaxP(T|S)=P(T)P(S|T ... -
JPEG 简易文档 V2.15【转载】
2016-04-10 16:35 584JPEG 简易文档 V2.15 ------------- ... -
Java 并发之 ConcurrentSkipListMap 简述
2015-09-20 20:24 1082JCIP 提到了在 Java 6 中引入了两个新的并发集合类 ... -
最简单的平衡树(红-黑树)的实现
2015-09-04 08:04 1127在二叉搜索树(BST)的基础上,要实现一颗平衡树,可以使用 ... -
lucene索引创建的理解思路
2014-06-29 23:12 1429虽然lucene4很早就出来,但是这里仍然以lucene3. ... -
lucene的拼写检查的实现原理
2014-06-08 18:19 12751. 建索引时, 使用ngram的方式创建索引 Sp ... -
字符串相似算法-(3) NGram Distance
2014-06-08 17:54 4850就是N-Gram version of edit dista ... -
字符串相似算法-(2) Levenshtein distance
2014-06-08 16:32 2163编辑距离概念描述: ... -
字符串相似算法-(1) Jaro-Winkler Distance
2014-06-08 12:05 6448Jaro-Winkler Distance 算法 ... -
Lucene的数字范围搜索 (Numeric Range Query)原理
2014-04-05 16:08 134920. 全文索引的核心就是倒排索引. 1. 若 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(7)-流量和拥塞控制
2014-04-02 20:53 4098流量控制 对于一个带宽1Gbps, RTT为100ms的网络 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(6)-链接的建立和关闭
2014-04-01 22:47 19611. 模式有client/server mode(客户端, ... -
协议-基于UDP的可靠数据传输协议的实现分析(5)-可靠性怎么保证
2014-03-31 23:08 3738发送方的处理:1) 包发送确认后,由于还没有收到确认,先缓存 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(4)-发送和接收的算法
2014-03-30 10:09 70580. 计时器udt有四种计时器: ACK, NAK, E ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(3)-包结构说明
2014-03-29 17:24 3135udt的包结构1. 数据包,基本结构如下: 0 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(2)-为什么要用udt
2014-03-28 08:00 37170. AIMD算法的简单回顾 (1) 慢开始 ... -
UDT协议-基于UDP的可靠数据传输协议的实现分析(1)-准备工作
2014-03-27 12:52 37601. 协议实现方案: Yunhong Gu提出的rfc的草 ... -
mapreduce的一些算法设计,优化等(2)
2014-01-28 15:50 14171. 反序(order inversion ... -
mapreduce的一些算法设计,优化等(1)
2014-01-27 17:15 2026本系列是根据书籍《Da ...
相关推荐
作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和...
作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和...
第一部分:数据结构与算法的基本概念 考核内容: 算法、算法正确性、复杂性; 算法的时间与空间复杂性级别; 数据类型、数据结构和表示、实现; 抽象数据类型的说明、高级语言对抽象数据类型的支持 考核要求: 理解...
串基本操作演示代码加报告,报告里面有使用说明书
基于C语言实现的基本数据结构定义以及简单的解题应用项目源码.zip基于C语言实现的基本数据结构定义以及简单的解题应用项目源码.zip基于C语言实现的基本数据结构定义以及简单的解题应用项目源码.zip基于C语言实现的...
数据结构课程设计,本课程设计是为了配合《数据结构》课程的开设,通过设计一完整的程序,使学生能达到如下要求: 1. 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; 2. 初步掌握软件开发过程...
数据结构与算法分析,主要包括最基本的说明和基本算法举例说明.
包括习题与答案及要点,很实用啊 ... 数据结构的定义虽然没有标准,但是它包括以下三方面内容:逻辑结构、存储结构、和对数据的操作。这一段比较重要,我用自己的语言来说明一下,大家看看是不是这样。
数据结构与算法分析 经典笔记学习笔记 1 前言 1.1 所选教材 1.2 写作原因 1.3 一些约定 1.4 历史记录 1.5 联系方式 2 单链表 2.1 代码实现 2.2 效率问题 2.3 应用:一元多项式(加法和乘法) 2.3.1 基础知识 2.3.2 ...
JAVA实现链表 有序二叉树 队列的代码例子
数据结构形成了程序员基本数据结构工具箱(toolkit)。对于许多常见的问题,工 具箱里的数据结构是理想的选择。就像.NET Framework 中Windows应用程序开 发中的工具箱,程序员可以直接拿来或经过少许的修改就可以使用...
数据结构具体指同一类数据元素中,各元素之间的相互关系,包括三个组成成分,数 据的逻辑结构,数据的存储结构和数据运算结构。 1.1. 重要意义 一般认为,一个数据结构是由数据元素依据某种逻辑联系组织起来的。对...
一、基本概念和术语 数据(Data) 数据是信息的载体。它能够被计算机识别、存储和加工处理,是计算机程序加工...为了增加对数据结构的感性认识,下面举例来说明有关数据结构的概念。 【例1.1】 学生成绩表,见下表。
(3) 录入:可以录入航班情况(数据可以存储在一个数据文件中,数据结构、具体数据自定) (4) 查询:可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达城市,航班票价,票价折扣,确定航班是否满...
全书内容浅显易懂,利用大量且丰富的图示与范例, 详解复杂的抽象理论,从最基本的数据结构概念开始 说明,再以Java工具加以诠释阵列结构、堆栈、链表 、队列、排序、查找等重要的概念,引领读者抓住重 点轻松进入...
《数据结构》课程第三次实验报告 实验报告(三) "姓名 " "学号 " "班级 " " "实验名称 "顺序栈的基本操作 "实验日期 " "机房 " " "实验报告 " "1. 说明自己在实验操作过程中遇到的难点及解决方法 " "难点: " "1....
它基本上涉及了数据结构基础的“方方面面”。很难想象这书的厚度,居然能讲这么多内容(你看看算法导论有多厚就知道我在说什么了)。 它在内容上并不乏深度。高级数据结构部分并不容易,如果你第一次就全部耐心看完...
天健医疗HIS系统的数据库表结构说明,再数据分析时可以帮助不了解的数据结构的工程师,快速的了解详细的数据情况。
在无法使用二叉查找树的时候,这三种数据结构证明对查找是很有用的。他们是:AVL树、红黑树和跳跃表。 第16章讨论了图以及图的算法。图在表示许多不同的数据类型时非常有用,特别是网络的情况。最后,第17章向读者...
2.4.3 三种基本结构和改进的流程图 28 2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 ...