[关闭]
@XQF 2018-03-07T15:00:43.000000Z 字数 6080 阅读 1460

如何已知先序和和中序，求后序？

数据结构与算法

1.已知中序和前序求后序

主要是依据中序求出offset，这个offset为了方便成了加上就能拿到索引那种

  1.  public void createTreeWithPreAndIn(int[] preOrder, int[] inOrder) {
  2.         root = createTreeWithPreAndIn(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
  3.     }
  5.     public TreeNode createTreeWithPreAndIn(int[] preOrder, int preLeft, int preRight, int[] inOrder, int inLeft, int inRight) {
  6.         if (preLeft > preRight || inLeft > inRight) {
  7.             return null;
  8.         }
  9.         int rootData = preOrder[preLeft];
  10.         TreeNode root = new TreeNode(rootData);
  11.         int rootIndexInInOrder = findRootIndex(inOrder, inLeft, inRight, rootData);
  12.         int offset = rootIndexInInOrder - 1 - inLeft;
  14.         TreeNode left = createTreeWithPreAndIn(preOrder, preLeft + 1, preLeft + 1 + offset, inOrder, inLeft, inLeft + offset);
  15.         TreeNode right = createTreeWithPreAndIn(preOrder, preLeft + 1 + offset + 1, preRight, inOrder, rootIndexInInOrder + 1, inRight);
  16.         root.left = left;
  17.         root.right = right;
  18.         return root;
  19.     }

2.已知中序和后序求前序

  1.  public void createTreeWithInAndPost(int[] inOrder, int[] postOrder) {
  2.         root = createTreeWithInAndPost(inOrder, 0, inOrder.length - 1, postOrder, 0, postOrder.length - 1);
  3.     }
  5.     public TreeNode createTreeWithInAndPost(int[] inOrder, int inLeft, int inRight, int[] postOrder, int postLeft, int postRight) {
  6.         if (inLeft > inRight || postLeft > postRight) {
  7.             return null;
  8.         }
  9.         int rootData = postOrder[postRight];
  10.         TreeNode root = new TreeNode(rootData);
  11.         int rootIndexInInOrder = findRootIndex(inOrder, inLeft, inRight, rootData);
  12.         int offset = rootIndexInInOrder - 1 - inLeft;
  14.         TreeNode left = createTreeWithInAndPost(inOrder, inLeft, inLeft + offset, postOrder, postLeft, postLeft + offset);
  15.         TreeNode right = createTreeWithInAndPost(inOrder, rootIndexInInOrder + 1, inRight, postOrder, postLeft + offset + 1, postRight - 1);
  16.         root.left = left;
  17.         root.right = right;
  18.         return root;
  19.     }

3.找中序根索引方法

貌似不能根据前序和后序求出中序，因为，。，没办法确定左右子树的界限。

  1.  public int findRootIndex(int[] inOrder, int leftIn, int rightIn, int target) {
  2.         int result = -1;
  3.         for (int i = leftIn; i <= rightIn; i++) {
  4.             if (inOrder[i] == target) {
  5.                 result = i;
  6.                 break;
  7.             }
  8.         }
  9.         return result;
  10.     }

4.二叉树的所有基本操作

  1. class TreeNode {
  2.     int data;
  3.     TreeNode left;
  4.     TreeNode right;
  6.     public TreeNode(int data) {
  7.         this.data = data;
  8.         this.left = null;
  9.         this.right = null;
  10.     }
  11. }
  13. class BinaryTree {
  14.     TreeNode root;
  16.     public BinaryTree() {
  17.         root = null;
  18.     }
  20.     public void insert(int data) {
  21.         TreeNode node = new TreeNode(data);
  22.         if (root == null) {
  23.             root = node;
  24.         } else {
  25.             TreeNode dummy = root;
  26.             while (true) {
  27.                 if (node.data < dummy.data) {
  28.                     if (dummy.left == null) {
  29.                         dummy.left = node;
  30.                         return;
  31.                     }
  32.                     dummy = dummy.left;
  33.                 } else {
  34.                     if (dummy.right == null) {
  35.                         dummy.right = node;
  36.                         return;
  37.                     }
  38.                     dummy = dummy.right;
  39.                 }
  40.             }
  41.         }
  42.     }
  44.     public TreeNode create(int[] datas) {
  45.         for (int i = 0; i < datas.length; i++) {
  46.             insert(datas[i]);
  47.         }
  48.         return root;
  49.     }
  51.     public void inOrder(TreeNode root) {
  52.         if (root != null) {
  53.             inOrder(root.left);
  54.             System.out.print(root.data + " ");
  55.             inOrder(root.right);
  56.         }
  57.     }
  59.     public void preOrder(TreeNode root) {
  60.         if (root != null) {
  61.             System.out.print(root.data + " ");
  62.             preOrder(root.left);
  63.             preOrder(root.right);
  64.         }
  65.     }
  67.     public void postOrder(TreeNode root) {
  68.         if (root != null) {
  69.             postOrder(root.left);
  70.             postOrder(root.right);
  71.             System.out.print(root.data + " ");
  72.         }
  73.     }
  75.     public void bfs(TreeNode root) {
  76.         Queue<TreeNode> queue = new LinkedList<>();
  77.         queue.add(root);
  78.         while (!queue.isEmpty()) {
  79.             TreeNode current = queue.poll();
  80.             if (current.left != null) {
  81.                 queue.add(current.left);
  82.             }
  83.             if (current.right != null) {
  84.                 queue.add(current.right);
  85.             }
  86.             System.out.print(" " + current.data);
  87.         }
  88.     }
  90.     public void initTree(int[] preOrder, int[] inOrder) {
  91.         this.root = this.initTree(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
  92.     }
  94.     public TreeNode initTree(int[] preOrder, int leftPre, int rightPre, int[] inOrder, int leftIn, int rightIn) {
  95.         if (leftPre > rightPre || leftIn > rightIn) {
  96.             return null;
  97.         }
  98.         int rootData = preOrder[leftPre];
  99.         TreeNode root = new TreeNode(rootData);
  100.         int rootIndexInOrder = findRootIndex(inOrder, leftIn, rightIn, rootData);
  101.         int offset = rootIndexInOrder - 1 - leftIn;
  102.         TreeNode left = initTree(preOrder, leftPre + 1, leftPre + 1 + offset, inOrder, leftIn, leftIn + offset);
  103.         TreeNode right = initTree(preOrder, leftPre + offset + 2, rightPre, inOrder, rootIndexInOrder + 1, rightIn);
  104.         root.left = left;
  105.         root.right = right;
  106.         return root;
  107.     }
  109.     public void createTreeWithPreAndIn(int[] preOrder, int[] inOrder) {
  110.         root = createTreeWithPreAndIn(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
  111.     }
  113.     public TreeNode createTreeWithPreAndIn(int[] preOrder, int preLeft, int preRight, int[] inOrder, int inLeft, int inRight) {
  114.         if (preLeft > preRight || inLeft > inRight) {
  115.             return null;
  116.         }
  117.         int rootData = preOrder[preLeft];
  118.         TreeNode root = new TreeNode(rootData);
  119.         int rootIndexInInOrder = findRootIndex(inOrder, inLeft, inRight, rootData);
  120.         int offset = rootIndexInInOrder - 1 - inLeft;
  122.         TreeNode left = createTreeWithPreAndIn(preOrder, preLeft + 1, preLeft + 1 + offset, inOrder, inLeft, inLeft + offset);
  123.         TreeNode right = createTreeWithPreAndIn(preOrder, preLeft + 1 + offset + 1, preRight, inOrder, rootIndexInInOrder + 1, inRight);
  124.         root.left = left;
  125.         root.right = right;
  126.         return root;
  127.     }
  129.     public void createTreeWithPreAndPost(int[] preOrder, int[] postOrder) {
  131.     }
  133.     public void createTreeWithInAndPost(int[] inOrder, int[] postOrder) {
  134.         root = createTreeWithInAndPost(inOrder, 0, inOrder.length - 1, postOrder, 0, postOrder.length - 1);
  135.     }
  137.     public TreeNode createTreeWithInAndPost(int[] inOrder, int inLeft, int inRight, int[] postOrder, int postLeft, int postRight) {
  138.         if (inLeft > inRight || postLeft > postRight) {
  139.             return null;
  140.         }
  141.         int rootData = postOrder[postRight];
  142.         TreeNode root = new TreeNode(rootData);
  143.         int rootIndexInInOrder = findRootIndex(inOrder, inLeft, inRight, rootData);
  144.         int offset = rootIndexInInOrder - 1 - inLeft;
  146.         TreeNode left = createTreeWithInAndPost(inOrder, inLeft, inLeft + offset, postOrder, postLeft, postLeft + offset);
  147.         TreeNode right = createTreeWithInAndPost(inOrder, rootIndexInInOrder + 1, inRight, postOrder, postLeft + offset + 1, postRight - 1);
  148.         root.left = left;
  149.         root.right = right;
  150.         return root;
  151.     }
  153.     public int findRootIndex(int[] inOrder, int leftIn, int rightIn, int target) {
  154.         int result = -1;
  155.         for (int i = leftIn; i <= rightIn; i++) {
  156.             if (inOrder[i] == target) {
  157.                 result = i;
  158.                 break;
  159.             }
  160.         }
  161.         return result;
  162.     }
  163. }
  165. public class Solution {
  166.     public static void main(String[] args) {
  167.         BinaryTree tree = new BinaryTree();
  168.         int[] nums = {1, 3, 4, 5, 6, 4, 3, 2};
  169.         System.out.print("中序：");
  170.         TreeNode root = tree.create(nums);
  171.         tree.inOrder(root);
  172.         System.out.println();
  173.         System.out.print("先序：");
  174.         tree.preOrder(root);
  175.         System.out.println();
  176.         System.out.print("后序：");
  177.         tree.postOrder(root);
  178.         System.out.println();
  179.         System.out.print("层序：");
  180.         tree.bfs(root);
  181.         System.out.println();
  182.         BinaryTree tree1 = new BinaryTree();
  183.         int[] preOrder = {1, 2, 4, 8, 9, 5, 10, 3, 6, 7};
  184.         int[] inOrder = {8, 4, 9, 2, 10, 5, 1, 6, 3, 7};
  185. //       ? tree1.initTree(preOrder, inOrder);
  186.         tree1.createTreeWithPreAndIn(preOrder, inOrder);
  187.         System.out.print("后序：");
  188.         tree1.postOrder(tree1.root);
  190.     }
  191. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注