二叉树的先序创建，先序，中序，后序的递归与非递归遍历，层次遍历，叶子结点数及树的深度计算

输入格式：如   abd###ce##f##*

 

package tree;//二叉树的二叉链表实现import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;import java.util.Stack;public class BTree
    
      {	BTNode rootNode=new BTNode();		  class BTNode
     
      {		char data;		BTNode
      
        leftChildNode;		BTNode
       
         rightChildNode;		public BTNode(){			data=0;			leftChildNode=rightChildNode=null;		}		public BTNode(char data){			this.data=data;			leftChildNode=rightChildNode=null;		}		public BTNode(char data,BTNode leftChildNode,BTNode rightChildNode){			this.data=data;			leftChildNode=leftChildNode;			rightChildNode=rightChildNode;		}	}	 //先序创建二叉树        char d[]=new char[100];		int i=0;		public BTNode creatBTree(){			BTNode node=null;		    if(d[i]!='*'){			    if(d[i]=='#'){				    node=null;				    i++;			    }			    else{				    node=new BTNode(d[i]);				    i++; 				    node.leftChildNode=creatBTree();   				    node.rightChildNode=creatBTree();						}			}			return node;		}	//先序递归遍历	public void preOrder(BTNode
        
          t){		if(t!=null){			System.out.print(t.data);			preOrder(t.leftChildNode);			preOrder(t.rightChildNode);		}	}	//先序非递归遍历	public void preStackOrder(BTNode t){		Stack s=new Stack();		BTNode p=t;		while(p!=null&&s.isEmpty()!=true){			if(p!=null){				System.out.print(p.data);				s.push(p);				p=p.leftChildNode;			}			if(s.isEmpty()){				s.pop();				p=p.rightChildNode;			}		}	}	//中序递归遍历	public void inOrder(BTNode t){		if(t!=null){			inOrder(t.leftChildNode);			System.out.print(t.data);			inOrder(t.rightChildNode);		}			}	//中序非递归遍历    public void inStackOrder(BTNode t){      	Stack
         
           s=new Stack
          
           (); BTNode p=t; while(p!=null&&s.isEmpty()){ if(p!=null){ s.push(p); p=p.leftChildNode; } if(s.isEmpty()!=true){ p=s.pop(); System.out.print(p.data); p=p.rightChildNode; } } } //后序递归遍历 public void postOrder(BTNode t){ if(t!=null){ postOrder(t.leftChildNode); postOrder(t.rightChildNode); System.out.print(t.data); } } //后序非递归遍历 public void postStackOrder(BTNode t){ Stack
           
             s=new Stack
            
             (); Stack
             
               ss=new Stack
              
               (); Integer i=new Integer(1); BTNode p=t; BTNode q=t; while(p!=null||s.isEmpty()!=true){ while(p!=null){ s.push(p); ss.push(new Integer(0)); p=p.leftChildNode; } while(s.isEmpty()!=true&&ss.peek().equals(i)){ ss.pop(); q=s.pop(); System.out.print(q.data); } if(s.isEmpty()!=true){ ss.pop(); ss.push(i); p=s.peek(); p=p.rightChildNode; } } } //层次非递归遍历 public void levelQueueOrder(BTNode t){ Queue
               
                 q=new LinkedList
                
                 (); q.add(t); while(q.isEmpty()!=true){ BTNode step=q.remove(); System.out.print(step.data); if(step.leftChildNode!=null){ q.add(step.leftChildNode); } if(step.rightChildNode!=null){ q.add(step.rightChildNode); } } } //计算二叉树深度 public int depth(BTNode t){ int leftDepth,rightDepth; if(t==null) return 0; leftDepth=depth(t.leftChildNode); rightDepth=depth(t.rightChildNode); return Math.max(leftDepth,rightDepth)+1; } //叶子结点个数 int num=0; public int leaf(BTNode t){ if(t!=null){ if(t.leftChildNode==null&&t.rightChildNode==null) num++; leaf(t.leftChildNode); leaf(t.rightChildNode); } return num; } public static void main(String[] args) { BTree bt=new BTree(); Scanner sc=new Scanner(System.in); String a=sc.next(); char c[]=a.toCharArray(); for(int i=0;i