栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【数据结构与算法】【10】数据结构之树

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【数据结构与算法】【10】数据结构之树

树结构

树是一种嵌套型结构,用来表达上下级和归属关系

每个树节点可以拥有若干个下级节点,并且下级节点的结构和上级节点的结构完全相同,可以再拥有自己的下级


树的分类

根据树节点分支数量可分为

  • 二叉树,每个节点最多只有两个子节点
  • 多叉树,每个节点可以有两个以上的子节点

根据树节点上数值的有序性可分为

  • 查找树,也叫搜索树,这种树规定,父节点上的值,必须大于等于左孩子,小于等于右孩子
  • 无序树,节点上的值无大小顺序要求

根据树节点的对称性可分为

  • 平衡树,任意节点的所有子树高度,最多相差1
  • 非平衡树,子树高度无要求

根据树的整体结构特征,还有这样一些特殊的树

  • 完美树,树的每一层,节点都铺满,没有任何空位
  • 完全树,比完全树要求稍微低一点,除了树的最后一层,其它层节点全部铺满,并且所有节点从左往右排列
  • 满树,树的所有节点,要么没有子节点,要么子节点铺满

树的代码实现

树的代码实现比较简单,每个节点包含一个链表,用链表来存储子节点就行了

	import java.util.LinkedList;
	import java.util.List;
	import java.util.Objects;
	
	@SuppressWarnings("all")
	public class TreeNode {
	
	    //树深度
	    public Integer depth = 0;
	
	    //数值
	    public T data = null;
	
	    //添加transient关键字,是告诉JSON等序列化功能,在序列化时忽略此字段
	    //父节点包含子节点,字节点也包含父节点,对象之间相互循环引用,会导致序列化时产生死循环
	    //可以通过transient来忽略parentNode字段,通过parentId来查找
	    public transient TreeNode parent;
	    public final LinkedList children = new LinkedList();
	
	    //添加子节点
	    public void add(TreeNode child) {
	        child.parent = this;
	        child.depth = depth + 1;
	        children.addLast(child);
	    }
	
	    //移除子节点
	    public void remove(TreeNode child) {
	        child.parent = null;
	        child.depth = null;
	        children.remove(child);
	    }
	
	    //添加子节点
	    public void add(T data) {
	        TreeNode child = new TreeNode();
	        child.data = data;
	        child.parent = this;
	        child.depth = depth + 1;
	        children.addLast(child);
	    }
	
	    //移除子节点
	    public void remove(T data) {
	        List deleteNodes = new LinkedList();
	        for (TreeNode child : children)
	            if (Objects.equals(child.data, data)) {
	                child.parent = null;
	                child.depth = null;
	                deleteNodes.add(child);
	            }
	        children.removeAll(deleteNodes);
	    }
	
	    //打印当前子树
	    @Override
	    public String toString() {
	        String childDescription = "";
	        if (!children.isEmpty()) {
	            childDescription = childDescription + "(";
	            for (TreeNode child : children)
	                childDescription = childDescription + child.data;
	            childDescription = childDescription + ")";
	        }
	        return data + childDescription;
	    }
	
	    public static void main(String[] args) {
	        TreeNode tree = new TreeNode();
	        tree.data = "S";
	        tree.add("A");
	        tree.add("B");
	        tree.add("C");
	        tree.add("D");
	        tree.add("C");
	        tree.add("C");
	        tree.add("C");
	        tree.remove("C");
	        TreeNode child = new TreeNode();
	        child.data = "C";
	        tree.add(child);
	        System.out.println(tree);
	    }
	}

树是一种非常实用和强大的数据结构,本章讲的只是最基本的存储功能

后面会讲解更专业的特殊树结构,还有树的遍历排序查找等算法

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936178.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号