1.树形结构的介绍

 * 树形结构简介
 * 树形结构是一种非线性结构，存储的是“一对多的”关系的数据元素的集合
 *
 * 树形结构的相关术语：
 * 节点（Node）：使用树结构存储的每一个数据元素都被称为“节点”
 * 节点的度（Degree of Node）：某个节点所拥有的子树的个数
 * 树的深度（Degree of Tree）：树中节点的最大层数
 * 叶子节点（Leaf Node）：度为0的节点，也叫终端节点
 * 分支节点（Branch Node）：度不为0的节点，也叫非终端节点或内部节点
 * 孩子（child）：也可称之为子树或子节点，表示当前节点下层的直接节点
 * 双亲（parent）：也可称为父节点，表示当前节点的直接上层节点
 * 根节点（Root Node）：没有双亲节点的节点，在树形结构中只有一个根节点
 * 祖先（Ancestor）：当前节点上层的所有节点（当前节点的直接祖先节点）
 * 子孙（Descendent）：当前节点下层的所有节点
 * 兄弟（Brother）：同一双亲孩子
 *
 * 二叉树简介
 * 二叉树（Binary Tree）是树形结构的重要类型
 * 二叉树特点是每个节点最多只能有两颗子树，且有左右之分
 *
 * 二叉树分类
 * 满二叉树：除最后一层外，每一层上的所有节点都有两个子节点
 * 完全二叉树：除最后一层可能不满外，其他各层都达到该层节点的最大数，最后一层如果不满，该层节点全部靠左排
 *
 * 二叉树遍历方式
 * 前序遍历：根-左-右
 * 中序遍历：左-根-右
 * 后序遍历：左-右-根
 * 层序遍历：从上至下逐层遍历

2.树形结构容器类--递归方法的使用--this关键字的指向

package DataStructure_8;//树形结构容器类--递归方法的使用--this关键字的指向/** * 自定义树形结构容器： * 能够找到当前节点的父节点 * 能够找到当前节点的子节点 * 能够找到当前节点的兄弟节点 * 能够找到当前节点的祖先节点 * 能够找到当前节点的子孙节点 * */import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;/** * 基于树形结构实现元素存储的容器 *///一个节点就是一个元素public class Text5 {    //子节点映射父节点    private Map aa=new HashMap();    //父节点映射子节点    private Map<E,List> bb=new HashMap();    //向容器中添加元素的方法    private void add(E parent,E item){   //参数为父节点和子节点，每个节点就是一个元素 //完成单节点之间的映射，子节点映射父节点 this.aa.put(item,parent); //完成多节点之间的映射，父节点映射子节点 List list=this.bb.get(parent); //判断装载子节点的容器是否为空，为空则创建新list容器装载子节点 if (list==null){     list=new ArrayList();     this.bb.put(parent,list);//将新创建的list容器赋给父节点的value } list.add(item);     //为list容器添加子节点元素    }    //根据当前节点获取其父节点    private E getParent(E item){ return this.aa.get(item);    }    //获取当前节点的子节点    private List getChild(E item){ return this.bb.get(item);    }    //获取当前节点的兄弟节点    private List getBrother(E item){ //获取当前节点的父节点 E parent=this.getParent(item); //获取当亲节点的子节点容器 List list=this.getChild(parent); //list容器中的子节点不能删除，否则子节点会被永久删除 List brother=new ArrayList(); if (brother != null){    //新建ArrayList对象为[]，不为null     brother.addAll(list);     brother.remove(item); } return brother;    }    //获取当前节点的祖先节点    private List getFullFathers(E item){ //获取当前节点的父节点 E parent=this.getParent(item); //递归终止条件 if (parent==null){     return new ArrayList();//此处return直接返回ArrayList容器对象 } List list=this.getFullFathers(parent); list.add(parent); return list;    }    //获取当前节点的子孙节点    private List getGrandChild(E item){ //创建容器装载当前节点所有子孙节点 List list= new ArrayList(); List child=this.getChild(item); if (child==null){     return list; } for (int i = 0; i <child.size() ; i++) {     E ele = child.get(i);     List temp =this.getGrandChild(ele);      //将list易容成temp，list就是temp，返回的list，与temp等同     temp.add(ele);    //因为list与temp等同，所以此处使用谁都行     list.addAll(temp);      //list不能与list求并集，因此使用temp代替list } return list;    }    public static void main(String[] args) { Text5 uu=new Text5(); uu.add("root","生物"); uu.add("生物","植物"); uu.add("生物","动物"); uu.add("生物","动物"); uu.add("动物","脊索动物"); uu.add("动物","脊椎动物"); uu.add("动物","肠腔动物"); uu.add("脊椎动物","哺乳动物"); uu.add("脊椎动物","鱼类"); uu.add("哺乳动物","猫"); uu.add("哺乳动物","牛"); uu.add("哺乳动物","人"); System.out.println("========获取当前节点的父节点========="); String aa = uu.getParent("鱼类"); System.out.println(aa); System.out.println("========获取当前节点的父节点========="); List bb = uu.getChild("脊椎动物"); for (int i = 0; i <bb.size() ; i++) {     System.out.println(bb.get(i)); } System.out.println("==========获取兄弟节点=================="); List cc=uu.getBrother("动物"); for (int i = 0; i < cc.size(); i++) {     System.out.println(cc.get(i)); } System.out.println("===========获取祖先节点================"); List dd = uu.getFullFathers("人"); for (int i = 0; i <dd.size() ; i++) {     System.out.println(dd.get(i)); } System.out.println("============获取子孙节点=============="); List ff=uu.getGrandChild("root"); for (int i = 0; i <ff.size() ; i++) {     System.out.println(ff.get(i)); }    }}