java数据结构之树基本概念解析及代码示例

Java中树的存储结构实现 一、树 树与线性表、栈、队列等线性结构不同,树是一...节点与节点之间的父子关系,可以为每个节点增加一个parent域,用以记录该节点的父点

树是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把 它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

树定义和基本术语

定义

树(Tree)是n(n≥0)个结点的有限集T,并且当n>0时满足下列条件:

(1)有且仅有一个特定的称为根(Root)的结点;

(2)当n>1时,其余结点可以划分为m(m>0)个互不相交的有限集T1、T2、…、Tm,每个集Ti(1≤i≤m)均为树,且称为树T的子树(SubTree)。

特别地,不含任何结点(即n=0)的树,称为空树。

如下就是一棵树的结构:

基本术语

结点:存储数据元素和指向子树的链接,由数据元素和构造数据元素之间关系的引用组成。
孩子结点:树中一个结点的子树的根结点称为这个结点的孩子结点,如图1中的A的孩子结点有B、C、D
双亲结点:树中某个结点有孩子结点(即该结点的度不为0),该结点称为它孩子结点的双亲结点,也叫前驱结点。双亲结点和孩子结点是相互的,如图1中,A的孩子结点是B、C、D,B、C、D的双亲结点是A。
兄弟结点:具有相同双亲结点(即同一个前驱)的结点称为兄弟结点,如图1中B、B、D为兄弟结点。
结点的度:结点所有子树的个数称为该结点的度,如图1,A的度为3,B的度为2.
树的度:树中所有结点的度的最大值称为树的度,如图1的度为3.
叶子结点:度为0的结点称为叶子结点,也叫终端结点。如图1的K、L、F、G、M、I、J
分支结点:度不为0的结点称为分支结点,也叫非终端结点。如图1的A、B、C、D、E、H
结点的层次:从根结点到树中某结点所经路径的分支数称为该结点的层次。根结点的层次一般为1(也可以自己定义为0),这样,其它结点的层次是其双亲结点的层次加1.
树的深度:树中所有结点的层次的最大值称为该树的深度(也就是最下面那个结点的层次)。
有序树和无序树:树中任意一个结点的各子树按从左到右是有序的,称为有序树,否则称为无序树。
树的抽象数据类型描述
数据元素:具有相同特性的数据元素的集合。
结构关系:树中数据元素间的结构关系由树的定义确定。

基本操作:树的主要操作有

(1)创建树IntTree(&T)
         创建1个空树T。
(2)销毁树DestroyTree(&T)
(3)构造树CreatTree(&T,deinition)
(4)置空树ClearTree(&T)
          将树T置为空树。
(5)判空树TreeEmpty(T)
(6)求树的深度TreeDepth(T)
(7)获得树根Root(T)
(8)获取结点Value(T,cur_e,&e)
         将树中结点cur_e存入e单元中。
(9)数据赋值Assign(T,cur_e,value)
         将结点value,赋值于树T的结点cur_e中。
(10)获得双亲Parent(T,cur_e)
        返回树T中结点cur_e的双亲结点。
(11)获得最左孩子LeftChild(T,cur_e)
        返回树T中结点cur_e的最左孩子。
(12)获得右兄弟RightSibling(T,cur_e)
        返回树T中结点cur_e的右兄弟。
(13)插入子树InsertChild(&T,&p,i,c)
      将树c插入到树T中p指向结点的第i个子树之前。
(14)删除子树DeleteChild(&T,&p,i)
       删除树T中p指向结点的第i个子树。
(15)遍历树TraverseTree(T,visit())

树的实现

树是一种递归结构,表示方式一般有孩子表示法和孩子兄弟表示法两种。树实现方式有很多种、有可以由广义表的递归实现,也可以有二叉树实现,其中最常见的是将树用孩子兄弟表示法转化成二叉树来实现。

下面以孩子表示法为例讲一下树的实现:

树的定义和实现

package datastructure.tree;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
   * 树的定义和实现
   * @author Administrator
   *
   */
