利用先序序列递归构造根节点，利用中序序列来逻辑上判断是构造左子树还是右子树
package com.cn.sotred; /** * 采用先序和中序序列构造二叉树 * * @author wanjn * */ public class MyTree { private Node root;// 根节点 public Node getRoot() { return root; } public void setRoot(Node root) { this.root = root; } /** * 先序序列和中序序列构造二叉树，递归的根据先序序列和中序序列构造根节点， 然后根据逻辑人为的判断是构造左子数还是右子数 * * @param pre * 先序序列 * @param i * 先序序列起点 * @param j * 先序序列终点 * @param mid * 中序序列 * @param s * 中序序列起点 * @param t * 中序序列终点 */ public MyTree(int[] pre, int i, int j, int[] mid, int s, int t) { root = createTree(pre, i, j, mid, s, t); } /** * 先根遍历 */ public void preOrder() { doPreOrder(root); } /** * 中根遍历 */ public void midOrder() { doMidOrder(root); } /** * 后根遍历 */ public void lastOrder() { doLastOrder(root); } /** * 得到某个节点的所有子孙节点（注意不是真子孙） * * @param i * 指定节点的节点值 */ public void descents(int i) { DoDescents(root, i, 0); } /** * 递归方法最后一层需要退出，既可以是正常执行完毕的退出也可以是return的退出 * * @param node */ private void doPreOrder(Node node) { // 先访问根节点 System.out.print(node.value + " "); // 再访问左子树 if (node.left != null) { doPreOrder(node.left); } // 再访问右子树 if (node.right != null) { doPreOrder(node.right); } } /** * 得到某个节点的所有子孙节点（注意不是真子孙） 逻辑为：从根节点开始找，没找到指定节点前，标志位为0，不输出； * 找到指定节点后标示位置为1，之后递归该节点左右子树，因为标志位被传递下去，依然为1.标志位为1均输出节点值； * 然后在遍历完左右子树后，手动将标志位置为0，接下去继续遍历，因为标志位0，即使遍历了也不会输出节点值 * * @param node * 根节点 * @param i * 指定的节点 * @param flag * 标志位 */ private void DoDescents(Node node, int i, int flag) { if (node == null) { return; } // 开始 if ((Integer) node.value == i) { flag = 1; } if (flag == 1) { System.out.print(node.value + " "); } DoDescents(node.left, i, flag); DoDescents(node.right, i, flag); // 结束 if ((Integer) node.value == i) { flag = 0; } } private void doLastOrder(Node node) { // 先遍历左子树 if (node.left != null) { doLastOrder(node.left); } // 再遍历右子树 if (node.right != null) { doLastOrder(node.right); } // 最后遍历根节点 System.out.print(node.value + " "); } private Node createTree(int[] pre, int i, int j, int[] mid, int s, int t) { if (i > j) { return null; } // k用来在中序序列（从头开始找）中找根的位置 int k = s; // 创建根节点,即先序序列的第一个元素 Node node = new Node(pre[i]); // 在中序序列中查找该根节点的位置，从而确定，新的先序和中序序列 while (k <= t && mid[k] != pre[i]) { k++; } // 在中序序列中没有找到根节点，说明序列本身有问题 if (k > t) { throw new RuntimeException("不存在序列组合指定的树！"); } // 创建左子树 // 其中 k-s 表示在中序序列中左子树中节点的个数假设是q，从而可以知道先序序列从根节点开始后面的q个节点都属于左子树； // 依次我们可以得到左先，左中 ; 右先，右中的数组对应下标组合 node.left = createTree(pre, i + 1, i + k - s, mid, s, k - 1); node.right = createTree(pre, i + k - s + 1, j, mid, k + 1, t); return node; } private void doMidOrder(Node node) { // 先遍历左子树 if (node.left != null) { doMidOrder(node.left); } // 再遍历根节点 System.out.print(node.value + " "); // 最后遍历右子树 if (node.right != null) { doMidOrder(node.right); } } private class Node { Node left;// 左儿子 Object value;// 节点值 Node right;// 右儿子 private Node(Object value) { this.value = value; } } }