三、 树形结构
1 树形结构简介
树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。
2 树的相关术语
2.1结点(Node)
使用树结构存储的每一个数据元素都被称为“结点”。
2.2结点的度(Degree of Node)
某个结点所拥有的子树的个数。
2.3树的深度(Degree of Tree)
树中结点的最大层次数。
2.4叶子结点(Leaf Node)
度为 0 的结点，也叫终端结点。
2.5分支结点(Branch Node)
度不为 0 的结点，也叫非终端结点或内部结点。
2.6孩子(Child)
也可称之为子树或者子结点，表示当前结点下层的直接结点。
2.7双亲(Parent)
也可称之为父结点，表示当前结点的直接上层结点。
2.8根节点(Root Node)
没有双亲结点的结点。在一个树形结构中只有一个根节点。
2.9祖先(Ancestor)
从当前结点上层的所有结点。
2.10子孙(Descendant)
当前结点下层的所有结点。
2.11兄弟(Brother)
同一双亲的孩子。
3 二叉树简
二叉树（Binary Tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构 往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其 算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树， 且有左右之分。
3.1 二叉树分类
3.1.1 满二叉
满二叉树指除最后一层外，每一层上的所有节点都有两个子节点。
3.1.2 完全二叉
完全二叉树，除最后一层可能不满以外，其他各层都达到该层节点的最大数，最后一层 如果不满，该层所有节点都全部靠左排。
3.2二叉树遍历
二叉树遍历的方式：
前序遍历：根-左-右
中序遍历：左-根-右
后序遍历：左-右-根
层序遍历：从上至下逐层遍
3.2.1 前序遍历
前序遍历顺序：根-左-右
3.2.2 中序遍历
中序遍历顺序：左-根-右
3.2.3 后序遍历
后序遍历顺序：左-右-根
3.2.4 层序遍历
层序遍历顺序： 从根节点出发，依次访问左右孩子结点，再从左右孩子出发，依次它们的孩子结点，直 到节点访问完毕。
3.3二叉树排序
3.3.1 二叉树排序分析
利用二叉树结构以及遍历方式可以实现基于二叉树的元素排序处理。
3.3.2 二叉树排序实现
3.3.2.1 创建二叉树排序器类
/** * 基于二叉树结构实现元素排序处理的排序器 */ public class BinaryTreeSort<E extends Integer> { /** * 将元素添加到排序器中 */ public void add(E element){ } /** * 对元素进行排序 */ public void sort(){ } public static void main(String[] args) { } }
3.3.2.2 创建结点类
/** * 定义结点类 */ class Node<E extends Integer>{ private E item;//存放元素 private Node left;//存放左子树地址 private Node right;//存放右子树地址 Node(E item){ this.item = item; } /** * 添加结点 */ public void addNode(Node node){ //完成新结点中的元素与当前结点中的元素的判断. //如果新结点中的元素小于当前结点中的元素，那么新结点则放到当前结点的左子树中。 if(node.item.intValue() < this.item.intValue()){ if(this.left == null) this.left = node; else this.left.addNode(node); }else{ //如果新结点中的元素大于当前结点中的元素，那么新结点则放到当前结点的右子树中。 if(this.right == null) this.right = node; else this.right.addNode(node); } } /** * 使用中序遍历二叉树 */ public void inorderTraversal(){ //找到最左侧的那个结点 if(this.left != null)this.left.inorderTraversal(); System.out.println(this.item); if(this.right != null)this.right.inorderTraversal(); } }
3.3.2.3 实现向排序器中添加元素方法
/** * 将元素添加到排序器中 */ public void add(E element){ //实例化结点对象 Node<E> node = new Node<>(element); //判断当前二叉树中是否有根结点。如果没有那么新结点则为根结点 if(this.root == null) this.root = node; else this.root.addNode(node); }
3.3.2.4 实现排序器中排序方法
/** * 对元素进行排序 */ public void sort(){ //判断根结点是否为空 if(this.root == null)return ; this.root.inorderTraversal(); }
4 自定义树形结构容器
4.1树形结构定义
能够找到当前结点的父结点
能够找到当前结点的子结点
能够找到当前结点的兄弟结点
能够找到当前结点的祖先结点
能够找到当前结点的子孙节点
4.2自定义树形结构分析
4.3实现自定义树形结构容器
4.3.1 创建树形结构容器类
/** * 基于树形结构实现元素存储的容器 */ public class MyTree<E> { /** * 向容器中添加元素 */ public void add(E parent,E item){} /** * 获取当前结点的父结点 */ public E getParent(E item){ return null; } /** * 获取当前结点的子结点 */ public List<E> getChild(E item){ return null; } /** * 获取当前结点的兄弟结点 */ public List<E> getBrother(E item){ return null; } /** * 获取当前结点的祖先结点 */ public List<E> getForefathers(E item){ return null; } /** * 获取当前结点的子孙结点 */ public List<E> getGrandChildren(E item){ return null; } public static void main(String[] args) {} }
4.3.2 实现添加元素方法
private Map<E,E> map = new HashMap<>();//String--->String private Map<E,List<E>> map2 = new HashMap<>();//String ---->List /** * 向容器中添加元素 */ public void add(E parent,E item){ //完成在单结点之间映射 this.map.put(item,parent); //完成多结点之间映射 List<E> list = this.map2.get(parent); //判断当前结点下是否含有子结点，如果没有则创建一个新的 List if(list == null){ list = new ArrayList<>(); this.map2.put(parent,list); } list.add(item); }
4.3.3 获取当前结点的父结点与子结点
4.3.3.1 获取父结点
/** * 获取当前结点的父结点 */ public E getParent(E item){ return this.map.get(item); }
4.3.3.2 获取子结点
/** * 获取当前结点的子结点 */ public List<E> getChild(E item){ return this.map2.get(item); }
4.3.4 获取当前结点的兄弟结点
/** * 获取当前结点的兄弟结点 */ public List<E> getBrother(E item){ //获取当前结点的父结点 E parent = this.getParent(item); //获取当前父结点的所有的子结点 List<E> list = this.getChild(parent); List<E> brother = new ArrayList<>(); if(list != null){ brother.addAll(list); brother.remove(item); } return brother; }
4.3.5 获取当前结点的祖先结点
/** * 获取当前结点的祖先结点 */ public List<E> getForefathers(E item){ //获取当前结点的父结点 E parent = this.getParent(item); //结束递归的边界条件 if(parent == null){ return new ArrayList<>(); } //递归调用，再次获取当前结点父结点的父结点 List<E> list = this.getForefathers(parent); //将递归到的所有结点元素添加到返回的 List 中 list.add(parent); return list; }
4.3.6 获取当前结点的子孙节点
/** * 获取当前结点的子孙结点 */ public List<E> getGrandChildren(E item){ //存放所有子孙结点中的元素 List<E> list = new ArrayList<>(); //获取当前结点的子结点 List<E> child = this.getChild(item); //结束递归的边界条件 if (child == null){ return list; } //遍历子结点 for(int i=0;i<child.size();i++){ //获取节点中的元素 E ele = child.get(i); List<E> temp = this.getGrandChildren(ele); list.add(ele); list.addAll(temp); } return list; }
4.3.7 测试自定义容器
public static void main(String[] args) { //实例化容器 MyTree<String> myTree = new MyTree<>(); //添加元素 myTree.add("root","生物"); myTree.add("生物","植物"); myTree.add("生物","动物"); myTree.add("生物","菌类"); myTree.add("动物","脊椎动物"); myTree.add("动物","脊索动物"); myTree.add("动物","腔肠动物"); myTree.add("脊椎动物","哺乳动物"); myTree.add("脊椎动物","鱼类"); myTree.add("哺乳动物","猫"); myTree.add("哺乳动物","牛"); myTree.add("哺乳动物","人"); System.out.println("---------获取父结点---------"); String parent = myTree.getParent("鱼类"); System.out.println(parent); System.out.println("---------获取子结点---------"); List<String> child= myTree.getChild("动物"); for(int i=0;i<child.size();i++){ System.out.println(child.get(i)); } System.out.println("---------获取兄弟结点---------"); List<String> brother = myTree.getBrother("脊椎动物"); for(int i=0;i<brother.size();i++){ System.out.println(brother.get(i)); } System.out.println("---------获取祖先结点---------"); List<String> foreFathers = myTree.getForefathers("人"); for(int i=0;i<foreFathers.size();i++){ System.out.println(foreFathers.get(i)); } System.out.println("---------获取子孙结点---------"); List<String> grandChildren = myTree.getGrandChildren("root"); for(int i =0;i<grandChildren.size();i++){ System.out.println(grandChildren.get(i)); } }
