算法与数据结构知识汇总（七、树）
1、树的定义
树（Tree）是n（n>=0）个结点的有限集合。n=0时称为空树。在任意一颗非空树中：
（1）有且仅有一个特定的称为根（Root）的结点；
（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、....、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
2、树的度
结点拥有的子树数量称为结点的度。
度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。
除根结点以外，分支结点也称为内部结点。
树的度是树内各结点的度的最大值，下图是树形结构，其节点度的最大值为3，即树的度为3。
图片.png
3、层次和深度
结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第n层，则其子树的根就在n+1层。其双亲在同一层的结点互为堂兄弟。显然图中的DEF是堂兄弟，而GHIJ也是。树中结点的最大层次称为树的深度（Depth）或高度，当前树的深度为4。
图片.png
4、森林
森林（Forest）是m（m>=0）棵互不相交的树的集合。
森林只需要理解概念就行了。
5、树的存储结构
树的存储结构有四种：双亲表示法、孩子表示法、双亲孩子表示法、孩子兄弟表示法
假设有一个树形结构，如图：
图片.png
（1）双亲表示法
让每个结点记住其父结点的位置。存储数据元素的结点由两部分组成：存储数据元素值的数据字段，以及存储父结点位置的父指针字段。树的所有结点可存放在一个数组中（称“静态双亲表示法”），也可组织成一个链表（称“动态双亲表示法”）。
将各节点放入数组，数组的下标、数据以及父节点位置体现在下标：
| 下标 | data | parent |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 1 |
| 4 | E | 1 |
| 5 | F | 2 |
| 6 | G | 3 |
| 7 | H | 3 |
| 8 | I | 3 |
| 9 | J | 5 |
双亲表示法的特点是：十分简洁，但找子结点比较困难。
（2）孩子表示法
由于每个结点可能有多棵子树，可以考虑使用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。
不过树的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案来解决。
[方案一]
指针域的个数就等于树的度（树的度是树的各个结点度的最大值）
图片.png
不过这种结构由于每个结点的孩子数目不同，当差异较大时，很多结点的指针域就都为空，显然是浪费空间的，不过若树的各结点度相差很小时，那就意味着开辟的空间都被利用了，这时这种缺点反而变成了优点。
[方案二]
每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针域的个数。
图片.png
这种方法克服了浪费空间的缺点，对空间的利用率是很高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。
那么，有没有办法既能减少空指针的浪费，又能节省时间呢？
具体方案是：把每个结点的孩子排列起来，以单链表做存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针有组成一个线性表，采用顺序存储结构，存放进入一个一维数组中。
图片.png
（3）双亲孩子表示法
把每个结点的孩子结点排列起来，以单链表作为存储结构，
则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，
然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中
图片.png
（4）孩子兄弟表示法
孩子兄弟表示法为每个节点设计三个域：
一个数据域，一个该节点的第一个孩子节点域，一个该节点的下一个节点的兄弟指针域
图片.png
6、二叉树
二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
什么叫斜树？
分为左斜树和右斜树：
左斜树：所有节点都只有左子树
右斜树：所有节点都只有右子树
如图是左斜树：
图片.png
什么叫满二叉树？
满二叉树有如下特点：
一个二叉树的所有分支结构都存在左子树和右子树，并且所有叶子节点只存在在最下面一层。
同样深度二叉树中，满二叉树的节点最多
K为深度(1≤k≤n),则节点总数为2^k - 1
如图：
图片.png
完全二叉树？（编号连续）
完全二叉树的特点：
若二叉树的深度为k，二叉树的层数从1到k-1层的节点数都达到了最大个数，在第k层的所有节点都集中在最左边，这就是完全二叉树
完全二叉数由满二叉树引出
满二叉树一定是完全二叉树，但完全二叉树不是满二叉树
k为深度(1≤k≤n),则节点总数的最大值为2^k - 1,当达到最大值的时候就是满二叉树
如图：
图片.png
7、二叉树的存储结构
（1）顺序存储
给一个树形结构从左到右添加角标。
图片.png
存入数组之后：
图片.png
（2）链式存储
图片.png
8、二叉树的遍历
假设有一个树形结构，如图：
图片.png
（1）前序（DLR）（中左右）
规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后前序遍历左子树，再前序遍历右子树
遍历顺序分析步骤如下：
第一轮：A B C
第二轮：A B D E C F
第三轮：A B D G H E C F
第四轮：A B D G H E C F I
总共四轮分析，每轮都采用中左右输出。
最终的遍历顺序是：A B D G H E C F I
（2）中序（LDR）（左中右）
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），
中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树
遍历顺序分析步骤如下：
第一轮：B A C
第二轮：D B E A C F
第三轮：G D H B E A C I F
总共三轮分析，每轮都采用左中右输出。
最终的遍历顺序是：G D H B E A C I F
（3）后序（LRD）（左右中）
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点
遍历顺序分析步骤如下：
第一轮：B C A
第二轮：D E B F C A
第三轮：G H D E B I F C A
总共三轮分析，每轮都采用左右中输出。
最终的遍历顺序是：G H D E B I F C A
9、代码实现
public class BinarayTree {
Node<String> root;
public BinarayTree(String data){
root=new Node<>(data,null,null);
}
public void createTree(){
Node<String> nodeB=new Node<String>("B",null,null);
Node<String> nodeC=new Node<String>("C",null,null);
Node<String> nodeD=new Node<String>("D",null,null);
Node<String> nodeE=new Node<String>("E",null,null);
Node<String> nodeF=new Node<String>("F",null,null);
Node<String> nodeG=new Node<String>("G",null,null);
Node<String> nodeH=new Node<String>("H",null,null);
Node<String> nodeJ=new Node<String>("J",null,null);
Node<String> nodeI=new Node<String>("I",null,null);
root.leftChild=nodeB;
root.rightChild=nodeC;
nodeB.leftChild=nodeD;
nodeC.leftChild=nodeE;
nodeC.rightChild=nodeF;
nodeD.leftChild=nodeG;
nodeD.rightChild=nodeH;
nodeE.rightChild=nodeJ;
nodeH.leftChild=nodeI;
}
/**
* 中序访问树的所有节点
*/
public void midOrderTraverse(Node root){//逻辑
if(root==null){
return;
}
midOrderTraverse(root.leftChild);//逻辑
System.out.println("mid:"+root.data);//输出
midOrderTraverse(root.rightChild);//逻辑
}
/**
* 前序访问树的所有节点 Arrays.sort();
*/
public void preOrderTraverse(Node root){
if(root==null){
return;
}
System.out.println("pre:"+root.data);
preOrderTraverse(root.leftChild);
preOrderTraverse(root.rightChild);
}
/**
* 后序访问树的所有节点
*/
public void postOrderTraverse(Node root){
if(root==null){
return;
}
postOrderTraverse(root.leftChild);
postOrderTraverse(root.rightChild);
System.out.println("post:"+root.data);
}
/**
* 节点
*/
public class Node<T>{
T data;
Node<T> leftChild;
Node<T> rightChild;
public Node(T data, Node<T> leftChild, Node<T> rightChild) {
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
}
[本章完...]
