java 如何从前序和中序遍历构建二叉树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5213069/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
how to build a binary tree from preorder and inorder traversals
提问by jfisk
Im doing an assignment on building a binary tree from the preorder and inorder traversals (a char in each Node) and im trying to wrap my brain around how to build the actual tree.
我正在做一项关于从前序和中序遍历（每个节点中的一个字符）构建二叉树的作业，并且我试图让我的大脑围绕如何构建实际的树。
Here is my thought process on how to accomplish this:
这是我关于如何实现这一点的思考过程：
- store the first entry in the preorder as the root node
- search the inorder for that entry.
- take the chars to the left of the root node and save them as a char array.
- take the chars to the right of the root node and save them as a char array.
- make a new tree, with the root as the parent and its 2 children being the left and right char arrays.
- keep going recursively until the preorder length is 0.
- 将前序中的第一个条目存储为根节点
- 搜索该条目的顺序。
- 将根节点左侧的字符保存为字符数组。
- 将根节点右侧的字符保存为字符数组。
- 制作一棵新树，以根为父级，其 2 个子级为左右字符数组。
- 继续递归直到前序长度为 0。
I have steps 1-4 taken care of, but im not too sure how to properly build my tree, and was wondering if anyone had any pointers. Thank you.
我处理了第 1-4 步，但我不太确定如何正确构建我的树，并且想知道是否有人有任何指示。谢谢你。
采纳答案by Pa?lo Ebermann
Do the recursion before building the new tree. So, your list would look like this:
在构建新树之前进行递归。因此，您的列表将如下所示：
- If the arrays have length 1, just return a leaf node with this single item in it. (This is the recursion foundation.) (O(1))
- Store the first entry in the preorder array as the root node. (O(1))
- Search the inorder array for that entry. (O(n))
- Take the chars to the left of the root node in the inorder array and save them as a char array. Take the same amount of characters from the preorder array (after the root). (O(n), or O(1) when just throwing pointers/indexes around.)
- Take the chars to the right of the root node and save them as a char array. Take the same amount of characters from the preorder array (after the first part – that should be just the remainding part). (O(n), or O(1) when just throwing pointers/indexes around.)
- Recursively make a tree from both left char arrays.
- Recursively make a tree from both right char arrays.
- Combine both trees with your root node. (O(1).)
- 如果数组的长度为 1，则只返回包含此单个项目的叶节点。（这是递归基础。）（O（1））
- 将 preorder 数组中的第一个条目存储为根节点。(O(1))
- 在中序数组中搜索该条目。（在））
- 取中序数组中根节点左侧的字符，并将它们保存为字符数组。从预序数组（根之后）中取出相同数量的字符。（O(n) 或 O(1) 当只是抛出指针/索引时。）
- 将根节点右侧的字符保存为字符数组。从 preorder 数组中取出相同数量的字符（在第一部分之后——应该只是剩下的部分）。（O(n) 或 O(1) 当只是抛出指针/索引时。）
- 从两个左字符数组递归地制作一棵树。
- 从两个正确的字符数组递归地制作一棵树。
- 将两棵树与根节点结合起来。（O（1）。）
The non-recursive parts can be done in O(n) overall, and summing them up for each recursion level is also O(n) each. The total runtime thus depends on the number of recursion levels. If you have a approximately balanced tree, the depth is O(log n), thus we get to O(n · log n) at all. As the only necessarily slow part is the search of the root node in the inorder array, I guess we could optimize that even a bit more if we know more about the tree.
非递归部分总体上可以在 O(n) 中完成，并且每个递归级别的总和也是 O(n)。因此，总运行时间取决于递归级别的数量。如果你有一个近似平衡的树，深度是 O(log n)，因此我们得到 O(n · log n)。由于唯一需要缓慢的部分是在中序数组中搜索根节点，我想如果我们对树有更多的了解，我们可以进一步优化它。
In the worst case we have one recursion level for each node in the tree, coming to complexity O(n·n).
在最坏的情况下，树中的每个节点都有一个递归级别，复杂度为 O(n·n)。
Example: Preorder ABCDEF, Inorder FEDCBA, Tree:
示例：预序 ABCDEF、中序 FEDCBA、树：
+---+
| A |
++--+
|
+---+ |
| B +<--+
++--+
|
+---+ |
| C +<--+
++--+
|
+---+ |
| D +<--+
++--+
|
+---+ |
| E +<--+
++--+
|
+---+ |
| F +<--+
+---+
回答by Andre Artus
回答by ASingh
You can use the below code, I just wrote for the same problem. It works for me.
你可以使用下面的代码，我只是为同样的问题写的。这个对我有用。
public class TreeFromInorderAndPreOrder {
public static List<Integer> inOrder = new ArrayList<Integer>();
public static List<Integer> preOrder = new ArrayList<Integer>();
public static void main(String[] args) {
Node root = new Node();
root.createRoot(5);
for(int i = 0 ; i < 9 ; i++){
if(i != 5){
root.insert(i);
}
}
inOrder(root);
preOrder(root);
for(Integer temp : inOrder){
System.out.print(temp + " ");
}
System.out.println();
for(Integer temp : preOrder){
System.out.print(temp + " ");
}
Node node1 = null;
node1 = reConstructTree(root, (ArrayList<Integer>) inOrder, true);
System.out.println();
inOrder(node1);
for(Integer temp : inOrder){
System.out.print(temp + " ");
}
System.out.println();
for(Integer temp : preOrder){
System.out.print(temp + " ");
}
}
public static void inOrder(Node node){
if(node!= null){
inOrder(node.leftchild);
inOrder.add(node.key);
inOrder(node.rightChild);
}
}
public static void preOrder(Node node){
if(node != null){
preOrder.add(node.key);
preOrder(node.leftchild);
preOrder(node.rightChild);
}
}
public static Node reConstructTree(Node root, ArrayList<Integer> inOrder,
boolean isLeft){
if(preOrder.size() != 0 && inOrder.size() != 0){
return null;
}
Node node = new Node();
node.createRoot(preOrder.get(0));
if(root != null && isLeft){
root.leftchild = node;
}else if(root != null && !isLeft){
root.rightChild = node;
}
int indx = inOrder.get(preOrder.get(0));
preOrder.remove(0);
List<Integer> leftInorder = getSublist(0, indx);
reConstructTree(node, (ArrayList<Integer>) leftInorder, true);
List<Integer> rightInorder = getSublist(indx+1, inOrder.size());
reConstructTree(node, (ArrayList<Integer>)rightInorder, false);
return node;
}
public static ArrayList<Integer> getSublist(int start, int end){
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = start ; i < end ; i++){
list.add(inOrder.get(i));
}
return list;
}
}
回答by Dungeon Hunter
I have written a sample program using divide and conquer approach using recursion in java
我在java中使用递归使用分而治之方法编写了一个示例程序
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeNode {
private char data;
public char getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public BinaryTreeNode getLeft() {
return left;
}
public void setLeft(BinaryTreeNode left) {
this.left = left;
}
public BinaryTreeNode getRight() {
return right;
}
public void setRight(BinaryTreeNode right) {
this.right = right;
}
private BinaryTreeNode left;
private BinaryTreeNode right;
public static void levelTravesal(BinaryTreeNode node)
{
Queue queue = new LinkedList();
if(node == null)
return;
queue.offer(node);
queue.offer(null);
int level =0;
while(!queue.isEmpty())
{
BinaryTreeNode temp = (BinaryTreeNode) queue.poll();
if(temp == null)
{
System.out.println("Level: "+level);
if(!queue.isEmpty())
queue.offer(null);
level++;
}else {
System.out.println(temp.data);
if(temp.getLeft()!=null)
queue.offer(temp.getLeft());
if(temp.getRight()!=null)
queue.offer(temp.getRight());
}
}
}
static int preIndex = 0;
public static void main(String[] args) {
if(args.length < 2)
{
System.out.println("Usage: preorder inorder");
return;
}
char[] preOrderSequence = args[0].toCharArray();
char[] inOrderSequence = args[1].toCharArray();
//char[] preOrderSequence = {'A','B','D','E','C','F'};
//char[] inOrderSequence = "DBEAFC".toCharArray();
if(preOrderSequence.length != inOrderSequence.length)
{
System.out.println("Pre-order and in-order sequences must be of same length");
return;
}
BinaryTreeNode root = buildBinaryTree(preOrderSequence, inOrderSequence, 0, preOrderSequence.length-1);
System.out.println();
levelTravesal(root);
}
static BinaryTreeNode buildBinaryTree(char[] preOrder, char[] inOrder, int start, int end)
{
if(start > end)
return null;
BinaryTreeNode rootNode = new BinaryTreeNode();
rootNode.setData(preOrder[preIndex]);
preIndex++;
//System.out.println(rootNode.getData());
if(start == end)
return rootNode;
int dataIndex = search(inOrder, start, end, rootNode.getData());
if(dataIndex == -1)
return null;
//System.out.println("Left Bounds: "+start+" "+(dataIndex-1));
rootNode.setLeft(buildBinaryTree(preOrder, inOrder, start, dataIndex - 1));
//System.out.println("Right Bounds: "+(dataIndex+1)+" "+end);
rootNode.setRight(buildBinaryTree(preOrder, inOrder, dataIndex+1, end));
return rootNode;
}
static int search(char[] inOrder,int start,int end,char data)
{
for(int i=start;i<=end;i++)
{
if(inOrder[i] == data)
return i;
}
return -1;
}
}
回答by Ashish Jain
Here is a mathematical approach to achieve the thing in a very simplistic way :
这是一种以非常简单的方式实现这一目标的数学方法：
Language used : Java
使用语言：Java
`
/*
Algorithm for constructing binary tree from given Inorder and Preorder traversals.
Following is the terminology used :
`
/* 从给定的中序和预序遍历构造二叉树的算法。以下是使用的术语：
i : represents the inorder array supplied
i : 表示提供的中序数组
p : represents the preorder array supplied
p : 表示提供的预排序数组
beg1 : starting index of inorder array
beg1 : 中序数组的起始索引
beg2 : starting index of preorder array
beg2 : 前序数组的起始索引
end1 : ending index of inorder array
end1 : 中序数组的结束索引
end2 : ending index of preorder array
end2 : 前序数组的结束索引
*/
*/
public static void constructTree(Node root, int[] i, int[] p, int beg1, int end1, int beg2, int end2)
public static void constructorTree(Node root, int[] i, int[] p, int beg1, int end1, int beg2, int end2)
{
{
if(beg1==end1 && beg2 == end2)
{
root.data = i[beg1];
}
else if(beg1<=end1 && beg2<=end2)
{
root.data = p[beg2];
int mid = search(i, (int) root.data);
root.left=new Node();
root.right=new Node();
constructTree(root.left, i, p, beg1, mid-1, beg2+1, beg2+mid-beg1);
System.out.println("Printing root left : " + root.left.data);
constructTree(root.right, i, p, mid+1, end1, beg2+1+mid-beg1, end2);
System.out.println("Printing root left : " + root.right.data);
}
}
}
`
`
You need invoke the function by following code :
您需要通过以下代码调用该函数：
int[] i ={4,8,7,9,2,5,1,6,19,3,18,10}; //Inorder
int[] p ={1,2,4,7,8,9,5,3,6,19,10,18}; //Preorder
Node root1=new Node();
constructTree(root1, i, p, 0, i.length-1, 0, p.length-1);
In case you need a more elaborate explanation of code please mention it in the comments. I would be happy to help :).
如果您需要更详细的代码解释，请在评论中提及。我很乐意提供帮助:)。
