一、分析
二叉树是n个结点所构成的集合，它或为空树，或为非空树。对于非空树，它有且仅有一个根结点，且除根结点以外的其余结点分为两个互不相交的子集，分别称为左子树和右子树，它们本身又都是二叉树。
显而易见，二叉树具有递归的性质，因此表示二叉树的结点至少要包含3个域：数据域、左指针、右指针。在Java中，我们可以将二叉树的结点视为一个类，其中含有左子树地址、右子树地址和数据三个属性，每个结点即使类的实例化对象。因为二叉树的递归性质，所以我们可以通过递归来实现二叉树地求深度、求叶子结点的个数、先序、中序、后序遍历，而层序遍历则可以通过队列来实现。
二、实现
1、定义结点类
1 class InitBiTree{ 2 3 private String data = null; 4 5 private InitBiTree lchild = null; 6 7 private InitBiTree rchild = null; 8 9 public String getData() { 10 return data; 11 } 12 13 public void setData(String data) { 14 this.data = data; 15 } 16 17 public InitBiTree getLchild() { 18 return lchild; 19 } 20 21 public void setLchild(InitBiTree lchild) { 22 this.lchild = lchild; 23 } 24 25 public InitBiTree getRchild() { 26 return rchild; 27 } 28 29 public void setRchild(InitBiTree rchild) { 30 this.rchild = rchild; 31 } 32 }
2、定义方法类
1 class Tools{ 2 public static InitBiTree createBiTree() { //先序遍历创建二叉树 3 System.out.print("请按先序次序依次输入二叉树的值，#号表示建立空树："); 4 Scanner sc = new Scanner(System.in); 5 String input = null; 6 input = sc.next(); 7 if(input.equals("#")) { 8 return null; 9 }else { 10 InitBiTree initBiTree = new InitBiTree(); 11 initBiTree.setData(input); 12 initBiTree.setLchild(Tools.createBiTree()); 13 initBiTree.setRchild(Tools.createBiTree()); 14 return initBiTree; 15 } 16 } 17 18 public static void preOrderTraverse(InitBiTree initBiTree) { //先序遍历 19 if(initBiTree != null) { 20 System.out.print(initBiTree.getData()); 21 Tools.preOrderTraverse(initBiTree.getLchild()); 22 Tools.preOrderTraverse(initBiTree.getRchild()); 23 } 24 } 25 26 public static void inOrderTraverse(InitBiTree initBiTree) { //中序遍历 27 if(initBiTree != null) { 28 Tools.inOrderTraverse(initBiTree.getLchild()); 29 System.out.print(initBiTree.getData()); 30 Tools.inOrderTraverse(initBiTree.getRchild()); 31 } 32 } 33 34 public static void postOrderTraverse(InitBiTree initBiTree) { //后序遍历 35 if(initBiTree != null) { 36 Tools.postOrderTraverse(initBiTree.getLchild()); 37 Tools.postOrderTraverse(initBiTree.getRchild()); 38 System.out.print(initBiTree.getData()); 39 } 40 } 41 42 public static void levelOrderTraverse(InitBiTree initBiTree) { //层序遍历 43 if(initBiTree != null) { 44 LinkedList<InitBiTree> linkedList = new LinkedList<InitBiTree>(); 45 linkedList.offer(initBiTree); 46 while(!linkedList.isEmpty()) { 47 initBiTree = linkedList.poll(); 48 if(initBiTree.getLchild() != null) { 49 linkedList.offer(initBiTree.getLchild()); 50 } 51 if(initBiTree.getRchild() != null) { 52 linkedList.offer(initBiTree.getRchild()); 53 } 54 System.out.print(initBiTree.getData()); 55 } 56 } 57 } 58 59 public static int biTreeDepth(InitBiTree initBiTree) { //求二叉树深度 60 if(initBiTree != null) { 61 int l = Tools.biTreeDepth(initBiTree.getLchild()); 62 int r = Tools.biTreeDepth(initBiTree.getRchild()); 63 if(l > r) { 64 return l + 1; 65 }else { 66 return r + 1; 67 } 68 }else { 69 return 0; 70 } 71 } 72 73 public static int biTreeNodeCount(InitBiTree initBiTree) { //求叶节点个数 74 if(initBiTree != null) { 75 int l = Tools.biTreeNodeCount(initBiTree.getLchild()); 76 int r = Tools.biTreeNodeCount(initBiTree.getRchild()); 77 if(l == 0 && r == 0) { 78 return 1; 79 }else { 80 return l + r; 81 } 82 }else { 83 return 0; 84 } 85 } 86 }
3、主函数调用
1 package word7; 2 3 import java.util.LinkedList; 4 import java.util.Scanner; 5 6 public class Main { 7 8 public static void main(String[] args) { 9 InitBiTree initBiTree = Tools.createBiTree(); 10 System.out.println("——————先序遍历——————"); 11 Tools.preOrderTraverse(initBiTree); 12 System.out.println(); 13 System.out.println("——————中序遍历——————"); 14 Tools.inOrderTraverse(initBiTree); 15 System.out.println(); 16 System.out.println("——————后序遍历——————"); 17 Tools.postOrderTraverse(initBiTree); 18 System.out.println(); 19 System.out.println("——————层序遍历——————"); 20 Tools.levelOrderTraverse(initBiTree); 21 System.out.println(); 22 System.out.println("——————二叉树深度——————"); 23 System.out.println(Tools.biTreeDepth(initBiTree)); 24 System.out.println("——————叶子结点个数——————"); 25 System.out.println(Tools.biTreeNodeCount(initBiTree)); 26 } 27 28 }
三、运行截图
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
