package .binarytree.utils;/*** @author 刘利娟 liulijuan132@* @version 创建时间:7月20日 下午2:03:30 类说明：*/class Node {Node left;Node right;char chValue;Node(char chValue) {left = null;right = null;this.chValue = chValue;}}public class Rebuild {public static final int TREELEN = 6; // 树的节点数void rebuild(char[] preOrder, char[] inOrder, int treeLen, Node root) {if (preOrder == null || inOrder == null) { // 前序遍历序列或中序遍历序列为空return;}Node temp = new Node(preOrder[0]);// 获取前序遍历序列的第一个节点System.out.println("当前节点：" + preOrder[0]);if (root == null) { // 假设根节点为空，则把当前节点复制给根节点root = temp;}if (treeLen == 1) {return;}int i = 0;while (i < inOrder.length) { // 在inOrder中找到与preOrder[0]相等的节点if (preOrder[0] != inOrder[i]) {i++;} else {break;}}int leftLen = i;System.out.println("左子树长度:" + leftLen);int rightLen = inOrder.length - leftLen - 1;System.out.println("右子树长度:" + rightLen);if (leftLen > 0) {for (int j = 0; j < preOrder.length - 1; j++) {preOrder[j] = preOrder[j + 1];}char[] leftOrder = new char[leftLen];System.out.print("左子树:");for (int j = 0; j < leftLen; j++) {leftOrder[j] = inOrder[j];System.out.print(leftOrder[j] + "\t");}System.out.println();rebuild(preOrder, leftOrder, leftLen, root.left);}if (rightLen > 0) {for (int j = 0; j < preOrder.length - 1; j++) {preOrder[j] = preOrder[j + 1];}char[] rightOrder = new char[rightLen];System.out.print("右子树:");for (int j = 0; j < rightLen; j++) {rightOrder[j] = inOrder[j + leftLen + 1];System.out.print(rightOrder[j] + "\t");}System.out.println();rebuild(preOrder, rightOrder, rightLen, root.right);}}public static void main(String[] args) {char[] pre = { 'a', 'b', 'd', 'c', 'e', 'f' };char[] in = { 'd', 'b', 'a', 'e', 'c', 'f' };new Rebuild().rebuild(pre, in, TREELEN, null);}}
java实现重建二叉树：二叉树遍历序列和序列定序遍历，二进制重建。
版权声明：本文博客原创文章，博客，未经同意，。
