Java二叉树实现及递归与非递归遍历实现
生活随笔
收集整理的這篇文章主要介紹了
Java二叉树实现及递归与非递归遍历实现
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
樹的遍歷分兩種：
1、深度優先遍歷
1.1 遞歸算法實現
2.2 非遞歸算法實現（使用棧存儲）
2、廣度優先遍歷（使用隊列存儲）
import java.util.*; /**
* 類功能描述: 二叉樹遍歷算法Java實現
*
* @version 1.0.0
* @auther Create by Barry
* @date Create on 2018/3/12.
* @history
*/
public class BinaryTree {
private Node root;
private BinaryTree(Object data){
this.root = new Node(data, null, null);
} /**
* 1、 深度優先遍歷
* 1.1 遞歸先序遍歷
*/
public void preOrderTraverse(Node root){
System.out.println(root.data);
preOrderTraverse(root.leftChild);
preOrderTraverse(root.rightChild);
} /**
* 1、 深度優先遍歷
* 1.2 實現非遞歸先序遍歷
*/
public void preOrder(){
Stack stack = new Stack();
System.out.println(root.data);
stack.push(root);
while(!stack.isEmpty()){
Node element = (Node)stack.pop();
System.out.println(element.data);
if(element.rightChild != null){
stack.push(element.rightChild);
}
if(element.leftChild != null){
stack.push(element.leftChild);
}
}
} /**
* 2、 廣度優先遍歷
*/
public List<Node> breadthTraverse(Node root){
List<Node> allNodes = new LinkedList<>();
if(root == null){
return allNodes;
}
Deque<Node> queue = new ArrayDeque<>();
queue.add(root);
while(!queue.isEmpty()){
Node currentNode = queue.poll();
allNodes.add(currentNode);
if(currentNode.leftChild != null){
queue.add(currentNode.leftChild);
}
if(currentNode.rightChild != null){
queue.add(currentNode.rightChild);
}
}
return allNodes;
} class Node{
private Object data;
private Node leftChild;
private Node rightChild;
public Node(Object data, Node leftChild, Node rightChild){
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
}
總結
以上是生活随笔為你收集整理的Java二叉树实现及递归与非递归遍历实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 煤矿用气象站：保障矿区安全和生产管理的防
- 下一篇： 一体化防爆气象仪：一种多个参数监测的防爆