Java 二叉树的创建和前/中/后序遍历

旧城等待， 2022-11-21 11:19 46阅读 0赞

设计能存储char型数据的链式二叉树结构，并实现前/中/后序的递归遍历，前/中序非递归遍历。

import java.util.Scanner;
    class ReadTreeData{
        	//此类专门用于读取数据
    	String data; 
    	ReadTreeData(String x) {
         data = x;}
    	int pos;
    	char getChar() {
        
    		char x = data.charAt(pos); 
    		pos++;
    		return x;
    	}
    }
    class BinTree{
        
    	char data;
    	BinTree L,R;
    	BinTree(char x){
         data = x;}
    	BinTree(){
        ;}
    	
    	BinTree create(ReadTreeData r) {
         //r是建树数据的读取器，提供getChar()方法
    		char x = r.getChar();
    		if(x == '#') return null;
    		BinTree t = new BinTree(x);
    		t.L = create(r);
    		t.R = create(r);
    		return t;
    	}
    	void pre() {
         //前序递归
    		System.out.print(data); //此处省略this.data
    		if(L!=null) L.pre();
    		if(R!=null) R.pre();
    	}
    	void in() {
         //中序递归
    		if(L!=null) L.in();
    		System.out.print(data);
    		if(R!=null) R.in();
    	}
    	void post() {
         //后序递归
    		if(L!=null) L.post();
    		if(R!=null) R.post();
    		System.out.print(data);
    	}
    	class Stack{
         //栈：内部类，即内部类型，一般不外用
    		BinTree [] a = new BinTree[50];
    		int top;
    		boolean isEmpty() {
        return top==0;}
    		void push(BinTree x) {
        
    			a[top] = x;
    			top++;
    		}
    		BinTree pop() {
        
    			top--;
    			return a[top];
    		}
    	}
    	void preN() {
         //非递归前序遍历
    		Stack s = new Stack();
    		BinTree t = this;
    		while(t!=null || s.isEmpty()==false)
    			if(t!=null) {
        
    				System.out.print(t.data);
    				s.push(t);
    				t = t.L;
    			}
    			else {
        
    				t = s.pop();
    				t = t.R;
    			}
    	}
    	void inN() {
         //非递归中序遍历
    		Stack s = new Stack();
    		BinTree t = this;
    		while(t!=null || s.isEmpty()==false)
    			if(t!=null) {
        				
    				s.push(t);
    				t = t.L;
    			}
    			else {
        
    				t = s.pop();
    				System.out.print(t.data);
    				t = t.R;
    			}
    	}
    }
    class App{
        
    	public static void main(String [] args) {
        
    		System.out.println("请输入：");
    		Scanner sc = new Scanner(System.in);
    		String data = sc.nextLine();
    		ReadTreeData r = new ReadTreeData(data);
    		BinTree t = new BinTree();
    		t = t.create(r);
    		if(t == null) //注：这里需要判断，否则，若t为空，下面会报错空指针引用
    			System.out.print("为空表！");
    		else {
        
    			System.out.print("\n pre="); t.pre();
                System.out.print("\n preN="); t.preN();
                System.out.print("\n in="); t.in();
                System.out.print("\n inN="); t.inN();
                System.out.print("\n post="); t.post();
    		}
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTI3NTAz_size_16_color_FFFFFF_t_70_pic_center]  
//本例掌握：

1.  二叉树，关键在建树，建树关键在获取getChar()方法
2.  内部类–栈，因为该栈的数组元素类型只能是BinTree，或者说该类仅供BinTree使用，故干脆将其放在BinTree的内部（这样也可避免外部使用）；

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTI3NTAz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/4c358d02da784d1f83190fc5c9f47b19.png