重建二叉树
问题描述
分析与解法
用java实现的代码如下：
1 package chapter3jiegouzhifa.RebuildBinTree; 2 3 /** 4 * 重建二叉树 5 * 递归解法 6 * @author DELL 7 * 8 */ 9 public class RebuildBinTree {10 //定义节点类11 public static class Node{12 int left; //左子树位置13 int right; //右子树位置14 char value; //节点值15 public Node(int left, int right, char value){16 this.left = left;17 this.right = right;18 this.value = value;19 }20 public void setLeft(int left) {21 this.left = left;22 }23 public void setRight(int right) {24 this.right = right;25 }26 }27 /**28 * 重建二叉树29 * @param preOrder 前序遍历结果30 * @param inOrder 中序遍历结果31 * @param tree 重建的树32 * @param root 当前重建树的根节点位置33 */34 public static void rebuild(String preOrder, String inOrder, Node[] tree, int root){35 36 int nTreeLen = preOrder.length();37 //检查边界条件38 if(preOrder.length()==0||inOrder.length()==0)39 return ;40 //获取当前遍历的第一个节点41 Node temp = new Node(-1,-1,preOrder.charAt(0));42 //如果节点为空，把当前节点复制到根节点43 if(tree[root]==null){44 tree[root] = temp;45 }46 //如果当前树的长度为1，那么已经是最后一个节点47 if(nTreeLen == 1){ 48 return ;49 }50 //寻找左子树的结尾51 int i=0;52 while(inOrder.charAt(i)!=temp.value&&i 0){59 tree[index].setLeft(++root);60 Node left = new Node(-1,-1,preOrder.charAt(1));61 tree[root]=left;62 // System.out.println(preOrder.substring(1,i+1)+" "+i);63 rebuild(preOrder.substring(1,i+1),inOrder.substring(0, i),tree,root);64 }65 //重建右子树66 if(nTreeLen-i-1>0){67 tree[index].setRight(root+i);68 Node right = new Node(-1,-1,preOrder.charAt(i+1));69 tree[root+i] = right;70 rebuild(preOrder.substring(i+1,nTreeLen),inOrder.substring(i+1, nTreeLen),tree,root+i);71 }72 }73 public static void main(String[] args) {74 String preOrder = "abdcef";75 String inOrder = "dbaecf";76 Node[] tree = new Node[preOrder.length()];77 rebuild(preOrder,inOrder,tree,0);78 System.out.println("重建的树为：");79 for(int i=0;i 程序运行结果如下：
重建的树为：a 左子树：b 右子树：cb 左子树：d 右子树：nulld 左子树：null 右子树：nullc 左子树：e 右子树：fe 左子树：null 右子树：nullf 左子树：null 右子树：null