【数据结构与算法】【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);
	    }
	}

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

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