本文共 8090 字，大约阅读时间需要 26 分钟。

JAVA实现二叉树的前序遍历、中序遍历、后序遍历和层次遍历算法

如图所示一颗二叉树，用JAVA实现二叉树的前序遍历、中序遍历、后序遍历和层次遍历算法

定义树节点

public class TreeNode {    int data;    TreeNode leftChild;    TreeNode rightChild;    TreeNode(){        this.leftChild=null;        this.rightChild=null;        this.data=-1;    }    TreeNode(int data){        this.leftChild=null;        this.rightChild=null;        this.data=data;    }    public TreeNode(int data, TreeNode leftChild, TreeNode rightChild) {        this.data = data;        this.leftChild = leftChild;        this.rightChild = rightChild;    }    //其它代码省略……}

二叉树的前序遍历、中序遍历、后序遍历和层次遍历算法设计

package com.bean.binarytreedemo;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;import java.util.Stack;public class BinaryTreeTraversalOperation {    //给定一个一维数组，表示二叉树节点的值    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };      private static List
   
     nodeList = null;      public void createBinTree() {          nodeList = new LinkedList
    
     ();          // 将一个数组的值依次转换为Node节点          for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {              nodeList.add(new TreeNode(array[nodeIndex]));          }          // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树          for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {              // 左孩子              nodeList.get(parentIndex).leftChild = nodeList                      .get(parentIndex * 2 + 1);              // 右孩子              nodeList.get(parentIndex).rightChild = nodeList                      .get(parentIndex * 2 + 2);          }          // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理          int lastParentIndex = array.length / 2 - 1;          // 左孩子          nodeList.get(lastParentIndex).leftChild = nodeList                  .get(lastParentIndex * 2 + 1);          // 右孩子,如果数组的长度为奇数才建立右孩子          if (array.length % 2 == 1) {              nodeList.get(lastParentIndex).rightChild = nodeList                      .get(lastParentIndex * 2 + 2);          }      }      /*     * 二叉树的前序遍历     * */    public static ArrayList
     
       preOrder(TreeNode root){        Stack
      
        stack = new Stack
       
        ();        ArrayList
        
          list = new ArrayList
         
          (); if(root == null){ return list; } stack.push(root); while(!stack.empty()){ TreeNode node = stack.pop(); list.add(node.data); if(node.rightChild!=null){ stack.push(node.rightChild); } if(node.leftChild != null){ stack.push(node.leftChild); } } System.out.println(list); return list; } /* * 二叉树的中序遍历 * */ public static ArrayList
          
            inOrder(TreeNode root){ ArrayList
           
             list = new ArrayList
            
             (); Stack
             
               stack = new Stack
              
               (); TreeNode current = root; while(current != null|| !stack.empty()){ while(current != null){ stack.add(current); current = current.leftChild; } current = stack.peek(); stack.pop(); list.add(current.data); current = current.rightChild; } System.out.println(list); return list; } /* * 二叉树的后续遍历 * */ public static ArrayList
               
                 postOrder(TreeNode root){ ArrayList
                
                  list = new ArrayList
                 
                  (); if(root == null){ return list; } list.addAll(postOrder(root.leftChild)); list.addAll(postOrder(root.rightChild)); list.add(root.data); System.out.println(list); return list; } /* * 求二叉树的最高深度 * */ public static int maxDepth(TreeNode node){ if(node==null){ return 0; } int left = maxDepth(node.leftChild); int right = maxDepth(node.rightChild); return Math.max(left,right) + 1; } /* * 求二叉树的最小深度 * */ public static int minDepth(TreeNode root){ if(root == null){ return 0; } return getMin(root); } public static int getMin(TreeNode root){ if(root == null){ return Integer.MAX_VALUE; } if(root.leftChild == null&&root.rightChild == null){ return 1; } return Math.min(getMin(root.leftChild),getMin(root.rightChild)) + 1; } /* * 求二叉树的节点数 * */ public static int numOfTreeNode(TreeNode root){ if(root == null){ return 0; } int left = numOfTreeNode(root.leftChild); int right = numOfTreeNode(root.rightChild); return left + right + 1; } /* * 求二叉树的叶子节点数 * */ public static int numsOfLeafNode(TreeNode root){ if(root == null){ return 0; } if(root.leftChild==null&&root.rightChild==null){ return 1; } return numsOfLeafNode(root.leftChild)+numsOfLeafNode(root.rightChild); } /* * 求二叉树第K层的节点数 * */ public static int numsOfkLevelTreeNode(TreeNode root,int k){ if(root == null||k<1){ return 0; } if(k==1){ return 1; } int numsLeft = numsOfkLevelTreeNode(root.leftChild,k-1); int numsRight = numsOfkLevelTreeNode(root.rightChild,k-1); return numsLeft + numsRight; } /* * 判断是否为平衡二叉树 * */ public static boolean isBalanced(TreeNode node){ return maxDeath2(node)!=-1; } public static int maxDeath2(TreeNode node){ if(node == null){ return 0; } int left = maxDeath2(node.leftChild); int right = maxDeath2(node.rightChild); if(left==-1||right==-1||Math.abs(left-right)>1){ return -1; } return Math.max(left, right) + 1; } /* * 判断二叉树是否为一颗完全二叉树 * */ public static boolean isCompleteTreeNode(TreeNode root){ if(root == null){ return false; } Queue
                  
                    queue = new LinkedList
                   
                    (); queue.add(root); boolean result = true; boolean hasNoChild = false; while(!queue.isEmpty()){ TreeNode current = queue.remove(); if(hasNoChild){ if(current.leftChild!=null||current.rightChild!=null){ result = false; break; } }else{ if(current.leftChild!=null&&current.rightChild!=null){ queue.add(current.leftChild); queue.add(current.rightChild); }else if(current.leftChild!=null&&current.rightChild==null){ queue.add(current.leftChild); hasNoChild = true; }else if(current.leftChild==null&&current.rightChild!=null){ result = false; break; }else{ hasNoChild = true; } } } return result; } /* * 二叉树的层次遍历 * */ public static ArrayList
                    
                     
                      > levelOrder(TreeNode root){ ArrayList
                      
                       
                        > result = new ArrayList
                        
                         
                          >(); if(root == null){ return result; } Queue
                          
                            queue = new LinkedList
                           
                            (); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); ArrayList
                            
                              level = new ArrayList
                             
                              (); for(int i = 0;i < size ;i++){ TreeNode node = queue.poll(); level.add(node.data); if(node.leftChild != null){ queue.offer(node.leftChild); } if(node.rightChild != null){ queue.offer(node.rightChild); } } result.add(level); } System.out.println(result); return result; } public static void main(String[] args) { // TODO Auto-generated method stub BinaryTreeTraversalOperation createBinaryTree=new BinaryTreeTraversalOperation(); createBinaryTree.createBinTree(); TreeNode root = nodeList.get(0); //前序遍历 System.out.println("先序遍历："); preOrder(root); System.out.println(); preOrder(root); System.out.println("------------------------------------"); System.out.println("中序遍历："); //中序遍历 inOrder(root); System.out.println(); inOrder(root); System.out.println("------------------------------------"); //后续遍历 System.out.println("后序遍历："); postOrder(root); postOrder(root); System.out.println("------------------------------------"); int maxHigh= maxDepth(root); System.out.println("二叉树的最大深度为："+maxHigh); System.out.println("------------------------------------"); int minHigh= minDepth(root); System.out.println("二叉树的最小深度为："+minHigh); System.out.println("------------------------------------"); int treeNodeNumbers= numOfTreeNode(root); System.out.println("二叉树的节点数为："+treeNodeNumbers); System.out.println("------------------------------------"); int leafNodeNumbers= numsOfLeafNode(root); System.out.println("二叉树的叶子节点数为："+leafNodeNumbers); System.out.println("------------------------------------"); int k=3; int kLevelNodeNumbers= numsOfkLevelTreeNode(root,k); System.out.println("二叉树第 "+ k +" 层的节点数为："+kLevelNodeNumbers); System.out.println("------------------------------------"); boolean isBalance= isBalanced(root); if(isBalance) { System.out.println("该二叉树[是]一颗平衡二叉树."); }else { System.out.println("该二叉树[不是]一颗平衡二叉树"); } System.out.println("------------------------------------"); boolean isCompleteBinaryTree=isCompleteTreeNode(root); if(isCompleteBinaryTree) { System.out.println("该二叉树[是]一颗完全二叉树."); }else { System.out.println("该二叉树[不是]一颗完全二叉树"); } System.out.println("------------------------------------"); System.out.println("二叉树的层次遍历为："); levelOrder(root); System.out.println("------------------------------------"); }}
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

（完）