public class Tree {
	private Object data;
	private List<Tree> childs;
	public Tree(){
		data = null;
		childs = new ArrayList();
		childs.clear();
	}
	public Tree(Object data) {
		this.data = data;
		childs = new ArrayList();
		childs.clear();
	}
	/**
     * 添加子树
     * @param tree 子树
     */
	public void addNode(Tree tree) {
		childs.add(tree);
	}
	/**
     * 置空树
     */
	public void clearTree() {
		data = null;
		childs.clear();
	}
	/**
     * 求树的深度
     * 这方法还有点问题,有待完善
     * @return 树的深度
     */
	public int dept() {
		return dept(this);
	}
	/**
     * 求树的深度
     * 这方法还有点问题,有待完善
     * @param tree
     * @return
     */
	private int dept(Tree tree) {
		if(tree.isEmpty()) {
			return 0;
		} else if(tree.isLeaf()) {
			return 1;
		} else {
			int n = childs.size();
			int[] a = new int[n];
			for (int i=0; i<n; i++) {
				if(childs.get(i).isEmpty()) {
					a[i] = 0+1;
				} else {
					a[i] = dept(childs.get(i)) + 1;
				}
			}
			Arrays.sort(a);
			return a[n-1];
		}
	}
	/**
     * 返回递i个子树
     * @param i
     * @return
     */
	public Tree getChild(int i) {
		return childs.get(i);
	}
	/**
     * 求第一个孩子 结点
     * @return
     */
	public Tree getFirstChild() {
		return childs.get(0);
	}
	/**
     * 求最后 一个孩子结点
     * @return
     */
	public Tree getLastChild() {
		return childs.get(childs.size()-1);
	}
	public List<Tree> getChilds() {
		return childs;
	}
	/**
     * 获得根结点的数据
     * @return
     */
	public Object getRootData() {
		return data;
	}
	/**
     * 判断是否为空树
     * @return 如果为空,返回true,否则返回false
     */
	public Boolean isEmpty() {
		if(childs.isEmpty() && data == null)
		        return true;
		return false;
	}
	/**
     * 判断是否为叶子结点
     * @return
     */
	public Boolean isLeaf() {
		if(childs.isEmpty())
		        return true;
		return false;
	}
	/**
     * 获得树根
     * @return 树的根
     */
	public Tree root() {
		return this;
	}
	/**
     * 设置根结点的数据
     */
	public void setRootData(Object data) {
		this.data = data;
	}
	/**
     * 求结点数
     * 这方法还有点问题,有待完善
     * @return 结点的个数
     */
	public int size() {
		return size(this);
	}
	/**
     * 求结点数
     * 这方法还有点问题,有待完善
     * @param tree
     * @return
     */
	private int size(Tree tree) {
		if(tree.isEmpty()) {
			return 0;
		} else if(tree.isLeaf()) {
			return 1;
		} else {
			int count = 1;
			int n = childs.size();
			for (int i=0; i<n; i++) {
				if(!childs.get(i).isEmpty()) {
					count += size(childs.get(i));
				}
			}
			return count;
		}
	}
}

树的遍历

树的遍历有两种

前根遍历

(1).访问根结点;

(2).按照从左到右的次序行根遍历根结点的第一棵子树;

后根遍历

(1).按照从左到右的次序行根遍历根结点的第一棵子树;

(2).访问根结点;

Visit.Java

package datastructure.tree;
import datastructure.tree.btree.BTree;
/**
   * 对结点进行操作的接口,规定树的遍历的类必须实现这个接口
   * @author Administrator
   *
   */
public interface Visit {
	/**
     * 对结点进行某种操作
     * @param btree 树的结点
     */
	public void visit(BTree btree);
}

order.java

package datastructure.tree;
import java.util.List;
/**
   * 树的遍历
   * @author Administrator
   *
   */
public class Order {
	/**
     * 先根遍历
     * @param root 要的根结点
     */
	public void preOrder(Tree root) {
		if(!root.isEmpty()) {
			visit(root);
			for (Tree child : root.getChilds()) {
				if(child != null) {
					preOrder(child);
				}
			}
		}
	}
	/**
     * 后根遍历
     * @param root 树的根结点
     */
	public void postOrder(Tree root) {
		if(!root.isEmpty()) {
			for (Tree child : root.getChilds()) {
				if(child != null) {
					preOrder(child);
				}
			}
			visit(root);
		}
	}
	public void visit(Tree tree) {
		System.out.print("\t" + tree.getRootData());
	}
}

测试:

要遍历的树如下:

