如何从preorder和inorder遍历构建二叉树
我正在做一个关于从预订和顺序遍历（每个节点中的一个字符串）构建二叉树的任务，并试图围绕如何构建实际树包裹我的大脑。
以下是关于如何完成此操作的思考过程：
- 将预订中的第一个条目存储为根节点
- 搜索该条目的inorder。
- 将字符放在根节点的左侧，并将它们保存为char数组。
- 将chars放在根节点的右侧，并将它们保存为char数组。
- 创建一个新树，以root为父，其中2个子为左右char数组。
- 继续递归，直到预订长度为0。
我已经完成了步骤1-4，但我不太确定如何正确构建我的树，并且想知道是否有人有任何指针。 谢谢。
在构建新树之前执行递归。 所以，你的列表看起来像这样：
- 如果数组的长度为1，则只返回包含此单个项目的叶节点。 （这是递归基础。） （O（1））
- 将第一个条目存储在预订单数组中作为根节点。 （O（1））
- 在inorder数组中搜索该条目。 （上））
- 将字符放在inorder数组中根节点的左侧，并将它们保存为char数组。 从预订单数组中获取相同数量的字符（在根之后）。 （O（n）或O（1）当只是抛出指针/索引时。）
- 将字符放在根节点的右侧，并将它们保存为char数组。 从预订单数组中获取相同数量的字符（在第一部分之后 – 应该只是剩余部分）。 （O（n）或O（1）当只是抛出指针/索引时。）
- 从两个char数组递归地生成一个树。
- 从两个正确的char数组递归地生成一个树。
- 将两个树与根节点组合在一起。 （O（1）。）
非递归部分可以在O（n）中完成，并且对于每个递归级别对它们求和也是每个O（n）。 因此总运行时间取决于递归级别的数量。 如果你有一个近似平衡的树，深度是O（log n），因此我们得到O（n·log n）。 由于唯一一个缓慢的部分是在inorder数组中搜索根节点，我想如果我们对树有更多的了解，我们可以进一步优化它。
在最坏的情况下，我们在树中的每个节点都有一个递归级别，达到复杂度O（n·n）。
示例：预购ABCDEF，Inorder FEDCBA，树：
+---+ | A | ++--+ | +---+ | | B +<--+ ++--+ | +---+ | | C +<--+ ++--+ | +---+ | | D +<--+ ++--+ | +---+ | | E +<--+ ++--+ | +---+ | | F +<--+ +---+ 看看我对这个问题的回答 。 您可以通过在预订序列中添加节点来构建树，但是使用inorder位置作为比较器。
你可以使用下面的代码，我刚刚写了同样的问题。 这个对我有用。
public class TreeFromInorderAndPreOrder { public static List inOrder = new ArrayList (); public static List preOrder = new ArrayList (); 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 ) 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 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 leftInorder = getSublist(0, indx); reConstructTree(node, (ArrayList ) leftInorder, true); List rightInorder = getSublist(indx+1, inOrder.size()); reConstructTree(node, (ArrayList )rightInorder, false); return node; } public static ArrayList getSublist(int start, int end){ ArrayList list = new ArrayList (); for(int i = start ; i < end ; i++){ list.add(inOrder.get(i)); } return list; } }
我已经使用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; } }
这是一种以非常简单的方式实现该事物的数学方法：
使用的语言：Java
`
/ *从给定的Inorder和Preorder遍历构造二叉树的算法。 以下是使用的术语：
i：表示提供的inorder数组
p：表示提供的预订单数组
beg1：inorder数组的起始索引
beg2：预编程数组的起始索引
end1：inorder数组的结束索引
end2：预编程数组的结束索引
* /
public static void constructTree（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); }
}
`
您需要通过以下代码调用该函数：
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);
如果您需要更详细的代码说明，请在评论中提及。 我很乐意帮助:)。