了解树结构
在了解树结构之前，想必应该对链式结构和数组有了一定的了解，树的结构是也是一种特定的元素序列的集合，定义：树是非线性结构，它是由n(n>=0)个有限结点组成的集合，当n等于0时，称之为空树，在任意非空树中：
- 有且只有一个特定的称之为根(root)的结点
- 其余结点可以分为m个互不相交的有限集合
- 这些有限集合可以看作是新的树，并且称为根的子树
树结构的基本名称
结点的度：一个结点含有子树的个数称为该结点的度；
树的度：一棵树中，所有结点度的最大值称为树的度；
叶子结点或终端结点：度为0的结点称为叶结点；
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
根结点：一棵树中，没有双亲结点的结点；其中一棵不为空树的树，根结点是唯一的，不存在有很多根节点
树的高度或深度：树中结点的最大层次；
非终端结点或分支结点：度不为0的结点；
兄弟结点：具有相同父结点的结点互称为兄弟结点；
堂兄弟结点：双亲在同一层的结点互为堂兄弟；
结点的祖先：从根到该结点所经分支上的所有结点；
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。
森林：由m（m>=0）棵互不相交的树组成的集合称为森林
树的储存形式
树在内存中的储存形式有很多种，包括孩子表示法、双亲表示法、孩子双亲表示法、孩子兄弟表示法等等，不用的储存方式有着不同的优点，就比如双亲表示法，其子节点内存有双亲结点的地址，能够在时间复杂度为O(1)的情况下，访问到双亲结点，但是想要知道孩子结点，必须要访问整个结点。但是各种表示法都有一定缺点，接下来重点讲孩子兄弟表示法，这种方法给找某个结点的孩子带来了方便
但是如果想要想到这个结点的双亲结点，显然也是比较麻烦的，如果实在有必要，可以增加一个parent指针域来解决这个问题
这种方法最大的好处就是，可以将复杂的树结构，变为较为简单的二叉树结构
二叉树的特点
- 每个结点最多只有两颗子树，其次是有一颗子树或者不存在子树
- 拥有两个子树的结点，将这两颗子树称为这个结点的左子树和右子树，次序不能颠倒，即使是只有一颗子树，也被分为左子树和右子树，所以在这基础上，可以演变为二叉树有五种基本形态：空二叉树、只有根节点的二叉树、根结点只有左子树，根节点只有右子树，拥有左子树和右子树的根节点。
满二叉树和完全二叉树
如上图就是满二叉树，所以二叉树有以下特点：
- 二叉树除最后一层都是度为零的结点，也称之为叶子节点外，其余都是拥有左右度为二的结点
- 总结点的个数为2^（n-1），其中n为该满二叉树的深度
- 在同样深度的二叉树中，满二叉树拥有最多的节点数
完全二叉树
对于一颗具有n个结点的二叉树，对其进行层序编号，如果编号为i （i >= 1）的结点，与相同深度的满二叉树编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树如下图：
二叉树的特点：
- 叶子结点只能出现在最下两层，最下层叶子结点集中在左边，倒数第二层如果有叶子结点，一定集中在右部位置
- 如果度数为一，则该节点只能拥有左节点
- 同样结点的二叉树，完全二叉树拥有最小深度
二叉树的性质
- 在二叉树的第i层上至多有2^(i-1)个结点，(i>=1)
- 深度为k的二叉树至多有2^k -1个结点（k>=1）
- 叶子结点树比度为二的结点树多一个
- n个结点的完全二叉树的深度为[log 2 (N)] +1，([X]表示不大于x的最大整数)
二叉树的模拟实现
定义二叉树
public static class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
求结点的个数size
//方法一:遍历的思想求size
int sumSize = 0;
public int size(TreeNode root){
if(root != null) sumSize++;
if(root != null) size(root.left);
if(root != null) size(root.right);
return sumSize;
}
//方法二:子问题思路
public int size2(TreeNode root){
if(root == null) return 0;
return size2(root.left) + size2(root.right) + 1;
}
得到叶子结点的个数
public static int leafSize = 0;
public void getLeafNodeCount1(TreeNode root){
if(root == null)return;
if(root.left == null && root.right == null){
leafSize++;
}
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
}
public int getLeafNodeCount2(TreeNode root){
if(root == null)return 0;
if(root.left == null && root.right == null){
leafSize++;
}
return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
}
获取第k层结点的个数
public int getKLevelNodeCount(TreeNode root,int k){
if(root == null)return 0;
if(k == 1 && root != null) return 1;
return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
}
获取二叉树的高度
//获取二叉树高度
public int getHeight(TreeNode root){
if(root == null) return 0;
return (getHeight(root.left)>getHeight(root.right)?getHeight(root.left):getHeight(root.right))+1;
}
找到目标节点
public TreeNode find(TreeNode root,char val){
if(root == null) return null;
if(root.val == val) return root;
TreeNode ret = find(root.left,val);
if(ret != null)
return ret;
ret = find(root.right,val);
if(ret != null)
return ret;
return null;
}
层序遍历
public List<List<Character>> levelOrder2(TreeNode root){
List<List<Character>> ret = new ArrayList<>();
if(root == null)return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Character> list = new ArrayList<>();
while(size != 0){
TreeNode cur = queue.poll();
list.add(cur.val);
size--;
if(cur.left != null){
queue.offer(cur.left);
}
if(cur.right != null){
queue.offer(cur.right);
}
}
ret.add(list);
}
return ret;
}
判断一棵树是不是完全二叉树
boolean isCompleteTree(TreeNode root){
if(root == null) return false;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
if(cur != null){
queue.offer(cur.left);
queue.offer(cur.right);
}else{
break;
}
}
while(!queue.isEmpty()){
TreeNode cur = queue.peek();
if(cur == null){
queue.poll();
}else{
return false;
}
}
return true;
}