package datastructure.tree;
import java.util.Iterator;
import java.util.Scanner;
public class TreeTest {
	/**
     * @param args
     */
	public static void main(String[] args) {
		Tree root = new Tree("A");
		root.addNode(new Tree("B"));
		root.addNode(new Tree("C"));
		root.addNode(new Tree("D"));
		Tree t = null;
		t = root.getChild(0);
		t.addNode(new Tree("L"));
		t.addNode(new Tree("E"));
		t = root.getChild(1);
		t.addNode(new Tree("F"));
		t = root.getChild(2);
		t.addNode(new Tree("I"));
		t.addNode(new Tree("H"));
		t = t.getFirstChild();
		t.addNode(new Tree("L"));
		System.out.println("first node:" + root.getRootData());
		//System.out.println("size:" + root.size());
		//System.out.println("dept:" + root.dept());
		System.out.println("is left:" + root.isLeaf());
		System.out.println("data:" + root.getRootData());
		Order order = new Order();
		System.out.println("前根遍历:");
		order.preOrder(root);
		System.out.println("\n后根遍历:");
		order.postOrder(root);
	}
}

结果:

first node:A
is left:false
data:A
前根遍历:
A BL E C F DI L H
后根遍历:
B LE C F D IL H A

结束语:

以上就是本文关于java数据结构之树基本概念解析及代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:

Java编程求二叉树的镜像两种方法介绍

java算法实现红黑树完整代码示例

java实现遍历树形菜单两种实现代码分享

如有不足之处,欢迎留言指出。

(0)

