二叉树的前中后序遍历算法

r囧r小猫 2022-08-06 09:10 87阅读 0赞

/**

* java 实现的一个二叉树的前中后序遍历算法，使用递归。
     * @author chenyb
     *
     */
    public class BiTreeStudy {
      private static TreeNode tree = null;
    	public static void initTree(){
    		TreeNode node1 = new TreeNode(4,true,false);
    		TreeNode node2 = new TreeNode(6,true,false);
    		TreeNode node3 = new TreeNode(7,true,false);
    		TreeNode node4 = new TreeNode(3,true,false);
    		
    		TreeNode node5 = new TreeNode(2,false,false);
    		TreeNode node6 = new TreeNode(5,false,false);
    		tree = new TreeNode(1,false,true);
    		
    		node6.setLeftChild(node2);
    		node6.setRightChild(node3);
    		
    		node5.setLeftChild(node1);
    		node5.setRightChild(node6);
    		
    		tree.setLeftChild(node5);
    		tree.setRightChild(node4);
      }
    	//中序遍历
       public static void zxbl(TreeNode tree){
    	   if(tree==null){
    		   System.out.println(" no children,over!");
    	   } else if(tree.isLeaf()){
    		   System.out.println(tree.getIndex()+": is leaf,over!");
    	   }else{
    		   zxbl(tree.getLeftChild());
    		   System.out.print(tree.getIndex()+",");
    		   zxbl(tree.getRightChild());
    	   }
       }
     //后序遍历
       public static void hxbl(TreeNode tree){
    	   if(tree==null){
    		   System.out.println(" no children,over!");
    	   } else if(tree.isLeaf()){
    		   System.out.println(tree.getIndex()+": is leaf,over!");
    	   }else{
    		   hxbl(tree.getLeftChild());
    		   hxbl(tree.getRightChild());
    		   System.out.print(tree.getIndex()+",");
    	   }
       }
     //前序遍历
       public static void qxbl(TreeNode tree){
    	   if(tree==null){
    		   System.out.println(" no children,over!");
    	   } else if(tree.isLeaf()){
    		   System.out.println(tree.getIndex()+": is leaf,over!");
    	   }else{
    		   System.out.print(tree.getIndex()+",");
    		   qxbl(tree.getLeftChild());
    		   qxbl(tree.getRightChild());
    	   }
       }
       public static void leftTree(TreeNode tree){
    	  if(tree.isLeaf()){
    		 System.out.print(tree+",");
    	  }else{
    		  leftTree(tree.getLeftChild());
    		  System.out.print(tree.getLeftChild()+",");
    	  }
       }
       public static void rightTree(TreeNode tree){
    	   if(tree.isLeaf()){
    		 System.out.print(tree+",");
    	  }else{
    		  rightTree(tree.getRightChild());
    		  System.out.print(tree.getRightChild()+",");
    	  }
       }
    	public static void main(String[] args) {
    		BiTreeStudy.initTree();
    		BiTreeStudy.qxbl(tree);
    		System.out.println("--------qxbl---------------");
    		BiTreeStudy.zxbl(tree);
    		System.out.println("-----------zxbl------------");
    		BiTreeStudy.hxbl(tree);
    		System.out.println("----------hxbl-------------");
    	}
    }
    
    
    运行结果：
    1,2,4: is leaf,over!
    5,6: is leaf,over!
    7: is leaf,over!
    3: is leaf,over!
    --------qxbl---------------
    4: is leaf,over!
    2,6: is leaf,over!
    5,7: is leaf,over!
    1,3: is leaf,over!
    -----------zxbl------------
    4: is leaf,over!
    6: is leaf,over!
    7: is leaf,over!
    5,2,3: is leaf,over!
    1,----------hxbl-------------