- 浏览: 12903 次
- 性别:
- 来自: 上海
文章分类
最新评论
最近一段时间,公司项目上要对另外一个项目进行项目整合,由于业务上的差异,之前系统中的一些数据储存结构已经不在适用于现在的技术体系,为此,花了一段时间来研究一下数据结构。
做下总结:
一、数据结构分类
(A)按逻辑结构
- 集合(无辑关系)
- 线性结构(也就是常说的线性表): 数组, 链表,栈,队列.
- 非线性结构:树、图、多维数组
顺序(数组)储结构、链式储结构、索引储结构、散列储结构 . 遍历是按某种策略访问树中的每个节点,且仅访问一次。 (A)按存储结构
二、二叉树相关性质
三、二叉树的遍历
(一) 二叉树结构实现
package tree.bintree;
/**
* 创建 非完全二叉树、完全二叉树、满二叉树
*
* 由于二叉树的节点增加没有什么规则,所以这里只是简单的使用了递一
* 次性把整棵树创建出来,而没有设计出一个一个添加节点的方法与删除
*
* @author jzj
* @date 2009-12-23
*/
public class BinTree {// Bin=Binary(二进位的, 二元的)
protected Entry root;//根
private int size;//树的节点数
/**
* 树的节点结构
* @author jzj
* @date 2009-12-23
*/
protected static class Entry {
int elem;//数据域,这里我们作为编号
Entry left;//左子树
Entry right;//右子树
public Entry(int elem) {
this.elem = elem;
}
public String toString() {
return " number=" + elem;
}
}
/**
* 根据给定的节点数创建一个完全二叉树或是满二叉树
* @param nodeCount 要创建节点总数
*/
public void createFullBiTree(int nodeCount) {
root = recurCreateFullBiTree(1, nodeCount);
}
/**
* 递归创建完全二叉树
* @param num 节点编号
* @param nodeCount 节点总数
* @return TreeNode 返回创建的节点
*/
private Entry recurCreateFullBiTree(int num, int nodeCount) {
size++;
Entry rootNode = new Entry(num);//根节点
//如果有左子树则创建左子树
if (num * 2 <= nodeCount) {
rootNode.left = recurCreateFullBiTree(num * 2, nodeCount);
//如果还可以创建右子树,则创建
if (num * 2 + 1 <= nodeCount) {
rootNode.right = recurCreateFullBiTree(num * 2 + 1, nodeCount);
}
}
return (Entry) rootNode;
}
/**
* 根据给定的数组创建一棵树,这个棵树可以是完全二叉树也可是普通二叉树
* 数组中为0的表示不创建该位置上的节点
* @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建
*/
public void createBinTree(int[] nums) {
root = recurCreateBinTree(nums, 0);
}
/**
* 递归创建二叉树
* @param nums 数组中指定了要创建的节点的编号,如果为0,表示不创建
* @param index 需要使用数组中的哪个元素创建节点,如果为元素为0,则不创建
* @return TreeNode 返回创建的节点,最终会返回树的根节点
*/
private Entry recurCreateBinTree(int[] nums, int index) {
//指定索引上的编号不为零上才需创建节点
if (nums[index] != 0) {
size++;
Entry rootNode = new Entry(nums[index]);//根节点
//如果有左子树则创建左子树
if ((index + 1) * 2 <= nums.length) {
rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1);
//如果还可以创建右子树,则创建
if ((index + 1) * 2 + 1 <= nums.length) {
rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1) * 2);
}
}
return (Entry) rootNode;
}
return null;
}
public int size() {
return size;
}
//取树的最左边的节点
public int getLast() {
Entry e = root;
while (e.right != null) {
e = e.right;
}
return e.elem;
}
//测试
public static void main(String[] args) {
//创建一个满二叉树
BinTree binTree = new BinTree();
binTree.createFullBiTree(15);
System.out.println(binTree.size());//15
System.out.println(binTree.getLast());//15
//创建一个完全二叉树
binTree = new BinTree();
binTree.createFullBiTree(14);
System.out.println(binTree.size());//14
System.out.println(binTree.getLast());//7
//创建一棵非完全二叉树
binTree = new BinTree();
int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };
binTree.createBinTree(nums);
System.out.println(binTree.size());//8
System.out.println(binTree.getLast());//8
}
}
(二)利用二叉树本身特点进行递归遍历(属内部遍历)
由于二叉树所具有的递归性质,一棵非空的二叉树可以看作是由根节点、左子树和右子树3部分构成,因为若能依次遍历这3部分的信息,也就遍历了整个二叉树。按照左子树的遍历在右子树的遍历之前进行的约定,根据访问根节点位置的不同,可以得到二叉的前序、中序、后序3种遍历方法。
package tree.bintree;
/**
* 二叉树的三种 内部 遍历:前序、中序、后序
* 但不管是哪种方式,左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都
* 必须遵循的约定
* @author jzj
* @date 2009-12-23
*/
public class BinTreeInOrder extends BinTree {
/**
* 节点访问者,可根据需要重写visit方法
*/
static abstract class Visitor {
void visit(Object ele) {
System.out.print(ele + " ");
}
}
public void preOrder(Visitor v) {
preOrder(v, root);
}
/**
* 树的前序递归遍历 pre=prefix(前缀)
* @param node 要遍历的节点
*/
private void preOrder(Visitor v, Entry node) {
//如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null
if (node != null) {
v.visit(node.elem);//先遍历父节点
preOrder(v, node.left);//再遍历左节点
preOrder(v, node.right);//最后遍历右节点
}
}
public void inOrder(Visitor v) {
inOrder(v, root);
}
/**
* 树的中序递归遍历 in=infix(中缀)
* @param node 要遍历的节点
*/
private void inOrder(Visitor v, Entry node) {
//如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null
if (node != null) {
inOrder(v, node.left);//先遍历左节点
v.visit(node.elem);//再遍历父节点
inOrder(v, node.right);//最后遍历右节点
}
}
public void postOrder(Visitor v) {
postOrder(v, root);
}
/**
* 树的后序递归遍历 post=postfix(后缀)
* @param node 要遍历的节点
*/
private void postOrder(Visitor v, Entry node) {
//如果传进来的节点不为空,则遍历,注,叶子节点的子节点为null
if (node != null) {
postOrder(v, node.left);//先遍历左节点
postOrder(v, node.right);//再遍历右节点
v.visit(node.elem);//最后遍历父节点
}
}
//测试
public static void main(String[] args) {
//创建二叉树
int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };
BinTreeInOrder treeOrder = new BinTreeInOrder();
treeOrder.createBinTree(nums);
System.out.print("前序遍历 - ");
treeOrder.preOrder(new Visitor() {
});
System.out.println();
System.out.print("中序遍历 - ");
treeOrder.inOrder(new Visitor() {
});
System.out.println();
System.out.print("后序遍历 - ");
treeOrder.postOrder(new Visitor() {
});
/*
* output:
* 前序遍历 - 1 2 4 6 3 5 7 8
* 中序遍历 - 4 6 2 1 3 7 5 8
* 后序遍历 - 6 4 2 7 8 5 3 1
*/
}
}
(三)二叉树的非递归遍历(属外部遍历)
1、利用栈与队列对二叉树进行非递归遍历
package tree.bintree; import java.util.Iterator; import java.util.LinkedList; import java.util.Stack; /** * 二叉树的外部遍历:深度优先(先根)、广度(层次)优先遍历 * * @author jzj * @date 2009-12-23 */ public class BinTreeOutOrder extends BinTree { /** * 二叉树深序优先遍历(即二叉树的先根遍历)迭代器,外部可以使用该迭代器 * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用 * 二叉树本身的结构特点(左右子树递归)进行递归遍历 * @author jzj */ private class DepthOrderIterator implements Iterator { //栈里存放的是每个节点 private Stack stack = new Stack(); public DepthOrderIterator(Entry node) { //根入栈,但在放入左右子节点前会马上出栈,即根先优于左右子节点访问 stack.push(node); } //是否还有下一个元素 public boolean hasNext() { if (stack.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶元素 Entry treeNode = (Entry) stack.pop();//先访问根 if (treeNode.right != null) { stack.push(treeNode.right);//再放入右子节点 } if (treeNode.left != null) { stack.push(treeNode.left);//最后放入左子节点,但访问先于右节点 } // 返回遍历得到的节点 return treeNode; } else { // 如果栈为空 return null; } } public void remove() { throw new UnsupportedOperationException(); } } /** * 向外界提供先根遍历迭代器 * @return Iterator 返回先根遍历迭代器 */ public Iterator createPreOrderItr() { return new DepthOrderIterator(root); } /** * 二叉树广度优先遍历迭代器,外部可以使用该迭代器 * 进行非递归的遍历,这是一种在二叉树结构外部的一种遍历算法,它没有使用 * 二叉树本身的结构特点(左右子树递归)进行递归遍历 * @author jzj */ private class LevelOrderIterator implements Iterator { //使用队列结构实现层次遍历,队列里存储的为节点 private LinkedList queue = new LinkedList(); public LevelOrderIterator(Entry node) { if (node != null) { //将根入队 queue.addLast(node); } } //是否还有下一个元素 public boolean hasNext() { if (queue.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶迭元素 Entry treeNode = (Entry) queue.removeFirst(); if (treeNode.left != null) {//如果有左子树,加入有序列表中 queue.addLast(treeNode.left); } if (treeNode.right != null) {//如果有右子树,加入有序列表中 queue.addLast(treeNode.right); } // 返回遍历得到的节点 return treeNode; } else { // 如果队列为空 return null; } } public void remove() { throw new UnsupportedOperationException(); } } /** * 向外界提供广度优先迭代器 * @return Iterator 返回遍历迭代器 */ public Iterator createLayerOrderItr() { return new LevelOrderIterator(root); } public static void main(String[] args) { //创建一棵满二叉树 BinTreeOutOrder treeOrder = new BinTreeOutOrder(); treeOrder.createFullBiTree(15); Iterator preOrderItr = treeOrder.createPreOrderItr(); System.out.print("深度优先(先根)遍历 - "); while (preOrderItr.hasNext()) { System.out.print(((Entry) preOrderItr.next()).elem + " "); } System.out.println(); System.out.print("广度优先(层次)遍历 - "); Iterator layerOrderItr = treeOrder.createLayerOrderItr(); while (layerOrderItr.hasNext()) { System.out.print(((Entry) layerOrderItr.next()).elem + " "); } /* * output: * 深度优先(先根)遍历 - 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 * 广度优先(层次)遍历 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 */ } }
2、利用二叉树节点的父节点指针进行非递归遍历
要想采用非递归的方法遍历树,又不借助于前面的队列与栈,我们需要该树是一棵可回溯的二叉树,即从子节点要能够知道他的父节点及祖先节点,与前面的二叉树不同的是,树的节点结构体中多一个指向父的节点指针,这样外界可以以非递归的方式来遍历二叉树了。
发表评论
-
Java GC
2011-03-10 17:38 1170JVM学习笔记之JVM内存管 ... -
java字符串操作
2011-02-26 13:20 648String、StringBuffer和StringBul ... -
java 垃圾回收器的理解
2011-02-24 23:12 639Java语言具备GC(垃圾 ... -
Java 垃圾回收器的概念
2011-02-24 23:07 767内存管理和垃圾回收 ... -
spirng mvc
2010-09-15 23:29 1509Spring的Web MVC框架是围绕DispatcherSe ... -
java io的性能调整
2010-09-12 22:27 722本文大多技术围绕调整磁盘文件 I/O,但是有些内容也同样适合网 ... -
java io的总结之二
2010-09-12 22:16 501java中的io中的(input/output)stream无 ... -
java io的总结之一
2010-09-12 22:11 575知识点一: 四大等级结构 java语言的i/o库提供了 ...
相关推荐
基于java实现tree的数据结构和算法
关于Java的一个树结构,类似于本论坛左侧的样式,对初学者有一定的帮助
NULL 博文链接:https://xgw123485.iteye.com/blog/1160924
NULL 博文链接:https://jun1986.iteye.com/blog/1144751
Java Tree 导航栏 java类源码
NULL 博文链接:https://n040661.iteye.com/blog/1849909
很好用的java tree控件,适合JSP开发使用
javaTree的一个例子 很实用 需要的可以下载看看
简单java tree 比较简单的demo,无限极菜单
java中tree的实现,更简单,更易懂。。。。。。。
SR-tree realization on Java
b/s下jsp+javabean实现从数据库中读取数据生成目录树
源程序(包括最初的版本,XP过程的版本,最后版本)都放在了课设版本包中。 要运行程序见运行和使用说明文档。
一个XML文档容器,不需要复杂的js tree来实现
java 树 tree
tree example WebDynpro Java
部门组织显示开发,从jsp到后台java都有详细解析,同时提供有相关的js。开发内容简单,适合初学者和忘记部门树开发者。
Jsp XML树状菜单类库开发代码Jsp XML tree menu code library development
该项目旨在提供可扩展的Tree接口,以补充Java Collections框架,从而充分利用Java 5泛型。 作为该项目范围的一部分,将至少提供一个参考实现。
java中List结构与tree结构相互转化。可实现list转树与tree转list。本链接为解读https://jingyan.baidu.com/article/455a99507b687da1662778ec.html。