物有本末术瓮，事有始終康聂，知所先后，則近道矣胞四。-----題記恬汁。
今天小編跟大家探討的是遞歸，遞歸的基本意思是不斷調(diào)用自己實現(xiàn)邏輯辜伟，可減少代碼量氓侧。它遠看像一個穿短裙的美人，然而不管多看幾眼游昼，如若沒有相關經(jīng)驗甘苍，恐怕這種美也只看到了十分之三。
我們從jvm烘豌，在字節(jié)碼層面看看遞歸是到底是怎么回事载庭，把那十分之七的靈魂之美補上，以后的江湖路上廊佩，可賞他人不知矣囚聚！
先看一段二叉樹的insert方法的代碼（二叉樹有很多種，下面舉的例子是一棵左節(jié)點<根節(jié)點<右節(jié)點的樹）：
@SuppressWarnings("unchecked")
public BinaryTreeNode<Integer> insert(BinaryTreeNode<Integer> node,Integer data){
//如果當前節(jié)點的權值大于data标锄，那么插入到左孩子節(jié)點上
if((int)node.data.toString()>data){
node.left=insert(node.left,data);
}
//如果當前節(jié)點的權值大于data顽铸，那么插入到左孩子節(jié)點上
if((int)node.data.toString()<data){
node.right=insert(node.right,data);
}
return node;
}
}
insert方法中涉及到遞歸，下面我們仔細研究一下哈：
0: aload_1
1: ifnonnull 13
4: new #1 // class tree/BinaryTreeNode
7: dup
8: aload_2
9: invokespecial #45 // Method "<init>":(Ljava/lang/Object;)V
12: areturn
13: aload_1
14: getfield #20 // Field data:Ljava/lang/Object;
23: aload_2
30: if_icmple 79
36: getfield #24 // Field left:Ltree/BinaryTreeNode;
39: aload_2
40: invokevirtual #53 // Method insert:(Ltree/BinaryTreeNode;Ljava/lang/Object;)Ltree/BinaryTreeNode;
43: putfield #24 // Field left:Ltree/BinaryTreeNode;
79: aload_1
80: areturn
上面是insert方法的jvm執(zhí)行的指令料皇，我摘抄了部分關鍵點說明一下遞歸是怎么做的：
insert函數(shù)棧中的局部變量表中的參數(shù)：第一個是當前樹節(jié)點對象（暫且稱為ref0）谓松，第二個是函數(shù)中傳進來的node對象的引用（稱為ref1）星压，第三個是傳進來的常量data（在常量池中#20）
0: aload_1 將第一個引用類型局部變量推送至棧頂，那個引用也就是insert方法中的node對象的引用（ref1）
1 : ifnonnull 13 如果ref1不為空鬼譬，則跳到13行執(zhí)行
4-12 : 如果是空娜膘，則此節(jié)點即是我們要插入的節(jié)點，調(diào)用它的構造函數(shù)<init>方法优质，將data值賦給它竣贪，然后areturn（將這個新生成的對象引用返回）
13 : aload_1 將ref1壓入棧頂
14：getfield 將常量池中當前對象ref1的data的值壓入棧頂
23：aload_2 將傳入的data值壓入棧頂
30：if_icmple 79，如果傳入的data值小于ref1的權值巩螃，那么就跳到79執(zhí)行
36：getfield #24 演怎，將常量池中#24，left壓入棧中避乏，即left常量的引用
39：aload_2 將data值壓入棧中爷耀。實際上36、39兩步的指令都是在為下面40行做準備淑际，40行調(diào)用insert方法畏纲，傳遞給它需要的參數(shù)
40：invokevirtrual #53扇住，調(diào)用insert方法春缕，將36、39行準備的兩個參數(shù)帶過去
43：putfield #24 艘蹋，給當前實例ref1的left字段賦值
79：aload_1 锄贼，將當前實例ref1壓入棧中
80：areturn ，將棧頂?shù)膔ef1返回
如果不太懂女阀，我畫了兩張圖宅荤，幫助理解：
image.png
假設找到了為空的左節(jié)點，new了一個D節(jié)點浸策，并逐層返回：
image.png
棧幀3：B節(jié)點不具有左節(jié)點冯键，new一個新的節(jié)點對象D，賦值data庸汗， 此時左子樹的遞歸就結(jié)束了惫确，字節(jié)碼指令跳回到棧幀2的第43行， 執(zhí)行putfield指令蚯舱，也就是將棧幀3返回的節(jié)點對象D賦值給B節(jié)點的left屬性改化。
棧幀繼續(xù)返回對象引用，不斷構建節(jié)點之間的關系枉昏，大家一定要能腦補出這段畫面哦陈肛。
光說不練假把式，下面是小編自己寫的二叉樹及相關類兄裂，好好品味遞歸是怎么實現(xiàn)的吧：
一句旱、二叉樹類：
package tree;
/**
* 二叉樹數(shù)據(jù)載體類
* @author tery
* @param <T>
*/
public class BinaryTreeNode<T> {
private T data;
private BinaryTreeNode<T> left;
private BinaryTreeNode<T> right;
public BinaryTreeNode(T data){
this.data=data;
left=right=null;
}
public T getData(){
return this.data;
}
public void setData(T data){
this.data=data;
}
public BinaryTreeNode<T> getLeft() {
return left;
}
public void setLeft(BinaryTreeNode<T> left) {
this.left = left;
}
public BinaryTreeNode<T> getRight() {
return right;
}
public void setRight(BinaryTreeNode<T> right) {
this.right = right;
}
/**
* 插入權值
* @param node
* @param data
* @return
*/
@SuppressWarnings("unchecked")
public BinaryTreeNode<T> insert(BinaryTreeNode<T> node,Integer data){
//如果當前節(jié)點的權值大于data阳藻，那么插入到左孩子節(jié)點上
if(Integer.valueOf(node.data.toString())>data){
node.left=insert(node.left,data);
}
//如果當前節(jié)點的權值大于data，那么插入到左孩子節(jié)點上
if(Integer.valueOf(node.data.toString())<data){
node.right=insert(node.right,data);
}
//相等拋異常
if(Integer.valueOf(node.data.toString())==data){
throw new IllegalArgumentException("the data:"+data+"is already exsist in the tree");
}
return node;
}
}
二谈撒、二叉排序樹：
package tree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 二叉排序樹（Binary Sort Tree）又稱二叉查找樹.它或者是一棵空樹稚配；或者是具有下列性質(zhì)的二叉樹：
* （1）若左子樹不空,則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
* （2）若右子樹不空,則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值港华；
* （3）左道川、右子樹也分別為二叉排序樹
*
* @author tery
*
* @param <T>
*/
public class BinarySearchTree<T extends Comparable> {
BinaryTreeNode<T> root;
public BinarySearchTree(BinaryTreeNode<T> root) {
this.root = root;
}
public BinaryTreeNode<T> getRoot() {
return this.root;
}
/**
* 最小值
* @return
*/
public T findMin() {
if (root == null) {
return null;
}
return findMin(root).getData();
}
private BinaryTreeNode<T> findMin(BinaryTreeNode<T> root) {
if (root == null) {
return null;
} else if (root.getLeft() == null) {
return root;
} else {
return findMin(root.getLeft());
}
}
/**
* 最大值
*
* @return
*/
public T findMax() {
if (root == null) {
return null;
}
return findMax(root).getData();
}
public BinaryTreeNode<T> findMax(BinaryTreeNode<T> root) {
if (root == null) {
return null;
} else if (root.getRight() == null) {
return root;
} else {
return findMax(root.getRight());
}
}
/*
* 獲取高度
*/
public int height() {
return height(root);
}
private int height(BinaryTreeNode<T> node) {
if (node == null) {
return 0;
} else {
int leftHeight = height(node.getLeft());
int rightHeight = height(node.getRight());
if (leftHeight > rightHeight) {
return leftHeight + 1;
} else {
return rightHeight + 1;
}
}
}
/**
* 節(jié)點數(shù)
*
* @return
*/
public int size() {
return getSize(root);
}
private int getSize(BinaryTreeNode<T> node) {
if (node == null) {
return 0;
}
return getSize(node.getLeft()) + 1 + getSize(node.getRight());
}
/**
* 是否合法
*
* @return
*/
public boolean isValid() {
return isValid(root);
}
@SuppressWarnings("unchecked")
private boolean isValid(BinaryTreeNode<T> node) {
if (node == null) {
return true;
}
if (node.getLeft() != null && findMax(node.getLeft()).getData().compareTo(node.getData()) > 0) {
return false;
}
if (node.getRight() != null && findMin(node.getRight()).getData().compareTo(node.getData()) < 0) {
return false;
}
if (!isValid(node.getLeft()) || !isValid(node.getRight())) {
return false;
}
return true;
}
/**
* 刪除節(jié)點數(shù)據(jù)
* @param t
*/
public void remove(T t) {
remove(t, root);
}
@SuppressWarnings("unchecked")
private BinaryTreeNode<T> remove(T t, BinaryTreeNode<T> node) {
if(node==null){
return node;
}
int result=t.compareTo(node.getData());
if(result>0){
remove(t,node.getRight());
}else if(result<0){
remove(t,node.getLeft());
}else{
if(node.getLeft()!=null && node.getRight()!=null){
node.setData(findMin(node.getRight()).getData());
//把右孩子做為根節(jié)點，執(zhí)行刪除邏輯后即可將值為t的元素刪除
node.setRight(remove(node.getData(),node.getRight()));
}else{
//左右有一個為空立宜，則直接賦值不為空的那個節(jié)點
node=node.getLeft()==null?node.getRight():node.getLeft();
}
}
return node;
}
/**
* 得到最小的那個公共祖先
*
* @param t1
* @param t2
* @return
*/
@SuppressWarnings("unchecked")
public T getLowestCommonAncestor(BinaryTreeNode<T> node,T t1, T t2) {
if(node==null){
return null;
}
//公共祖先在左孩子
if(t1.compareTo(node.getData())<0&&t2.compareTo(node.getData())<0){
//以左節(jié)點為根節(jié)點冒萄，一直找到右節(jié)點為空，函數(shù)棧中存留的那個節(jié)點即是要找的公共祖先橙数。
//實際上下面這個語句在jvm編譯后執(zhí)行的是areturn(即返回一個reference類型數(shù)據(jù)）
return getLowestCommonAncestor(node.getLeft(), t1, t2);
//公共祖先在右孩子
}else if(t1.compareTo(node.getData())>0&&t2.compareTo(node.getData())>0){
//
return getLowestCommonAncestor(node.getRight(), t1, t2);
}else{
//當前節(jié)點的權值在t1和t2的之間尊流，那當前節(jié)點即是公共祖先,拿到權值返回即可
return node.getData();
}
}
/**
* 返回所有滿足下列條件的節(jié)點的值： n1 <= n <= n2 , n 為 該二叉查找樹中的某一節(jié)點
*
* @param n1
* @param n2
* @return
*/
public List<T> getBetweenNode(T n1, T n2) {
List<T> elements=new ArrayList<>();
getBetweenNode(elements,root,n1,n2);
return elements;
}
@SuppressWarnings("unchecked")
public List<T> getBetweenNode(List<T> elements ,BinaryTreeNode<T> node,T n1, T n2){
if(node==null){
return null;
}
if(node.getData().compareTo(n1)>=0&&node.getData().compareTo(n2)<=0){
elements.add(node.getData());
}else if(node.getData().compareTo(n1)<0){
getBetweenNode(elements,node.getLeft(),n1,n2);
}else if(node.getData().compareTo(n2)>0){
getBetweenNode(elements,node.getRight(),n1,n2);
}
return elements;
}
/**
* 按層級遍歷二叉樹
*
* @return
*/
public List<T> getLevelList() {
List<T> result=new ArrayList<>();
if(root==null){
return result;
}
Queue<BinaryTreeNode<T>> queue=new LinkedList<>();
BinaryTreeNode<T> node=root;
queue.add(root);
while(!queue.isEmpty()){
result.add(node.getData());
queue.remove(node);
if(node.getLeft()!=null){
queue.add(node.getLeft());
}
if(node.getRight()!=null){
queue.add(node.getRight());
}
}
return result;
}
}
三、二叉樹工具類：
image.png
1. 前根序遍歷：先遍歷根結(jié)點灯帮，然后遍歷左子樹崖技，最后遍歷右子樹。（ABDHECFG）
2.中根序遍歷：先遍歷左子樹钟哥，然后遍歷根結(jié)點迎献，最后遍歷右子樹。（HDBEAFCG）
3.后根序遍歷：先遍歷左子樹腻贰，然后遍歷右子樹吁恍，最后遍歷根節(jié)點（HDEBFGCA）
package tree;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class BinaryTreeUtil {
/**
* 用遞歸的方式實現(xiàn)二叉樹的前序遍歷
* @param root
* @return
*/
public static<T> List<T> preOrderVisit(BinaryTreeNode<T> root){
List<T> result=new ArrayList<>();
preOrderVisit(root,result);
return result;
}
private static<T> void preOrderVisit(BinaryTreeNode<T> node, List<T> result) {
//如果節(jié)點為空，返回
if(node==null){
return;
}
//不為空播演，則加入節(jié)點的值
result.add(node.getData());
//先遞歸左孩子
preOrderVisit(node.getLeft(),result);
//再遞歸右孩子
preOrderVisit(node.getRight(),result);
}
/**
* 用遞歸的方式實現(xiàn)二叉樹的中序遍歷
* @param root
* @return
*/
public static<T> List<T> inOrderVisit(BinaryTreeNode<T> root){
List<T> result=new ArrayList<T>();
inOrderVisit(root,result);
return result;
}
private static<T> void inOrderVisit(BinaryTreeNode<T> node, List<T> result) {
if(node==null){
return;
}
inOrderVisit(node.getLeft(),result);
result.add(node.getData());
inOrderVisit(node.getRight(),result);
}
/**
* 用遞歸的方式實現(xiàn)二叉樹的后遍歷
* @param root
* @return
*/
public static<T> List<T> postOrderVisit(BinaryTreeNode<T> root){
List<T> result=new ArrayList<T>();
postOrderVisit(root,result);
return result;
}
private static<T> void postOrderVisit(BinaryTreeNode<T> node, List<T> result) {
if(node==null){
return;
}
postOrderVisit(node.getLeft(),result);
postOrderVisit(node.getRight(),result);
result.add(node.getData());
}
/**
* 用非遞歸的方式實現(xiàn)前序遍歷
* @param root
* @return
*/
public static<T> List<T> preOrderVisitWithoutRecursion(BinaryTreeNode<T> root){
List<T> result=new ArrayList<T>();
Stack<BinaryTreeNode<T>> stack=new Stack<>();
if(root!=null){
stack.push(root);
}
while(!stack.isEmpty()){
BinaryTreeNode<T> node=stack.pop();
result.add(node.getData());
if(node.getRight()!=null){
stack.push(node.getRight());
}
if(node.getLeft()!=null){
stack.push(node.getLeft());
}
}
return result;
}
/**
* 用非遞歸的方式實現(xiàn)中序遍歷
* @param root
* @return
*/
public static<T> List<T> inOrderVisitWithoutRecursion(BinaryTreeNode<T> root){
List<T> result=new ArrayList<T>();
Stack<BinaryTreeNode<T>> stack=new Stack<>();
BinaryTreeNode<T> node=root;
while(node!=null || !stack.isEmpty()){
while(node!=null){
stack.push(node);
node=node.getLeft();
}
BinaryTreeNode<T> currentNode=stack.pop();
result.add(currentNode.getData());
node=currentNode.getRight();
}
return result;
}
public static void main(String[] args) {
BinaryTreeNode<Integer> tree=new BinaryTreeNode<Integer>(10);
tree.insert(tree,8);
tree.insert(tree,5);
tree.insert(tree,9);
}
}
關于遞歸冀瓦，請各位再深入思考一下。里面涉及到了jvm函數(shù)調(diào)用層面的知識写烤，如果不懂翼闽，建議大家去看看jvm的書，了解jvm怎么執(zhí)行代碼洲炊，那就可以輕輕松松地理解遞歸到底是怎么執(zhí)行的了感局。
