一、树
1、树简介
树是一种非线性的数据结构，具有n个结点其数据存储形式像一棵倒挂的树，树有一个根结点没有前驱结点，树有多个叶子结点没有后继结点，树有多个中间结点既有前驱结点又有后继结点。
树结构中子树之间不能有交集。
n个结点的树有n-1条边。
像电脑中的文件系统就是树结构存储，树结构如下图所示：
2、树的相关概念
结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为2
树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为3
叶子结点或终端结点：度为0的结点称为叶结点； 如上图：D、H、I、F、G节点为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
度为0的结点称为叶结点； 如上图：D、H、I、F、G节点为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
非终端结点或分支结点：度不为0的结点； 如上图：D、H、I、F、G节点为分支结点
兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：F、G互为堂兄弟结点
结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
森林：由m（m>=0）棵互不相交的树组成的集合称为森林，如下图所示：
二、二叉树
1、二叉树简介
二叉树也是一种特殊的树结构，但是二叉树的度最大只能为2，也就是说，二叉树中只存在度为1的结点和度为2的结点以及叶子结点。
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
2、两种特殊的二叉树
a、满二叉树
满二叉树是每层结点都达到最大值，也就是只存在度为2和度为0的结点。
b、完全二叉树
完全二叉树是与满二叉树编号为0~n-1的结点一一对应时则称为完全二叉树，满二叉树也是一种特殊的完全二叉树。
3、二叉树的性质
- 若规定根的层数为1，则非空二叉树的第k层最多有（2^(k-1)）个结点。
- 若规定根所在的高度为1，则高度为k的二叉树最多有（(2^k)-1）个结点。
- 对于任何一棵二叉树，如果叶子结点数为n，则度为2的结点数为n-1。推导过程如下：
- 具有n个结点的完全二叉树的深度k为log2(n+1) 上取整。
- 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：
- 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
- 若2i+1<n，左孩子序号：2i+1，否则无左孩子
- 若2i+2<n，右孩子序号：2i+2，否则无右孩子
4、二叉树的模拟实现
采用孩子表示法来存存储结点，结点包含数据域、左孩子以及右孩子。
public static class TreeNode{ char val; TreeNode left; TreeNode right; public TreeNode(char val){ this.val=val; } }
a、创建一棵二叉树
使用逐个插入元素的方法进行创建。
例如创建如下图所示的二叉树：
public TreeNode createTree() { TreeNode A=new TreeNode('A'); TreeNode B=new TreeNode('B'); TreeNode C=new TreeNode('C'); TreeNode D=new TreeNode('D'); TreeNode E=new TreeNode('E'); TreeNode F=new TreeNode('F'); A.left=B; A.right=C; B.left=D; B.right=E; C.left=F; root=A; return root; }
b、前序遍历
先序遍历的顺序是：根-左-右，采用递归的方法，先对根进行判断，如果不为空则进行打印，然后递归调用左子树以及右子树。
public void preOrder(TreeNode root) { if(root==null){ return; } System.out.println(root.val); preOrder(root.left); preOrder(root.right); }
c、中序遍历
中序遍历的顺序是左-根-右，同样也是递归的方法，只不过是先递归左子树再打印根结点最后递归右子树。
void inOrder(TreeNode root) { if(root==null){ return; } inOrder(root.left); System.out.println(root.val); inOrder(root.right); }
d、后序遍历
后序遍历的顺序是左-右-根，代码实现与中序遍历类似。
void postOrder(TreeNode root) { if(root==null){ return; } inOrder(root.left); inOrder(root.right); System.out.println(root.val); }
e、层序遍历
层序遍历是一层一层地进行遍历，需要用到先进先出的队列，如果根结点非空，就将根结点存入队列中，然后只要队列不为空就出队，同时若出队元素的左孩子不为空，就将左孩子加入到队列中，如果右孩子不为空，就将右孩子加入到队列中。
public void levelOrder(TreeNode root) { if(root==null){ return; } Queue<TreeNode> que=new LinkedList<>(); que.offer(root); while(!que.isEmpty()){ TreeNode cur=que.peek(); System.out.println(que.poll().val); if(cur.left!=null){ que.offer(cur.left); } if(cur.right!=null){ que.offer(cur.right); } } }
f、获取结点的个数
首先判断根结点是否为空，若不为空就利用递归或遍历的思想分别获取到左孩子和右孩子的结点数，然后再加1表示加上根结点。
/** * 获取树中节点的个数：遍历思路 */ void size(TreeNode root) { if(root==null){ return; } nodeSize++; size(root.left); size(root.right); } /** * 获取节点的个数：子问题的思路 * * @param root * @return */ int size2(TreeNode root) { if(root==null){ return 0; } return size2(root.left)+size2(root.right)+1; }
d、获取叶子结点的个数
与上题解法相似，但是需要新增一个递归入口，如果根结点的左孩子和右孩子都为空则返回1，递归或遍历求左孩子与右孩子的叶子结点数。
/* 获取叶子节点的个数：遍历思路 */ public static int leafSize = 0; void getLeafNodeCount1(TreeNode root) { if(root==null){ return; } if (root.left==null&&root.right==null){ leafSize++; } getLeafNodeCount1(root.left); getLeafNodeCount1(root.right); } /* 获取叶子节点的个数：子问题 */ int getLeafNodeCount2(TreeNode root) { if(root==null){ return 0; } if (root.left==null&&root.right==null){ return 1; } int len1=getLeafNodeCount2(root.right); int len2=getLeafNodeCount2(root.left); return len1+len2; }
f、获取第k层结点的个数
如果一棵树非空，要求第k层的几点的个数，就可以理解为求其左子树和右子树的第k-1层结点之和，如果k为1，表示求第一层则只有根结点，结点个数为1，递归求解。
int getKLevelNodeCount(TreeNode root, int k) { if(root==null){ return 0; } if(k==1){ return 1; } int len1=getKLevelNodeCount(root.right,k-1); int len2=getKLevelNodeCount(root.left,k-1); return len1+len2; }
g、获取树的高度
若树非空，则进行递归求出左子树的高度和右子树的高度并求出两者的较大值还要加1表示根结点的所在层即为求出树的高度。
int getHeight(TreeNode root) { if(root==null){ return 0; } int height1=getHeight(root.left); int height2=getHeight(root.right); return height1>height2?height1+1:height2+1; }
h、判断是否为完全二叉树
依据层序遍历的思想，若树非空，则将根结点先入队，然后进行while循环，若出队列的元素不为空就将其左孩子结点和右孩子结点加入队列否则就跳出循环，对队列进行二次遍历队列中存在不为空的元素则就不是完全二叉树否则就是完全二叉树。
boolean isCompleteTree(TreeNode root) { if(root==null){ return false; } Queue<TreeNode> que=new LinkedList<>(); que.offer(root); while(!que.isEmpty()) { TreeNode cur = que.peek(); if(cur!=null){ que.offer(cur.left); que.offer(cur.right); }else{ break; } que.poll(); } while (!que.isEmpty()){ TreeNode node=que.poll(); if(node==null){ return false; } } return true; }
i、判断是否为平衡树
平衡树就是树中每个结点的左孩子和右孩子的高度差不能大于1。那么就可以利用递归求每个结点的左右子树高度差，若存在大于1的则不为平衡树，否则为平衡树。
public int getHeight(TreeNode root) { if(root==null){ return 0; } int height1=getHeight(root.left); int height2=getHeight(root.right); return height1>height2?height1+1:height2+1; } public boolean isBalanced(TreeNode root) { if (root == null) return true; int len=Math.abs(getHeight(root.left)-getHeight(root.right)); return len<=1&&isBalanced(root.left)&&isBalanced(root.right); }
上述方法的时间复杂度为O(n^2)，那么要想时间复杂度为O(n),则应该怎么做？
那么就可以在求结点的左右高度时进行判断，如果左右高度差大于1就返回-1，表示不平衡，否则就返回左右高度的最大值加1，递归处理，在判断是否为平衡树的函数里只需调用求高度的函数判断其返回值是否为-1。
boolean isBalanceTree2(TreeNode root) { return getLen(root)>0; } int getLen(TreeNode root){ if(root==null){ return 0; } int len1=getLen(root.left); if(len1<0) return -1; int len2=getLen(root.right); if(len2<0) return -1; if(Math.abs(len1-len2)<=1){ return Math.max(len1,len2)+1; }else{ return -1; } }
