利用java如何實現創建并遍歷二叉樹？針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
用java實現的數組創建二叉樹以及遞歸先序遍歷，遞歸中序遍歷，遞歸后序遍歷，非遞歸前序遍歷，非遞歸中序遍歷，非遞歸后序遍歷，深度優先遍歷，廣度優先遍歷8種遍歷方式：
package myTest;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
public class myClass {
public static void main(String[] args) {
// TODO Auto-generated method stub
myClass tree = new myClass();
int[] datas = new int[]{1,2,3,4,5,6,7,8,9};
List<Node> nodelist = new LinkedList<>();
tree.creatBinaryTree(datas, nodelist);
Node root = nodelist.get(0);
System.out.println("遞歸先序遍歷：");
tree.preOrderTraversal(root);
System.out.println();
System.out.println("非遞歸先序遍歷：");
tree.preOrderTraversalbyLoop(root);
System.out.println();
System.out.println("遞歸中序遍歷：");
tree.inOrderTraversal(root);
System.out.println();
System.out.println("非遞歸中序遍歷：");
tree.inOrderTraversalbyLoop(root);
System.out.println();
System.out.println("遞歸后序遍歷：");
tree.postOrderTraversal(root);
System.out.println();
System.out.println("非遞歸后序遍歷：");
tree.postOrderTraversalbyLoop(root);
System.out.println();
System.out.println("廣度優先遍歷：");
tree.bfs(root);
System.out.println();
System.out.println("深度優先遍歷：");
List<List<Integer>> rst = new ArrayList<>();
List<Integer> list = new ArrayList<>();
tree.dfs(root,rst,list);
System.out.println(rst);
}
/**
*
* @param datas 實現二叉樹各節點值的數組
* @param nodelist 二叉樹list
*/
private void creatBinaryTree(int[] datas,List<Node> nodelist){
//將數組變成node節點
for(int nodeindex=0;nodeindex<datas.length;nodeindex++){
Node node = new Node(datas[nodeindex]);
nodelist.add(node);
}
//給所有父節點設定子節點
for(int index=0;index<nodelist.size()/2-1;index++){
//編號為n的節點他的左子節點編號為2*n 右子節點編號為2*n+1 但是因為list從0開始編號，所以還要+1
//這里父節點有1（2,3）,2（4,5）,3（6,7）,4（8,9） 但是最后一個父節點有可能沒有右子節點 需要單獨處理
nodelist.get(index).setLeft(nodelist.get(index*2+1));
nodelist.get(index).setRight(nodelist.get(index*2+2));
}
//單獨處理最后一個父節點 因為它有可能沒有右子節點
int index = nodelist.size()/2-1;
nodelist.get(index).setLeft(nodelist.get(index*2+1)); //先設置左子節點
if(nodelist.size() % 2 == 1){ //如果有奇數個節點，最后一個父節點才有右子節點
nodelist.get(index).setRight(nodelist.get(index*2+2));
}
}
/**
* 遍歷當前節點的值
* @param nodelist
* @param node
*/
public void checkCurrentNode(Node node){
System.out.print(node.getVar()+" ");
}
/**
* 先序遍歷二叉樹
* @param root 二叉樹根節點
*/
public void preOrderTraversal(Node node){
if (node == null) //很重要，必須加上 當遇到葉子節點用來停止向下遍歷
return;
checkCurrentNode(node);
preOrderTraversal(node.getLeft());
preOrderTraversal(node.getRight());
}
/**
* 中序遍歷二叉樹
* @param root 根節點
*/
public void inOrderTraversal(Node node){
if (node == null) //很重要，必須加上
return;
inOrderTraversal(node.getLeft());
checkCurrentNode(node);
inOrderTraversal(node.getRight());
}
/**
* 后序遍歷二叉樹
* @param root 根節點
*/
public void postOrderTraversal(Node node){
if (node == null) //很重要，必須加上
return;
postOrderTraversal(node.getLeft());
postOrderTraversal(node.getRight());
checkCurrentNode(node);
}
/**
* 非遞歸前序遍歷
* @param node
*/
public void preOrderTraversalbyLoop(Node node){
Stack<Node> stack = new Stack();
Node p = node;
while(p!=null || !stack.isEmpty()){
while(p!=null){ //當p不為空時，就讀取p的值，并不斷更新p為其左子節點，即不斷讀取左子節點
checkCurrentNode(p);
stack.push(p); //將p入棧
p = p.getLeft();
}
if(!stack.isEmpty()){
p = stack.pop();
p = p.getRight();
}
}
}
/**
* 非遞歸中序遍歷
* @param node
*/
public void inOrderTraversalbyLoop(Node node){
Stack<Node> stack = new Stack();
Node p = node;
while(p!=null || !stack.isEmpty()){
while(p!=null){
stack.push(p);
p = p.getLeft();
}
if(!stack.isEmpty()){
p = stack.pop();
checkCurrentNode(p);
p = p.getRight();
}
}
}
/**
* 非遞歸后序遍歷
* @param node
*/
public void postOrderTraversalbyLoop(Node node){
Stack<Node> stack = new Stack<>();
Node p = node,prev = node;
while(p!=null || !stack.isEmpty()){
while(p!=null){
stack.push(p);
p = p.getLeft();
}
if(!stack.isEmpty()){
Node temp = stack.peek().getRight();
if(temp == null||temp == prev){
p = stack.pop();
checkCurrentNode(p);
prev = p;
p = null;
}else{
p = temp;
}
}
}
}
/**
* 廣度優先遍歷（從上到下遍歷二叉樹）
* @param root
*/
public void bfs(Node root){
if(root == null) return;
LinkedList<Node> queue = new LinkedList<Node>();
queue.offer(root); //首先將根節點存入隊列
//當隊列里有值時，每次取出隊首的node打印，打印之后判斷node是否有子節點，若有，則將子節點加入隊列
while(queue.size() > 0){
Node node = queue.peek();
queue.poll(); //取出隊首元素并打印
System.out.print(node.var+" ");
if(node.left != null){ //如果有左子節點，則將其存入隊列
queue.offer(node.left);
}
if(node.right != null){ //如果有右子節點，則將其存入隊列
queue.offer(node.right);
}
}
}
/**
* 深度優先遍歷
* @param node
* @param rst
* @param list
*/
public void dfs(Node node,List<List<Integer>> rst,List<Integer> list){
if(node == null) return;
if(node.left == null && node.right == null){
list.add(node.var);
/* 這里將list存入rst中時，不能直接將list存入，而是通過新建一個list來實現，
* 因為如果直接用list的話，后面remove的時候也會將其最后一個存的節點刪掉*/
rst.add(new ArrayList<>(list));
list.remove(list.size()-1);
}
list.add(node.var);
dfs(node.left,rst,list);
dfs(node.right,rst,list);
list.remove(list.size()-1);
}
/**
* 節點類
* var 節點值
* left 節點左子節點
* right 右子節點
*/
class Node{
int var;
Node left;
Node right;
public Node(int var){
this.var = var;
this.left = null;
this.right = null;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right) {
this.right = right;
}
public int getVar() {
return var;
}
public void setVar(int var) {
this.var = var;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
}
}運行結果：
遞歸先序遍歷：
1 2 4 8 9 5 3 6 7
非遞歸先序遍歷：
1 2 4 8 9 5 3 6 7
遞歸中序遍歷：
8 4 9 2 5 1 6 3 7
非遞歸中序遍歷：
8 4 9 2 5 1 6 3 7
遞歸后序遍歷：
8 9 4 5 2 6 7 3 1
非遞歸后序遍歷：
8 9 4 5 2 6 7 3 1
廣度優先遍歷：
1 2 3 4 5 6 7 8 9
深度優先遍歷：
[[1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5], [1, 3, 6], [1, 3, 7]]
關于利用java如何實現創建并遍歷二叉樹問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
