使用二叉树中根序列和后根序列/先根序列和中跟获得二叉树java

序列和后根序列/先根序列和中跟获得二叉树java"/>

使用二叉树中根序列和后根序列/先根序列和中跟获得二叉树java

• 通过中跟序列和后根序列或是前根序列和中跟序列构造二叉树，这里使用的递归方法
• 递归需要关注：在什么情况下进行递归，正什么情况下结束递归
• 进行递归：这里使用两个If条件判断中根序列左边和右边是否有字母，如先跟序列为EHJ，中根序列为EJH，可以判断E为当前根，由于E左边没有字母，那么就没有左树，则只能进入右数递归的if条件判断语句。
• 结束递归：假设先根序列为HJ，中跟序列为JH，则根为H，H右边没有字母，则只能进入左树即进入递归方法(J,J)
  • J即位先根序列也是中跟序列，两个if条件判断都不满足时，由于无法进入if语句，返回该J节点使H.left=J节点

运行结果

1. 节点类

package Class.Binarytree;public class BinaryNode {private String data;BinaryNode left, right;public BinaryNode(String data) {this.data = data;}public BinaryNode(String data, BinaryNode left, BinaryNode right) {this.data = data;this.left = left;this.right = right;}public String toString() {return data;}}

2. 二叉树类

package Class.Binarytree;public class BinaryTree {BinaryNode root;public BinaryTree(String preStr, String inStr) {root = this.preBuild(preStr, inStr);}public BinaryTree() {}// 通过前序和中序遍历获得二叉树// ABDFIGCEH  BIFDGAEJHC// 1.获取先根序列首个字母 father 并将创建该节点// 2.从中跟序列中找到该字母索引inIndex// 3.并且通过substring(0,inIndex)获得左树对应中根序列inLeft,同样地获取右树中根序列inRight,// 4.获得当前根节点的左树前根序列preLeft和右树前根序列preRightpublic BinaryNode preBuild(String preStr, String inStr) {String fatherAlpha;BinaryNode father;BinaryNode leftSon;BinaryNode rightSon;int leftLength = 0;fatherAlpha = preStr.substring(0, 1);father = new BinaryNode(fatherAlpha);int inIndex = inStr.indexOf(fatherAlpha);// 1. 需要考虑到subString索引越界的问题// 2. 需要考虑到递归结束的条件if (inIndex != 0) { // 当中跟序列根节点左边有字母时String inLeft = inStr.substring(0, inIndex);leftLength = inLeft.length();String preLeft = preStr.substring(1, leftLength + 1);father.left = preBuild(preLeft, inLeft);}if (inIndex + 1 != inStr.length()) { // 当中跟序列根节点右边有字母时String inRight = inStr.substring(inIndex + 1);String preRight = preStr.substring(leftLength + 1);father.right = preBuild(preRight, inRight);}return father;}// 通过中序和后续遍历获得二叉树public BinaryNode postBuild(String inStr, String postStr) {String fatherAlpha;BinaryNode father;BinaryNode leftSon;BinaryNode rightSon;int leftLength = 0;fatherAlpha = postStr.substring(postStr.length() - 1);father = new BinaryNode(fatherAlpha);int inIndex = inStr.indexOf(fatherAlpha);if (inIndex != 0) { // 当中跟序列根节点左边有字母时String inLeft = inStr.substring(0, inIndex);leftLength = inLeft.length();String postLeft = postStr.substring(0, leftLength);father.left = postBuild(inLeft, postLeft);}if (inIndex + 1 != inStr.length()) { // 当中跟序列根节点右边有字母时String inRight = inStr.substring(inIndex + 1);String postRight = postStr.substring(leftLength, postStr.length() - 1);father.right = postBuild(inRight, postRight);}return father;}// 前序遍历public void preOrder() {preOrder(root);System.out.println("");}public void preOrder(BinaryNode node) {if (node != null) {System.out.print(node.toString());preOrder(node.left);preOrder(node.right);}}// 中序遍历public void inOrder() {inOrder(root);System.out.println("");}public void inOrder(BinaryNode node) {if (node != null) {inOrder(node.left);System.out.print(node.toString());inOrder(node.right);}}// 后续遍历public void postOrder() {postOrder(root);System.out.println("");}public void postOrder(BinaryNode node) {if (node != null) {postOrder(node.left);postOrder(node.right);System.out.print(node.toString());}}
}

3. 主类

package Class.Binarytree;public class main {public static void main(String[] args) {// 通过前根序列和中跟序列BinaryTree tree1 = new BinaryTree("DFIG", "IFDG");System.out.println("===tree1===");tree1.preOrder();tree1.inOrder();tree1.postOrder();BinaryTree tree2 = new BinaryTree("ABCDEF", "CBAEDF");System.out.println("===tree2===");tree2.preOrder();tree2.inOrder();tree2.postOrder();BinaryTree tree3 = new BinaryTree("ABCIDEHFJG","BICAHEJFGD");System.out.println("===tree3===");tree3.preOrder();tree3.inOrder();tree3.postOrder();// 通过中根序列和后跟序列BinaryTree tree4 = new BinaryTree();tree4.root = tree4.postBuild("ABCD","BDCA");System.out.println("===tree4===");tree4.preOrder();tree4.inOrder();tree4.postOrder();BinaryTree tree5 = new BinaryTree();tree5.root = tree5.postBuild("CDBEGAHFIJK","DCEGBFHKJIA");System.out.println("===tree5(作业)===");tree5.preOrder();tree5.inOrder();tree5.postOrder();BinaryTree tree6 = new BinaryTree();tree6.root = tree6.postBuild("ABCDEFG","BDCAFGE");System.out.println("===tree6===");tree6.preOrder();tree6.inOrder();tree6.postOrder();}
}