【数据结构与算法】重建二叉树

╰+哭是因爲堅強的太久メ 2022-08-12 00:16 16阅读 0赞

只能根据前序中序或者中序后序重建二叉树，不可能根据前序和后序重建，因为需要中序去划分左右子树。

*  代码实现

/**
     * 源码名称：ConstructBT.java 
     * 日期：2014-09-05
     * 程序功能：重建二叉树（前序中序）
     * 版权：CopyRight@A2BGeek 
     * 作者：A2BGeek
     */
    public class ConstructBT {
    	class Node<T> {
    		T mValue;
    		Node<T> mLeft;
    		Node<T> mRight;
    
    		public Node(T value, Node<T> left, Node<T> right) {
    			mValue = value;
    			mLeft = left;
    			mRight = right;
    		}
    	}
    
    	public Node<Character> buildBT(String pre, String mid) {
    		Node<Character> root = null;
    		String lpre, rpre, lmid, rmid;
    		int pos = 0;
    		if (pre.length() == 0 || mid.length() == 0) {
    			return null;
    		} else {
    			root = new Node<Character>(pre.charAt(0), null, null);
    			while (mid.charAt(pos) != root.mValue) {
    				pos++;
    			}
    			// recursive left
    			lpre = pre.substring(1, pos + 1);
    			lmid = mid.substring(0, pos);
    			root.mLeft = buildBT(lpre, lmid);
    			// recursive right
    			rpre = pre.substring(pos + 1, pre.length());
    			rmid = mid.substring(pos + 1, mid.length());
    			root.mRight = buildBT(rpre, rmid);
    		}
    		return root;
    	}
    
    	public void postIterate(Node<Character> root) {
    		if (root == null) {
    			return;
    		} else {
    			postIterate(root.mLeft);
    			postIterate(root.mRight);
    			System.out.print(root.mValue + " ");
    		}
    	}
    
    	public static void main(String[] args) {
    		ConstructBT bt = new ConstructBT();
    		Node<Character> root = bt.buildBT("12473568", "47215386");
    		bt.postIterate(root);
    	}
    }