学步园

package cn.feng;<br /> class Node {<br /> Node left = null;<br /> Node right = null;<br /> char value;<br /> }<br /> public class BinaryTreeBuilder {<br /> /**<br /> * 根据前序遍历和中序遍历重建二叉树子树<br /> * @param preOrder 前序遍历数组<br /> * @param start 子树起始位置<br /> * @param inOrder 中序遍历数组<br /> * @param end 中序遍历结束位置<br /> * @param length 子树节点树<br /> * @return 子树的根节点<br /> */<br /> public static Node buildTree(char[] preOrder, int start,<br /> char[] inOrder, int end, int length) {<br /> //参数验证<br /> if (preOrder == null || preOrder.length == 0 || inOrder == null<br /> || inOrder.length == 0 || length <= 0) {<br /> return null;<br /> }</p> <p> //建立子树根节点<br /> char value = preOrder[start];<br /> Node root = new Node();<br /> root.value = value;</p> <p> //递归终止条件：子树只有一个节点<br /> if (length == 1)<br /> return root;</p> <p> //分拆子树的左子树和右子树<br /> int i = 0;<br /> while (i < length) {<br /> if (value == inOrder[end - i]) {<br /> break;<br /> }<br /> i++;<br /> }</p> <p> //建立子树的左子树<br /> root.left = buildTree(preOrder, start + 1, inOrder, end - i - 1, length - 1 - i);<br /> //建立子树的右子树<br /> root.right = buildTree(preOrder, start + length - i, inOrder, end, i );</p> <p> return root;<br /> }<br /> public static void main(String[] args) {<br /> char[] preOrder = new char[] {'a', 'b', 'd', 'c', 'e', 'f'};<br /> char[] inOrder = new char[] {'d', 'b', 'a', 'e', 'c', 'f'};<br /> Node root = buildTree(preOrder, 0, inOrder, inOrder.length - 1, inOrder.length);<br /> }<br /> }<br />