给出二叉树的中序和先序遍历，构建出二叉树

浅浅的花香味﹌ 2022-04-05 07:42 132阅读 0赞

假设二叉树的中序遍历为：

> D B E A F C

先序遍历为：

> A B D E C F

那么，如何构建还原出这颗二叉树？

**算法思想：**

先序遍历中，第一个节点为二叉树根节点，本例中，根节点为**A**，在中序遍历集合中检索字符**A**，字符**A**左边的字符为二叉树左子树，右边的字符为二叉树右子树。于是，我们得到如下结构：  
![在这里插入图片描述][20181211162653984.png]

递归重复上述步骤，得到如下结果:

![在这里插入图片描述][20181211162735388.png]

算法实现**buildTree**：

*  从先序中检索元素，元素位置索引**preIndex**，检索**preIndex+1**位置的元素，用以下次递归中。
 *  根据已检索的元素构建一个新的节点**tNode**
 *  在中序遍历集合中检索当前元素的位置索引**index**，记作**inIndex**
 *  对于**inIndex**之前的元素集合，调用**buildTree**方法，结果作为**tNode**的左子树
 *  对于**inIndex**之后的元素集合，调用**buildTree**方法，结果作为**tNode**的右子树
 *  返回**tNode**节点

**代码实现：**

public class InorderPreOrderToTree {
        Node root;
        static int preIndex = 0;
    
        /* Recursive function to construct binary of size len from
        Inorder 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 preIndex
    		and 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 and
    		right 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 functions
        public static void main(String args[]) {
            InorderPreOrderToTree tree = new InorderPreOrderToTree();
            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 traversal
            System.out.println("Inorder traversal of constructed tree is : ");
            tree.printInorder(root);
        }
    }
    
    // Java program to construct a tree using inorder and preorder traversal
    
    /* A binary tree node has data, pointer to left child
    and a pointer to right child */
    class Node {
        char data;
        Node left, right;
    
        Node(char item) {
            data = item;
            left = right = null;
        }
    }
    
    // This code has been contributed by Mayank Jaiswal

**执行结果：**

Inorder traversal of constructed tree is : 
    D B E A F C

[https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/][https_www.geeksforgeeks.org_construct-tree-from-given-inorder-and-preorder-traversal]

[20181211162653984.png]: /images/20220405/cec8932370ff4ed490115aa02ac46191.png
[20181211162735388.png]: /images/20220405/a21949b51e034033b9bbcb470a47c5f7.png
[https_www.geeksforgeeks.org_construct-tree-from-given-inorder-and-preorder-traversal]: https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/