相关推荐

  • Java数据结构与算法之树(动力节点java学院整理)

    为什么使用树: 树结合了两种数据结构的有点:一种是有序数组,树在查找数据项的速度和在有序数组中查找一样快:另一种是链表,树在插入数据和删除数据项的速度和链表一样.既然这样,就要好好去学了.... (最主要讨论的是二叉树中的二叉搜索树,即一个节点的左子节点关键值小于这个节点,右子节点的关键值大于这个节点) 设计前的思考: 树-->元素(节点) class Node { public int iData ; public float fData ; public Node left ; public

  • java 数据结构二叉树的实现代码

    1. 二叉树接口 public interface BinaryTreeInterface<T> { public T getRootData(); public int getHeight(); public int getNumberOfRoot(); public void clear(); public void setTree(T rootData); // 用rootData设置树 public void setTree(T rootData,BinaryTreeInterface

  • Java中二叉树数据结构的实现示例

    来看一个具体的习题实践: 题目 根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序.中序.后序进行遍历 代码 import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public Str

  • java数据结构排序算法之树形选择排序详解

    本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进

  • Java数据结构之红黑树的真正理解

    真正的帮助大家理解红黑树: 一.红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储 红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树 二叉树-->搜索二叉树-->平衡搜索二叉树--> 红黑树 从N阶树看,红黑树就是一颗 2-3-4树 N阶树-->B(B-)树 故我提取出了红黑树部分的源码,去说明红黑树的理解 看之前,理解红黑树的几个特性,后面的操作都是为了让树符合红黑树的这几个特性,从而满足对查找效率的O

  • java数据结构之树基本概念解析及代码示例

    Java中树的存储结构实现 一.树 树与线性表.栈.队列等线性结构不同,树是一...节点与节点之间的父子关系,可以为每个节点增加一个parent域,用以记录该节点的父点 树是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点组成一个具有层次关系的集合.把 它叫做"树"是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的. 树定义和基本术语 定义 树(Tree)是n(n≥0)个结点的有限集T,并且当

  • Java 数据结构之堆的概念与应用

    目录 什么是堆 堆的类型 小根堆 大根堆 堆的基本操作:创建堆 堆的时间复杂度和空间复杂度 堆的应用-优先级队列 概念 优先级队列基本操作 入优先级队列 出优先级队列首元素 java的优先级队列 堆的常见面试题 最后一块石头的重量 找到K个最接近的元素 查找和最小的K对数字 java数据结构的堆 什么是堆 堆指的是使用数组保存完全二叉树结构,以层次遍历的方式放入数组中. 如图: 注意:堆方式适合于完全二叉树,对于非完全二叉树若使用堆则会造成空间的浪费 对于根节点与其左右孩子在数组中的下标关系可表

  • 数据结构之树的概念详解

    数据结构树简介 一.树简介 树(Tree)是一种抽象的数据结构,是一个数据的集合,集合中的数据组成了一个树状结构.例如上图,看起来像一棵倒挂的树,根朝上叶朝下. 树是由n(n>=0)个节点组成的具有层次关系的数据集合.当 n=0 时,树中没有节点,称为空树.当 n>0 时,有且仅有一个节点被称为根节点(Root),如果 n=1 ,树只有根节点一个节点.如果 n>1 ,除根节点外,将其余的节点分成m(m>0)个互不相交的数据集合,这 m 个集合每一个都要满足树的结构(有且仅有一个根节

  • Python 数据结构之树的概念详解

    数据结构树简介 一.树简介 树(Tree)是一种抽象的数据结构,是一个数据的集合,集合中的数据组成了一个树状结构.例如上图,看起来像一棵倒挂的树,根朝上叶朝下. 树是由n(n>=0)个节点组成的具有层次关系的数据集合.当 n=0 时,树中没有节点,称为空树.当 n>0 时,有且仅有一个节点被称为根节点(Root),如果 n=1 ,树只有根节点一个节点.如果 n>1 ,除根节点外,将其余的节点分成m(m>0)个互不相交的数据集合,这 m 个集合每一个都要满足树的结构(有且仅有一个根节

  • Java数据结构之KMP算法详解以及代码实现

    目录 暴力匹配算法(Brute-Force,BF) 概念和原理 next数组 KMP匹配 KMP全匹配 总结 我们此前学了前缀树Trie的实现原理以及Java代码的实现.Trie树很好,但是它只能基于前缀匹配实现功能.但是如果我们的需求是:一个已知字符串中查找子串,并且子串并不一定符合前缀匹配,那么此时Trie树就无能为力了. 实际上这种字符串匹配的需求,在开发中非常常见,例如判断一个字符串是否包括某些子串,然后进行分别的处理. 暴力匹配算法(Brute-Force,BF) 这是最常见的算法字符

  • java多线程编程同步器Future和FutureTask解析及代码示例

    publicinterfaceFuture<V>Future表示异步计算的结果.它提供了检查计算是否完成的方法,以等待计算的完成,并获取计算的结果.计算完成后只能使用get方法来获取结果,如有必要,计算完成前可以阻塞此方法.取消则由cancel方法来执行.还提供了其他方法,以确定任务是正常完成还是被取消了.一旦计算完成,就不能再取消计算.如果为了可取消性而使用Future但又不提供可用的结果,则可以声明Future<?>形式类型.并返回null作为底层任务的结果. Future主要

  • Java语言字典序排序算法解析及代码示例

    字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的

  • 关于java中@Async异步调用详细解析附代码

    目录 前言 1. @Async讲解 2. 用法 2.1 同步调用 2.2 异步调用 3. 自定义线程池 前言 异步调用与同步调用 同步调用:顺序执行,通过调用返回结果再次执行下一个调用 异步调用:通过调用,无需等待返回结果,执行下一个调用 1. @Async讲解 其@Async的注解代码如下: @Target({ElementType.TYPE, ElementType.METHOD}) @Retention(RetentionPolicy.RUNTIME) @Documented public

  • Java编程Iterator迭代器设计原理及实现代码示例

    我们知道迭代器(Iterator)是一种对象,它能够用来遍历标准模板库容器中的部分或全部元素.那么Iterator迭代器的设计原理是什么呢?迭代器问什么定义了一个借口,而不是一个类呢? 我们假设迭代器迭代数据的功能定义为了一个类,那么,会有这样的问题.不同的集合,由于数据结构不一样,所以他们的存储方式也是不一样的.也就是说,迭代器获取的时候,获取的方式是变化的,也就是不固定的.所以把这种方式定义为具体的实现是不合理的. 无论何种集合,他们肯定都有获取的功能,而且不知道什么时候就没有数据了.所有他

  • Java编程小实例—数字时钟的实现代码示例

    本文的实例是Java编程实现一个数字时钟,代码测试可用,练练手吧.代码如下: package me.socketthread; import java.awt.Color; import java.awt.Dimension; import java.awt.Font; import java.awt.Graphics; import java.awt.Graphics2D; import java.util.Calendar; import java.util.GregorianCalenda

随机推荐