溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
java中的遞歸怎么利用二叉樹實現？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
如圖二叉樹：
二叉樹結點結構
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val=x;
}
@Override
public String toString(){
return "val: "+val;
}
}訪問函數
public void visit(TreeNode node){
System.out.print(node.val+" ");
}前序遍歷
對于圖中二叉樹而言其前序遍歷結果為：6 2 0 1 4 5 8 9
二叉樹的前序遍歷即先遍歷根結點再遍歷左結點最后遍歷右結點，使用遞歸如下：
/**
* 遞歸先序遍歷
* */
public void preOrderRecursion(TreeNode node){
if(node==null) //如果結點為空則返回
return;
visit(node);//訪問根節點
preOrderRecursion(node.left);//訪問左孩子
preOrderRecursion(node.right);//訪問右孩子
}非遞歸：
利用棧來實現二叉樹的先序非遞歸遍歷
/**
* 非遞歸先序遍歷二叉樹
* */
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> resultList=new ArrayList<>();
Stack<TreeNode> treeStack=new Stack<>();
if(root==null) //如果為空樹則返回
return resultList;
treeStack.push(root);
while(!treeStack.isEmpty()){
TreeNode tempNode=treeStack.pop();
if(tempNode!=null){
resultList.add(tempNode.val);//訪問根節點
treeStack.push(tempNode.right); //入棧右孩子
treeStack.push(tempNode.left);//入棧左孩子
}
}
return resultList;
}更新：評論里有人說不理解非遞歸的先序遍歷，其實你舉個例子，然后畫個圖就可以理解了，以上圖中的二叉樹為例，先將6入棧，此時List為空，Stack只有一個元素6，進入while循環，彈出棧頂加入List，將6的右孩子和左孩子入棧，此時Stack從棧底到棧頂元素為8,2，List元素為6，由于棧不為空，進入while循環，彈出棧頂2,將2加入List,同時將2的右孩子和左孩子分別入棧，此時Stack從棧底到棧頂的元素為8,4,0, List的元素為6,2，由于棧不為空再次進入while循環…依次下去，彈出0加入List，入棧1,null，此時Stack從棧底到棧頂為8,4,1,null，List為6,2,0，彈出null為空繼續彈出1，如此下去就可以了…
中序遍歷
對于二叉樹的中序遍歷，即先訪問左結點再訪問根節點最后訪問右結點
遞歸方法如下：
/**
* 遞歸中序遍歷
* */
public void preOrderRecursion(TreeNode node){
if(node==null) //如果結點為空則返回
return;
preOrderRecursion(node.left);//訪問左孩子
visit(node);//訪問根節點
preOrderRecursion(node.right);//訪問右孩子
}非遞歸：
在上圖中的二叉樹，其中序遍歷為：0 1 2 4 5 6 8 9
可以看到，二叉樹的中序遍歷如下：
先將根節點入棧，
一直往其左孩子走下去，將左孩子入棧，直到該結點沒有左孩子，則訪問這個結點，如果這個結點有右孩子，則將其右孩子入棧，重復找左孩子的動作，這里有個要判斷結點是不是已經被訪問的問題。
非遞歸中序遍歷（效率有點低），使用map（用set貌似更合理）來判斷結點是否已經被訪問
/**
* 非遞歸中序遍歷
* */
public List<Integer> inorderTraversalNonCur(TreeNode root) {
List<Integer> visitedList=new ArrayList<>();
Map<TreeNode,Integer> visitedNodeMap=new HashMap<>();//保存已訪問的節點
Stack<TreeNode> toBeVisitedNodes=new Stack<>();//待訪問的節點
if(root==null)
return visitedList;
toBeVisitedNodes.push(root);
while(!toBeVisitedNodes.isEmpty()){
TreeNode tempNode=toBeVisitedNodes.peek(); //注意這里是peek而不是pop
while(tempNode.left!=null){ //如果該節點的左節點還未被訪問，則需先訪問其左節點
if(visitedNodeMap.get(tempNode.left)!=null) //該節點已經被訪問（不存在某個節點已被訪問但其左節點還未被訪問的情況）
break;
toBeVisitedNodes.push(tempNode.left);
tempNode=tempNode.left;
}
tempNode=toBeVisitedNodes.pop();//訪問節點
visitedList.add(tempNode.val);
visitedNodeMap.put(tempNode, 1);//將節點加入已訪問map
if(tempNode.right!=null) //將右結點入棧
toBeVisitedNodes.push(tempNode.right);
}
return visitedList;
}Discuss中有人給出更簡潔的方法
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur!=null || !stack.empty()){
while(cur!=null){
stack.add(cur);
cur = cur.left;
}
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
return list;
}后序遍歷
遞歸代碼就不貼了
如果之前的非遞歸中序遍歷使用map的方法理解后，后序遍歷的話我們也可以使用一個map來保存那些已經被訪問的結點，后序遍歷即先訪問左孩子再訪問右孩子最后訪問根結點。
非遞歸代碼：
/**
* 非遞歸后序遍歷
* */
public List<Integer> postOrderNonCur(TreeNode root){
List<Integer> resultList=new ArrayList<>();
if(root==null)
return resultList;
Map<TreeNode,Integer> visitedMap=new HashMap<>();
Stack<TreeNode> toBeVisitedStack=new Stack<>();
toBeVisitedStack.push(root);
while(!toBeVisitedStack.isEmpty()){
TreeNode tempNode=toBeVisitedStack.peek(); //注意這里是peek而不是pop
if(tempNode.left==null && tempNode.right==null){ //如果沒有左右孩子則訪問
resultList.add(tempNode.val);
visitedMap.put(tempNode, 1);
toBeVisitedStack.pop();
continue;
}else if(!((tempNode.left!=null&&visitedMap.get(tempNode.left)==null )|| (tempNode.right!=null && visitedMap.get(tempNode.right)==null))){
//如果節點的左右孩子均已被訪問
resultList.add(tempNode.val);
toBeVisitedStack.pop();
visitedMap.put(tempNode, 1);
continue;
}
if(tempNode.left!=null){
while(tempNode.left!=null && visitedMap.get(tempNode.left)==null){//左孩子沒有被訪問
toBeVisitedStack.push(tempNode.left);
tempNode=tempNode.left;
}
}
if(tempNode.right!=null){
if(visitedMap.get(tempNode.right)==null){//右孩子沒有被訪問
toBeVisitedStack.push(tempNode.right);
}
}
}
return resultList;
}Discuss中有人給出了一個”巧“的方法，即先采用類似先序遍歷，先遍歷根結點再右孩子最后左孩子（先序是先根結點再左孩子最后右孩子），最后把遍歷的序列逆轉即得到了后序遍歷
public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
List<Integer> ret = new ArrayList<>();
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
ret.add(node.val);
stack.push(node.left);
stack.push(node.right);
}
}
Collections.reverse(ret);
return ret;
} 層序遍歷
層序遍歷也即寬度優先搜索，一層一層搜索，非遞歸代碼如下：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resultList=new ArrayList<>();
int levelNum=0;//記錄某層具有多少個節點
Queue<TreeNode> treeQueue=new LinkedList<>();
treeQueue.add(root);
while(!treeQueue.isEmpty()){
levelNum=treeQueue.size();
List<Integer> levelList=new ArrayList<>();
while(levelNum>0){
TreeNode tempNode=treeQueue.poll();
if(tempNode!=null){
levelList.add(tempNode.val);
treeQueue.add(tempNode.left);
treeQueue.add(tempNode.right);
}
levelNum--;
}
if(levelList.size()>0)
resultList.add(levelList);
}
return resultList;
}看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
