数据结构与算法--树的三种存储结构
之前学的链表、队列、栈，都是线性表，因为其中每个数据元素只有一个前驱和一个后继。是一对一的关系。
假如是一对多的关系呢？这种数据结构就是今天要学的树。
树的定义
树是由有限个结点（假设为n）构成的集合。n = 0说明这是棵空树。一棵树中，有且只有一个根结点，按照习惯在位于树的顶端。根结点可以理解为始祖一般的存在，他们有若干个孩子，但是他本身没有双亲。如图1中结点A就是根结点。
假设把树从中截断（并没有），可以得到若干个互不相交（没有交集）的集合，每一个集合本身又是一棵树，称为根的子树，以后就直接叫“子树”。比如假想我断开了A-B, A-C的连接，结点B和C没有双亲成为了根结点，产生了两棵互不相交的子树。如下。
什么叫互不相交呢？下面粗线连接部分如左图D和E，他们到底属于哪棵树？可以认为构成子树的集合之间有交集，造成了原来的子树T1和子树T2相交。这样相交的树，不叫子树，因为这不符合树的定义。
树的结点与深度
上面的图中每一个圆圈代表的就是一个结点，结点之间的连线表示了结点之间的关系。结点拥有的子树数目称为该结点的度，也可以简单理解为该结点拥有的孩子个数。如上面的图中A结点的度为2。度为0的结点称为叶子结点——也就是没孩子。度不为0的结点称为非叶子结点或非终端结点。树的度为树中各个结点度的最大值，如图1中结点D拥有的孩子有3个，最多，所以树的度就是3。
树中各个结点之间有什么关系呢？某结点它的子树的根称做该节点的孩子（Child），该结点称为这些孩子的双亲（Parent），或者直接叫父结点。同一个父结点的孩子之间互称为兄弟（Sibling）。举例来说，图1中结点C的孩子结点有E和F，E和F的父结点为C，而E和F之间是兄弟关系。
树的深度就是指树的层数，根结点处为第一层，其孩子结点为第二层，以此类推。易知图1树的深度为4。
树的存储结构
父结点（双亲）表示法
这种结构的思想比较简单：除了根结点没有父结点外，其余每个结点都有一个唯一的父结点。将所有结点存到一个数组中。每个结点都有一个数据域data和一个数值parent指示其双亲在数组中存放的位置。根结点由于没有父结点，parent用-1表示。
package Chap6;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class TreeParent- { public static class Node
{ private T data; private int parent; public Node(T data, int parent) { this.data = data; this.parent = parent; } public T getData() { return data; } @Override public String toString() { return "Node{" + "data=" + data + ", parent=" + parent + '}'; } } // 树的容量，能容纳的最大结点数 private int treeCapacity; // 树的结点数目 private int nodesNum; // 存放树的所有结点 private Node - [] nodes; // 以指定树大小初始化树 public TreeParent(int treeCapacity) { this.treeCapacity = treeCapacity; nodes = new Node[treeCapacity]; } // 以默认的树大小初始化树 public TreeParent() { treeCapacity = 128; nodes = new Node[treeCapacity]; } public void setRoot(Item data) { // 根结点 nodes[0] = new Node<>(data, -1); nodesNum++; } public void addChild(Item data, Node
- parent) { if (nodesNum < treeCapacity) { // 新的结点放入数组中第一个空闲位置 nodes[nodesNum] = new Node<>(data, index(parent)); nodesNum++; } else { throw new RuntimeException("树已满，无法再添加结点！"); } } // 用nodeNum是因为其中无null，用treeCapacity里面很多null值根本无需比较 private int index(Node
- parent) { for (int i = 0; i < nodesNum; i++) { if (nodes[i].equals(parent)) { return i; } } throw new RuntimeException("无此结点"); } public void createTree(List
- datas, List
parents) { if (datas.size() > treeCapacity) { throw new RuntimeException("数据过多，超出树的容量！"); } setRoot(datas.get(0)); for (int i = 1; i < datas.size(); i++) { addChild(datas.get(i), nodes[parents.get(i - 1)]); } } // 是否为空树 public boolean isEmpty() { return nodesNum == 0; // or return nodes[0] == null } public Node - parentTo(Node
- node) { return nodes[node.parent]; } // 结点的孩子结点 public List
- > childrenFromNode(Node
- parent) { List
- > children = new ArrayList<>(); for (int i = 0; i < nodesNum; i++) { if (nodes[i].parent == index(parent)) { children.add(nodes[i]); } } return children; } // 树的度 public int degreeForTree() { int max = 0; for (int i = 0; i < nodesNum; i++) { if (childrenFromNode(nodes[i]).size() > max) { max = childrenFromNode(nodes[i]).size(); } } return max; } public int degreeForNode(Node
- node) { return childrenFromNode(node).size(); } // 树的深度 public int depth() { int max = 0; for (int i = 0; i < nodesNum; i++) { int currentDepth = 1; int parent = nodes[i].parent; while (parent != -1) { // 向上继续查找父结点，知道根结点 parent = nodes[parent].parent; currentDepth++; } if (currentDepth > max) { max = currentDepth; } } return max; } // 树的结点数 public int nodesNum() { return nodesNum; } // 返回根结点 public Node
- root() { return nodes[0]; } // 让树为空 public void clear() { for (int i = 0; i < nodesNum; i++) { nodes[i] = null; nodesNum = 0; } } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("Tree{\n"); for (int i = 0; i < nodesNum - 1; i++) { sb.append(nodes[i]).append(", \n"); } sb.append(nodes[nodesNum - 1]).append("}"); return sb.toString(); } public static void main(String[] args) { // 按照以下定义，生成树 List
datas = new ArrayList<>(Arrays.asList("Bob", "Tom", "Jerry", "Rose", "Jack")); List parents = new ArrayList<>(Arrays.asList(0, 0, 1, 2)); TreeParent tree = new TreeParent<>(); tree.createTree(datas, parents); TreeParent.Node root = tree.root(); // root的第一个孩子 TreeParent.Node aChild = tree.childrenFromNode(root).get(0); System.out.println(aChild.getData() + "的父结点是" + tree.parentTo(aChild).getData()); System.out.println("根结点的孩子" + tree.childrenFromNode(root)); System.out.println("该树深度为" + tree.depth()); System.out.println("该树的度为" + tree.degreeForTree()); System.out.println("该树的结点数为" + tree.nodesNum()); System.out.println(tree); }}/* OutputsTom的父结点是Bob根结点的孩子[Node{data=Tom, parent=0}, Node{data=Jerry, parent=0}]该树深度为3该树的度为2该树的结点数为5Tree{Node{data=Bob, parent=-1}, Node{data=Tom, parent=0}, Node{data=Jerry, parent=0}, Node{data=Rose, parent=1}, Node{data=Jack, parent=2}}*/
setRoot方法必须首先被调用，可以看到根结点始终被放置在数组中第一个位置（下标为0），之后才能调用addChild方法。createTree将创建树的过程简化了，我们只需输入一组数据datas，和这组数据对应的parents传给createTree就行，注意datas的第一个数据是根结点信息，在代码中默认使用-1表示其parent，所以它在parents中没有对应的parent值，也就是说datas的第二个值才和parents的第一个值对应，以此类推。树创建完成后，若想再添加结点到树，调用addChild就行。
childrenFromNode方法获取某个结点的所有孩子结点，由代码看出它需要遍历所有结点，复杂度为O(n)。parentTo方法获取某结点的父结点，复杂度O(1)。
另外求树的度的时候，也是遍历了所有结点，从中选出最大的度作为树的度，复杂度为O(n)。求树的深度也类似，遍历了所有结点，从下往上，一直追溯到根结点，用currentDepth记录了当前结点的深度，从所有结点中选择最大深度值作为树的深度。
孩子表示法
换种思路，既然双亲表示法获取某结点的所有孩子有点麻烦，我们索性让每个结点记住他所有的孩子。但是由于一个结点拥有的孩子个数是一个不确定的值，虽然最多只有树的度那么多，但是大多数结点的孩子个数并没有那么多，如果用数组来存放所有孩子，对于大多数结点来说太浪费空间了。自然我们容易想到用一个可变容量的表来存，选用Java内置的LinkedList是个不错的选择。先用一个数组存放所有的结点信息，该链表只需存储结点在数组中的下标就行了。
package Chap6;import java.util.*;public class TreeChildren- { public static class Node
{ private T data; private List children; public Node(T data) { this.data = data; this.children = new LinkedList<>(); } public Node(T data, int[] children) { this.data = data; this.children = new LinkedList<>(); for (int child : children) { this.children.add(child); } } public T getData() { return data; } @Override public String toString() { return "Node{" + "data=" + data + ", children=" + children + '}'; } } // 树的容量，能容纳的最大结点数 private int treeCapacity; // 树的结点数目 private int nodesNum; // 存放树的所有结点 private Node - [] nodes; public TreeChildren(int treeCapacity) { this.treeCapacity = treeCapacity; nodes = new Node[treeCapacity]; } public TreeChildren() { treeCapacity = 128; nodes = new Node[treeCapacity]; } public void setRoot(Item data) { nodes[0].data = data; nodesNum++; } public void addChild(Item data, Node
- parent) { if (nodesNum < treeCapacity) { // 新的结点放入数组中第一个空闲位置 nodes[nodesNum] = new Node<>(data); // 父结点添加其孩子 parent.children.add(nodesNum); nodesNum++; } else { throw new RuntimeException("树已满，无法再添加结点！"); } } public void createTree(Item[] datas, int[][] children) { if (datas.length > treeCapacity) { throw new RuntimeException("数据过多，超出树的容量！"); } for (int i = 0; i < datas.length; i++) { nodes[i] = new Node<>(datas[i], children[i]); } nodesNum = datas.length; } // 根据给定的结点查找再数组中的位置 private int index(Node
- node) { for (int i = 0; i < nodesNum; i++) { if (nodes[i].equals(node)) { return i; } } throw new RuntimeException("无此结点"); } public List
- > childrenFromNode(Node
- node) { List
- > children = new ArrayList<>(); for (Integer i : node.children) { children.add(nodes[i]); } return children; } public Node
- parentTo(Node
- node) { for (int i = 0; i < nodesNum; i++) { if (nodes[i].children.contains(index(node))) { return nodes[i]; } } return null; } // 是否为空树 public boolean isEmpty() { return nodesNum == 0; // or return nodes[0] == null } // 树的深度 public int depth() { return nodeDepth(root()); } // 求以node为根结点的子树的深度 public int nodeDepth(Node
- node) { if (node == null) { return 0; } // max是某个结点所有孩子中的最大深度 int max = 0; // 即使没有孩子，返回1也是正确的 if (node.children.size() > 0) { for (int i : node.children) { int depth = nodeDepth(nodes[i]); if (depth > max) { max = depth; } } } // 这里需要+1因为depth -> max是当前结点的孩子的深度, +1才是当前结点的深度 return max + 1; } public int degree() { int max = 0; for (int i = 0; i < nodesNum; i++) { if (nodes[i].children.size() > max) { max = nodes[i].children.size(); } } return max; } public int degreeForNode(Node
- node) { return childrenFromNode(node).size(); } public Node
- root() { return nodes[0]; } // 树的结点数 public int nodesNum() { return nodesNum; } // 让树为空 public void clear() { for (int i = 0; i < nodesNum; i++) { nodes[i] = null; nodesNum = 0; } } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("Tree{\n"); for (int i = 0; i < nodesNum - 1; i++) { sb.append(nodes[i]).append(", \n"); } sb.append(nodes[nodesNum - 1]).append("}"); return sb.toString(); } public static void main(String[] args) { String[] datas = {"Bob", "Tom", "Jerry", "Rose", "Jack"}; int[][] children = { {1, 2}, {3}, {4}, {}, {}}; TreeChildren
tree = new TreeChildren<>(); tree.createTree(datas, children); TreeChildren.Node root = tree.root(); TreeChildren.Node rightChild = tree.childrenFromNode(root).get(1); System.out.println(rightChild.getData() + "的度为" + tree.degreeForNode(rightChild)); System.out.println("该树的结点数为" + tree.nodesNum()); System.out.println("该树根结点" + tree.root()); System.out.println("该树的深度为" + tree.depth()); System.out.println("该树的度为" + tree.degree()); System.out.println(tree.parentTo(rightChild)); tree.addChild("Joe", root); System.out.println("该树的度为" + tree.degree()); System.out.println(tree); }}/* OutputsJerry的度为1该树的结点数为5该树根结点Node{data=Bob, children=[1, 2]}该树的深度为3该树的度为2Node{data=Bob, children=[1, 2]}该树的度为3Tree{Node{data=Bob, children=[1, 2, 5]}, Node{data=Tom, children=[3]}, Node{data=Jerry, children=[4]}, Node{data=Rose, children=[]}, Node{data=Jack, children=[]}, Node{data=Joe, children=[]}}*/
有些方法的实现和双亲表示法一样，有些方法的实现改变了。
createTree方法中可以接受一个二维int数组，存放着每个结点的children，传参的时候注意一点，如果某个结点没有孩子，那么也应该填入空值。就像下面这样，否则会引发空指针。
int[][] children = { {1, 2}, {3}, {4}, {}, {}};
addChild参数列表没变，实现变为新添加的结点在数组中的下标（其实就是数组的第一个空闲位置）add进父结点的孩子链表中。createTree可以按照定义一次性生成树，只需传入结点信息的表和对应的孩子链表就行，复杂度也是O(n)。childrenFromNode获得某个结点的所有孩子，这就比双亲表示法好点了，它没有遍历所有结点也无需进行if判断，而仅仅将该结点的孩子链表中的内容（整型值）转换成Node对象返回而已。不过该实现要获取某个结点的父结点就没有双亲法好了，孩子表示法必须遍历所有结点，复杂度为O(n)。获取父结点方法中，遍历所有结点，如果有某个结点的孩子链表中包含了所求结点，则返回该结点。
求树的深度方法也变成了递归实现，在双亲法实现中由于存在parent域，所以从下至上查找比较方便；而在孩子表示法中，获取孩子结点比较方便，所以从根结点开始从上至下查找，这里使用到了递归的思想。由于返回的是max + 1（为什么是这个值后面会解释），所以需要对树空的情况进行正确的处理。若是叶子结点，循环不会执行，应该返回max + 1 = 1，正确；其他情况，该结点有孩子，进入循环开始递归，递归直到遇到叶子结点停止，开始返回，叶子结点返回1。回到父结点的nodeDepth函数，max被赋值为1。现在说说这个max到底是什么意思，代码中for (int i: node.children)，遍历当前结点的所有孩子，它们共享同一个max，所以max的意义就是某结点所有孩子结点的深度的最大值。于是max + 1就是当前结点的深度。接着说，函数一直返回，每次返回实际就是往上一层，到所求结点的孩子结点处，其孩子结点中的最大深度赋值给max，那么最后返回的max + 1就是所求结点作为根结点时的子树深度。
孩子表示法的优化
再说获取某结点父结点的方法，从代码看出它遍历了所有结点。如果要改进，可以将双亲表示法融合进去，增加一个parent域就行。也就是说，Node类改成如下就行，这种实现可以称为双亲孩子表示法。
public static class Node{ private int parent; private T data; private List children;}
这样获取父结点的复杂度就变成了O(1)，就懒得实现了，稍微改改代码就好了。
孩子兄弟表示法
还有一种表示法，关注某结点的孩子结点之间的关系，他们互为兄弟。一个结点可能有孩子，也有可能有兄弟，也可能两者都有，或者两者都没。基于这种思想，可以用具有两个指针域（一个指向当前结点的孩子，一个指向其兄弟）的链表实现，这种链表又称为二叉链表。特别注意的是，双亲表示法和孩子结点表示法，都使用了数组存放每一个结点的信息，若稍加分析，使用数组是有必要的。但在这种结构中，我们摒弃了数组，根结点可以作为头指针，以此开始可以遍历到树的全部结点——根结点肯定是没有兄弟的（根结点如果有兄弟这棵树就有两个根结点了），如果它没有孩子，则这棵树只有根结点；若有孩子，就如下图，它的nextChild的指针域就不为空，现在看这个左孩子，有兄弟（实际就是根结点的第二个孩子）还有孩子，则左孩子的两个指针域都不为空，再看这个左孩子的nextSib，他有个孩子...一直这样下去，对吧，能够访问到树的全部结点的。
整个结构就是一条有两个走向的错综复杂的链表，垂直走向是深入到结点的子子孙孙；水平走向就是查找它的兄弟姐妹。这种结构也能直观反映树的结构的，上图其实就是下面这棵树。
说了这么多，反正把它当链表就行了，就是多了一个指针域而已。（和双向链表区别开，双向链表是a.next =b，必然有b.prev = a;但是这里二叉链表却没有这个限制，它指向任意一个结点都可以）。
好了现在来实现吧！
package Chap6;import java.util.ArrayList;import java.util.List;public class TreeChildSib- { public static class Node
{ private T data; private Node nextChild; private Node nextSib; public T getData() { return data; } public Node(T data) { this.data = data; } public Node getNextChild() { return nextChild; } public Node getNextSib() { return nextSib; } @Override public String toString() { String child = nextChild == null ? null : nextChild.getData().toString(); String sib = nextSib == null ? null : nextSib.getData().toString(); return "Node{" + "data=" + data + ", nextChild=" + child + ", nextSib=" + sib + '}'; } } private Node - root; // 存放所有结点，每次新增一个结点就add进来 private List
- > nodes = new ArrayList<>(); // 以指定的根结点初始化树 public TreeChildSib(Item data) { setRoot(data); } // 空参数构造器 public TreeChildSib() { } public void setRoot(Item data) { root = new Node<>(data); nodes.add(root); } public void addChild(Item data, Node
- parent) { Node
- node = new Node<>(data); // 如果该parent是叶子结点，没有孩子 if (parent.nextChild == null) { parent.nextChild = node; // parent有孩子了，只能放在n其第一个孩子的最后一个兄弟之后 } else { // 从parent的第一个孩子开始，追溯到最后一个兄弟 Node
- current = parent.nextChild; while (current.nextSib != null) { current = current.nextSib; } current.nextSib = node; } nodes.add(node); } public List
- > childrenFromNode(Node
- node) { List
- > children = new ArrayList<>(); for (Node
- cur = node.nextChild; cur != null; cur = cur.nextSib) { { children.add(cur); } } return children; } public Node
- parentTo(Node
- node) { for (Node
- eachNode : nodes) { if (childrenFromNode(eachNode).contains(node)) { return eachNode; } } return null; } public boolean isEmpty() { return nodes.size() == 0; } public Node
- root() { return root; } public int nodesNum() { return nodes.size(); } public int depth() { return nodeDepth(root); } public int nodeDepth(Node
- node) { if (node == null) { return 0; } int max = 0; if (childrenFromNode(node).size() > 0) { for (Node
- child : childrenFromNode(node)) { int depth = nodeDepth(child); if (depth > max) { max = depth; } } } return max + 1; } public int degree() { int max = 0; for (Node
- node : nodes) { if (childrenFromNode(node).size() > max) { max = childrenFromNode(node).size(); } } return max; } public int degreeForNode(Node
- node) { return childrenFromNode(node).size(); } public void deleteNode(Node
- node) { if (node == null) { return; } deleteNode(node.nextChild); deleteNode(node.nextSib); node.nextChild = null; node.nextSib = null; node.data = null; nodes.remove(node); } public void clear() { deleteNode(root); root = null; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("Tree{\n"); for (int i = 0; i < nodesNum() - 1; i++) { sb.append(nodes.get(i)).append(", \n"); } sb.append(nodes.get(nodesNum() - 1)).append("}"); return sb.toString(); } public static void main(String[] args) { TreeChildSib
tree = new TreeChildSib<>("A"); TreeChildSib.Node root = tree.root(); tree.addChild("B", root); tree.addChild("C", root); tree.addChild("D", root); TreeChildSib.Node child1 = tree.childrenFromNode(root).get(0); TreeChildSib.Node child2 = tree.childrenFromNode(root).get(1); TreeChildSib.Node child3 = tree.childrenFromNode(root).get(2); tree.addChild("E", child1); tree.addChild("F", child2); tree.addChild("G", child1); tree.addChild("H", child3); System.out.println(tree); System.out.println("该树结点数为" + tree.nodesNum()); System.out.println("该树深度为" + tree.depth()); System.out.println("该树的度为" + tree.degree()); System.out.println(child1.getData() + "的度为" + tree.degreeForNode(child1)); System.out.println(child2.getData() + "的父结点为" + tree.parentTo(child2).getData()); tree.clear(); System.out.println(child1); System.out.println(tree.isEmpty()); }}/* OutputsTree{Node{data=A, nextChild=B, nextSib=null}, Node{data=B, nextChild=E, nextSib=C}, Node{data=C, nextChild=F, nextSib=D}, Node{data=D, nextChild=H, nextSib=null}, Node{data=E, nextChild=null, nextSib=G}, Node{data=F, nextChild=null, nextSib=null}, Node{data=G, nextChild=null, nextSib=null}, Node{data=H, nextChild=null, nextSib=null}}该树结点数为8该树深度为3该树的度为3B的度为2C的父结点为ANode{data=null, nextChild=null, nextSib=null}true*/
由于有的方法需要遍历树的所有结点，所以自建一个表List<Node<Item>> nodes来存放，具体来说就是每次添加结点的同时将这个结点加入到该表中。
addChild方法很重要，如果需要依附的父结点还没有孩子（if分支），那需要添加的结点成为它的第一个孩子；如果父结点有孩子了（else分支），那么就从父结点的第一个孩子开始，一直到它最后一个兄弟之后，新添加的结点位于此处。
获取某结点的所有孩子childrenFromNode方法，就是从所求结点的第一个孩子开始，不断找到其兄弟，第一个孩子与其所有兄弟全部就是所求结点的所有孩子。
求度，求深度的算法和孩子表示法差不多，就不再赘述。来看clear清空树的方法，需要把每个结点得信息都置为空，就必须有个方法能遍历这棵树，这里用了后序遍历的方法，这之后还没完，存放结点的表也应该清空才是。
若是想让获取父结点变得方便些，也可以多设置一个parent域，见孩子表示法的优化。
孩子兄弟表示法有一个优点，可以将一棵普通树转化成二叉树，由于二叉树有诸多特征，使得处理起来变得简单。孩子兄弟表示法上面的那个链表，稍微拉伸下改变下结构，就能变成一棵二叉树，如下。
by @sunhaiyu
2017.9.8