【编程之美】java二进制实现重建

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

package com.cn.binarytree.utils;

/**

 * @author 刘利娟 liulijuan132@gmail.com

 * @version 创建时间:2014年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);

	}

}