简介
树的相关术语
结点：使用数结构存储的每个数据元素都被称为“节点”
结点的度：某个节点所拥有的子树的个数
树的深度：树中结点的最大层数
叶子结点：度为0的结点，也叫终端节点
分支结点：度不为0的结点，也叫非终端结点或内部结点
孩子：也可称为子树或者子结点，表示当前结点下层的直接结点
双亲：也可称为父结点，表示当前结点的直接上层结点
根结点：没有双亲结点的结点，在一个树形结构中只有一个根结点
祖先：从当前结点上层的所有的结点
子孙：当前结点下层的所有的结点
兄弟：同一双亲的孩子
二叉树
简介
二叉树（Binary Tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构 往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其 算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树， 且有左右之分
二叉树分类
满二叉树
完全二叉树
完全二叉树，除最后一层可能不满以外，其他各层都达到该层节点的最大数，最后一层 如果不满，该层所有节点都全部靠左排。 <br />
二叉树的遍历
前序遍历
中序遍历
后续遍历
层序遍历
从根节点出发，依次访问左右孩子结点，再从左右孩子出发，依次它们的孩子结点，直 到节点访问完毕 
二叉树排序
自定义树形结构容器
树形结构定义条件：
- 能够找到当前结点的父结点
- 能够找到当前结点的子结点
- 能够找到当前结点的兄弟结点
- 能够找到当前结点的祖先结点
- 能够找到当前结点的子孙节点
树形结构容器使用
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class MyTree<E> {
private Map<E,E> map= new HashMap<>();
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);
}
/**
* 获取当前结点的父结点
*/
public E getParent(E item){
return this.map.get(item);
}
/**
* 获取当前结点的子结点
*/
public List<E> getChild(E item){
return this.map2.get(item);
}
/**
* 获取当前结点的兄弟结点
*/
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;
}
/**
* 获取当前结点祖先结点
*/
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;
}
/**
* 获取当前结点子孙结点
*/
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 elem=child.get(i);
List<E> temp=this.getGrandChildren(elem);
list.add(elem);
list.addAll(temp);
}
return list;
}
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("哺乳动物","人");
}
}
若有收获，就点个赞吧
0 人点赞
