二叉树的遍历（篇5）由中序和先序序列重建二叉树

本文主要是介绍二叉树的遍历（篇5）由中序和先序序列重建二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

让我们考虑下面的遍历：

中序序列：DBEAFC
前序序列：ABDECF

在Preorder序列中，最左侧的元素是树的根。所以我们知道’A’是给定序列的根。通过在Inorder序列中搜索’A’，我们可以发现’A’左侧的所有元素都在左子树中，右侧的元素在右子树中。所以我们现在知道下面的结构。

                 A/   \/       \D B E     F C

我们递归地按照上面的步骤，得到以下树。

         A/   \
     /       \
    B         C/ \        //     \    /
D       E  F

算法：buildTree（）

1）从Preorder中选择一个元素。preIndex++（下面的代码中的preIndex）在下一个递归调用中选择下一个元素。
2）用从Preorder中选的元素创建一个新的树节点tNode。
3）在Inorder中查找所选元素的索引。让索引为inIndex。
4）在inIndex之前调用元素的buildTree，并将构建的树作为tNode的左子树。
5）在inIndex之后调用元素的buildTree，并将构建的树作为tNode的右子树。
6）return tNode。

代码

// Java program to construct a tree using inorder and preorder traversal/* A binary tree node has data, pointer to left childand a pointer to right child */
class Node 
{char data;Node left, right;Node(char item) {data = item;left = right = null;}
}class BinaryTree 
{Node root;static int preIndex = 0;/* Recursive function to construct binary of size len fromInorder traversal in[] and Preorder traversal pre[].Initial values of inStrt and inEnd should be 0 and len -1.  The function doesn't do any error checking for cases where inorder and preorder do not form a tree */Node buildTree(char in[], char pre[], int inStrt, int inEnd) {if (inStrt > inEnd) return null;/* Pick current node from Preorder traversal using preIndexand increment preIndex */Node tNode = new Node(pre[preIndex++]);/* If this node has no children then return */if (inStrt == inEnd)return tNode;/* Else find the index of this node in Inorder traversal */int inIndex = search(in, inStrt, inEnd, tNode.data);/* Using index in Inorder traversal, construct left andright subtress */tNode.left = buildTree(in, pre, inStrt, inIndex - 1);tNode.right = buildTree(in, pre, inIndex + 1, inEnd);return tNode;}/* UTILITY FUNCTIONS *//* Function to find index of value in arr[start...end]The function assumes that value is present in in[] */int search(char arr[], int strt, int end, char value) {int i;for (i = strt; i <= end; i++) {if (arr[i] == value)return i;}return i;}/* This funtcion is here just to test buildTree() */void printInorder(Node node) {if (node == null)return;/* first recur on left child */printInorder(node.left);/* then print the data of node */System.out.print(node.data + " ");/* now recur on right child */printInorder(node.right);}// driver program to test above functionspublic static void main(String args[]) {BinaryTree tree = new BinaryTree();char in[] = new char[]{'D', 'B', 'E', 'A', 'F', 'C'};char pre[] = new char[]{'A', 'B', 'D', 'E', 'C', 'F'};int len = in.length;Node root = tree.buildTree(in, pre, 0, len - 1);// building the tree by printing inorder traversalSystem.out.println("Inorder traversal of constructed tree is : ");tree.printInorder(root);}
}