本文共 3358 字,大约阅读时间需要 11 分钟。
原文地址:
我们考虑下下面的遍历:
中序遍历:D B E A F C
先序遍历:A B D E C F在一个先序序列中,最左端的元素就是树根。所以我们知道A是已知序列的根。通过查询A的中序序列,我们可以得到A左边左子树的所有元素和右边右子树的所有元素。所以我们现在知道了以下结构。
A / \ / \ D B E F C
我们递归上述步骤,然后得到下面的树:
A / \ / \ B C / \ / / \ /D E F
算法: buildTree()
1)从先序序列中选一个元素。增加一个先序索引变量(下面代码中的preIndex)来选择下一次递归调用的下一个元素。
2)用已选择的元素的值创建一个新的树节点tNode。 3)找到已选择元素在中序遍历中的索引。设这个索引为inIndex。 4)在inIndex之前调用buildTree,建立树作为tNode的左子树。 5)在inIndex之后调用buildTree,建立树作为tNode的右子树。 6)返回tNode。// 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; }}class BinaryTree { 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[]) { 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 traversal System.out.println("Inorder traversal of constructed tree is : "); tree.printInorder(root); }}// This code has been contributed by Mayank Jaiswal
输出:
Inorder traversal of constructed tree is :D B E A F C
时间复杂度: O(n2) ,当树是一个的时候,发生最坏的情况。例如先序遍历与中序遍历最坏的情况是 {A, B, C, D}与{D, C, B, A}。
转载地址:http://ekhii.baihongyu.com/