首页 > 代码库 > 树&二叉树
树&二叉树
(哈弗曼树、哈弗曼编码、排序二叉树、平衡二叉树、红黑树、3种遍历(先序,后序,中序)、深度-广度优先遍历)
关键词、语句:
- 树的三种存储结构:父节点表示法、子节点表示法、链表存储
- 树代表一种非线性的数据结构
- 如果一组数组节点之间存在复杂的一对多关联时,程序就可以考虑使用树来保存这组数据了
- 一对多?例如,一个父节点可以包含多个子节点
- TreeMap即利用红黑树实现
树:一个集合(里面存在N个有父子关系的节点,N有限,即有限集合)
满足条件(请背诵下来):
a. 当N=0的时候,节点集合为空,称为"空树"
b. 在任意的非空树中,有且仅有一个根节点
c. N>1时,除了根节点,其余节点可以分为M个互有关联的子集合,称为根的子树(subtree)(递归)
注意:根节点没有父节点,叶子节点没有子节点。(除了根节点,所有的节点有唯一的父节点)
图解:
术语:(熟记)
节点:包含数据域和指针(引用)域
节点的度:节点的子树个数
树的度:所有节点度的最大值
叶子节点:度为0的节点
分支节点:度不为0的节点
兄弟节点:具有相同的父节点的节点
节点的层:更的层次为1,其余节点依次加1
树的深度:节点的最大层次
有序树:树中个子树节点从左到右是有序的,不能交换(区分左右)
祖先节点:从根到该节点所经分支上的所有节点
后代节点:以某一节点为跟的子树中任一节点
森林:2棵或者2棵以上互不相交的树的集合,删去一个树的根就得到一个森林
树的常用操作:
1. 初始化: 指定构造器创建空树,或者,以指定节点为根创建树
2. 为指定节点添加子节点
3. 判断是否为空树
4. 返回根节点
5. 返回指定节点(非根)的父节点
6. 返回指定节点(非叶子)的所有子节点
7. 返回指定节点(非叶子)的第i个子节点
8. 返回该树的深度(从节点数组里面的节点开始找其父类)
9. 返回指定节点的位置
树的实现(即表现父子节点的关系)
父节点表示法:每个子节点都记录它的父节点(有点像数据库中的无限级分类)----孩子记父亲(孩子只有一个父亲,1个记1个)
子节点表示法:每个非叶子节点通过一个链表来记录它所有的子节点------父亲记孩子(父亲可以有多个孩子,1个记多个)
详细说明:
1. 父节点表示法:
a. 为每个几点都多增加一个parent域,用来保存父节点的引用或者索引编号
数组索引 | data | parent |
0 | A | -1 |
1 | B | 0 |
2 | C | 0 |
3 | D | 1 |
代码实现:
import java.util.ArrayList;import java.util.List;public class TreeParent<E> { public static class Node<T> { T data; int parent; //记录父节点 public Node(){} public Node(T data) { this.data =http://www.mamicode.com/ data; } public Node(T data,int parent) { this.data =http://www.mamicode.com/ data; this.parent = parent; } public String toString() { return "TreeParent--Node[data="http://www.mamicode.com/+data+", parent="+parent+"]"; } } private final int DEFAULT_TREE_SIZE = 100; private int treeSize = 0; //存放节点的数组的容量(树的容量) private int nodeNums; //当前节点数量 private Node[] nodes; //记录所有的节点 public TreeParent(E data) //以指定根节点创建树 { treeSize = DEFAULT_TREE_SIZE; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data,-1); nodeNums++; //当前节点数量增加 } public TreeParent(E data,int treeSize)//指定树的容量 { this.treeSize = treeSize; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data,-1); nodeNums++; //当前节点数量增加 } public void addNode(E data,Node parent) //为指定节点添加子节点,注意传入的是Node,并且Node是static的 { //先要判断一下树是否已满,数组中不存在为null的元素 for (int i = 0 ; i < treeSize ; i++) { if (nodes[i] == null)//找到数组中第一个为null的元素,该元素保存新节点 { //创建新节点,并用指定的数组元素保存它 nodes[i] = new Node(data , pos(parent));//请注意这里实例化静态内部类 nodeNums++; return; } } throw new RuntimeException("该树已满,无法添加新节点"); } private int pos(Node parent) //返回指定节点的索引 { for (int i = 0 ; i < treeSize ; i++) { //找到指定节点 if (nodes[i] == parent) { return i; } } return -1; } public boolean empty()//判断树是否为空。 { return nodes[0] == null;//根节点是否为null } public Node<E> root()//返回根节点 { return nodes[0];//返回根节点 } public Node<E> parent(Node node)//返回指定节点(非根节点)的父节点 { //每个节点的parent记录了其父节点的位置 return nodes[node.parent]; } public List<Node<E>> children(Node parent)//返回指定节点(非叶子节点)的所有子节点 { List<Node<E>> list = new ArrayList<Node<E>>(); for (int i = 0 ; i < treeSize ; i++) { //如果当前节点的父节点的位置等于parent节点的位置 if (nodes[i] != null && nodes[i].parent == pos(parent)) { list.add(nodes[i]); } } return list; } public int deep()//返回该树的深度--从节点数组中的每一个节点开始向上不断找父节点,不断加1 { int max = 0;//用于记录节点的最大深度 for(int i = 0 ; i < treeSize && nodes[i] != null; i++) { int def = 1; //初始化本节点的深度 int m = nodes[i].parent;//m记录当前节点的父节点的位置 while(m != -1 && nodes[m] != null)//如果其父节点存在 { m = nodes[m].parent;//向上继续搜索父节点 def++; } if(max < def) { max = def; } } return max; //返回最大深度 } /* public static void main(String[] args) { TreeParent<String> tp = new TreeParent<String>("root"); TreeParent.Node root = tp.root(); System.out.println(root); tp.addNode("节点1" , root); System.out.println("此树的深度:" + tp.deep()); tp.addNode("节点2" , root); //获取根节点的所有子节点 List<TreeParent.Node<String>> nodes = tp.children(root); System.out.println("根节点的第一个子节点:" + nodes.get(0)); //为根节点的第一个子节点新增一个子节点 tp.addNode("节点3" , nodes.get(0)); System.out.println("此树的深度:" + tp.deep()); }*/}
特别注意:
1. 求深度的时候,是从子节点开始向上一步一步找。
但是要遍历数组中每一个节点,在找以前出现过的节点时,可能已经找过后面的节点了,后面又找了一遍,重复。
2. public static class Node<T> 这里出现了“静态内部类”,以及做了其实例化操作(添加节点的时候)
补充知识:static class 静态类的实例化
http://www.2cto.com/kf/201304/206692.html
http://kenby.iteye.com/blog/1603803
我在本博客的另外一篇文章中对上述连接做了整理: 内部类大总结
未完待续//
树&二叉树