本篇文章小编给大家分享一下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 ; } Dequestack=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 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 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 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 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 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引用结果如下:
忍者必须死34399账号登录版 最新版v1.0.138v2.0.72
下载勇者秘境oppo版 安卓版v1.0.5
下载忍者必须死3一加版 最新版v1.0.138v2.0.72
下载绝世仙王官方正版 最新安卓版v1.0.49
下载Goat Simulator 3手机版 安卓版v1.0.8.2
Goat Simulator 3手机版是一个非常有趣的模拟游
Goat Simulator 3国际服 安卓版v1.0.8.2
Goat Simulator 3国际版是一个非常有趣的山羊模
烟花燃放模拟器中文版 2025最新版v1.0
烟花燃放模拟器是款仿真的烟花绽放模拟器类型单机小游戏,全方位
我的世界动漫世界 手机版v友y整合
我的世界动漫世界模组整合包是一款加入了动漫元素的素材整合包,
我的世界贝爷生存整合包 最新版v隔壁老王
我的世界MITE贝爷生存整合包是一款根据原版MC制作的魔改整