溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“Java實現二叉樹的代碼怎么寫”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java實現二叉樹的代碼怎么寫”吧!
以此圖為例，完整代碼如下：
//基礎二叉樹實現
//使用左右孩子表示法
import java.util.*;
import java.util.Deque;
public class myBinTree {
private static class TreeNode{
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public static TreeNode build(){
TreeNode nodeA=new TreeNode('A');
TreeNode nodeB=new TreeNode('B');
TreeNode nodeC=new TreeNode('C');
TreeNode nodeD=new TreeNode('D');
TreeNode nodeE=new TreeNode('E');
TreeNode nodeF=new TreeNode('F');
TreeNode nodeG=new TreeNode('G');
TreeNode nodeH=new TreeNode('H');
nodeA.left=nodeB;
nodeA.right=nodeC;
nodeB.left=nodeD;
nodeB.right=nodeE;
nodeE.right=nodeH;
nodeC.left=nodeF;
nodeC.right=nodeG;
return nodeA;
}
//方法1(遞歸)
//先序遍歷: 根左右
public static void preOrder(TreeNode root){
if(root==null){
return;
}
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}
//方法1(遞歸)
//中序遍歷
public static void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
//方法1(遞歸)
//后序遍歷
public static void postOrder(TreeNode root){
if(root==null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}
//方法2(迭代)
//先序遍歷 (迭代)
public static void preOrderNonRecursion(TreeNode root){
if(root==null){
return ;
}
Deque<TreeNode> stack=new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode cur=stack.pop();
System.out.print(cur.val+" ");
if(cur.right!=null){
stack.push(cur.right);
}
if(cur.left!=null){
stack.push(cur.left);
}
}
}
//方法2(迭代)
//中序遍歷 (迭代)
public static void inorderTraversalNonRecursion(TreeNode root) {
if(root==null){
return ;
}
Deque<TreeNode> stack=new LinkedList<>();
// 當前走到的節點
TreeNode cur=root;
while (!stack.isEmpty() || cur!=null){
// 不管三七二十一，先一路向左走到根兒~
while (cur!=null){
stack.push(cur);
cur=cur.left;
}
// 此時cur為空，說明走到了null，此時棧頂就存放了左樹為空的節點
cur=stack.pop();
System.out.print(cur.val+" ");
// 繼續訪問右子樹
cur=cur.right;
}
}
//方法2(迭代)
//后序遍歷 (迭代)
public static void postOrderNonRecursion(TreeNode root){
if(root==null){
return;
}
Deque<TreeNode> stack=new LinkedList<>();
TreeNode cur=root;
TreeNode prev=null;
while (!stack.isEmpty() || cur!=null){
while (cur!=null){
stack.push(cur);
cur=cur.left;
}
cur=stack.pop();
if(cur.right==null || prev==cur.right){
System.out.print(cur.val+" ");
prev=cur;
cur=null;
}else {
stack.push(cur);
cur=cur.right;
}
}
}
//方法1(遞歸)
//傳入一顆二叉樹的根節點，就能統計出當前二叉樹中一共有多少個節點，返回節點數
//此時的訪問就不再是輸出節點值，而是計數器 + 1操作
public static int getNodes(TreeNode root){
if(root==null){
return 0;
}
return 1+getNodes(root.left)+getNodes(root.right);
}
//方法2(迭代)
//使用層序遍歷來統計當前樹中的節點個數
public static int getNodesNoRecursion(TreeNode root){
if(root==null){
return 0;
}
int size=0;
Deque<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
size++;
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
return size;
}
//方法1(遞歸)
//傳入一顆二叉樹的根節點，就能統計出當前二叉樹的葉子結點個數
public static int getLeafNodes(TreeNode root){
if(root==null){
return 0;
}
if(root.left==null && root.right==null){
return 1;
}
return getLeafNodes(root.left)+getLeafNodes(root.right);
}
//方法2(迭代)
//使用層序遍歷來統計葉子結點的個數
public static int getLeafNodesNoRecursion(TreeNode root){
if(root==null){
return 0;
}
int size=0;
Deque<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode cur=queue.poll();
if(cur.left==null && cur.right==null){
size++;
}
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
return size;
}
//層序遍歷
public static void levelOrder(TreeNode root) {
if(root==null){
return ;
}
// 借助隊列來實現遍歷過程
Deque<TreeNode> queue =new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size=queue.size();
for (int i = 0; i < size; i++) {
TreeNode cur=queue.poll();
System.out.print(cur.val+" ");
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
}
}
//傳入一個以root為根節點的二叉樹，就能求出該樹的高度
public static int height(TreeNode root){
if(root==null){
return 0;
}
return 1+ Math.max(height(root.left),height(root.right));
}
//求出以root為根節點的二叉樹第k層的節點個數
public static int getKLevelNodes(TreeNode root,int k){
if(root==null || k<=0){
return 0;
}
if(k==1){
return 1;
}
return getKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1);
}
//判斷當前以root為根節點的二叉樹中是否包含指定元素val，
//若存在返回true，不存在返回false
public static boolean contains(TreeNode root,char value){
if(root==null){
return false;
}
if(root.val==value){
return true;
}
return contains(root.left,value) || contains(root.right,value);
}
public static void main(String[] args) {
TreeNode root=build();
System.out.println("方法1(遞歸)：前序遍歷的結果為:");
preOrder(root);
System.out.println();
System.out.println("方法2(迭代)：前序遍歷的結果為:");
preOrderNonRecursion(root);
System.out.println();
System.out.println("方法1(遞歸)：中序遍歷的結果為:");
inOrder(root);
System.out.println();
System.out.println("方法2(迭代)：中序遍歷的結果為:");
inorderTraversalNonRecursion(root);
System.out.println();
System.out.println("方法1(遞歸)：后序遍歷的結果為:");
postOrder(root);
System.out.println();
System.out.println("方法2(迭代)：后序遍歷的結果為:");
postOrderNonRecursion(root);
System.out.println();
System.out.println();
System.out.println("層序遍歷的結果為:");
levelOrder(root);
System.out.println();
System.out.println();
System.out.println("方法1(遞歸)：當前二叉樹一共有:"+getNodes(root)+"個節點數");
System.out.println("方法2(迭代)：當前二叉樹一共有:"+getNodesNoRecursion(root)+"個節點數");
System.out.println("方法1(遞歸)：當前二叉樹一共有:"+getLeafNodes(root)+"個葉子節點數");
System.out.println("方法2(迭代)：當前二叉樹一共有:"+getLeafNodesNoRecursion(root)+"個葉子節點數");
System.out.println(contains(root,'E'));
System.out.println(contains(root,'P'));
System.out.println("當前二叉樹的高度為:"+height(root));
System.out.println("當前二叉樹第3層的節點個數為:"+getKLevelNodes(root,3));
}
}如上main引用結果如下：
到此，相信大家對“Java實現二叉樹的代碼怎么寫”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
