我正在完成一个关于从先序遍历和中序遍历（每个节点上有一个字符）构建二叉树的作业，我正在努力理解如何构建实际的树。
以下是我的思路：
- 将先序遍历中的第一个条目存储为根节点
- 在中序遍历中搜索该条目。
- 将根节点左侧的字符保存为字符数组。
- 将根节点右侧的字符保存为字符数组。
- 创建一个新树，以根节点为父节点，其两个子节点为左侧和右侧的字符数组。
- 递归进行，直到先序遍历长度为0为止。
我已经完成了步骤1-4，但我不太确定如何正确构建我的树，并想知道是否有人有任何指点。谢谢。
如何从先序遍历和中序遍历构建二叉树
9
- jfisk
5个回答
7
在构建新树之前进行递归。因此，您的列表将如下所示：
- 如果数组长度为1，则返回仅包含该单个项的叶节点。 （这是递归基础。）（O（1））
- 将前序数组中的第一个条目存储为根节点。（O（1））
- 在中序数组中搜索该条目。（O（n））
- 获取中序数组中根节点左侧的字符并将其保存为字符数组。从前序数组中取相同数量的字符（在根节点后）。（O（n），或仅在指针/索引周围抛出时为O（1））
- 获取根节点右侧的字符并将其保存为字符数组。从前序数组中取相同数量的字符（在第一部分之后 - 应该只是剩余部分）。（O（n），或仅在指针/索引周围抛出时为O（1））
- 从两个左字符数组递归制作树。
- 从两个右字符数组递归制作树。
- 使用根节点组合两个树。（O（1）。）
非递归部分总体上可以在O（n）内完成，并且将它们累加到每个递归级别也是O（n）每个。因此，总运行时间取决于递归级别的数量。如果您拥有近似平衡的树，则深度为O（log n），因此我们总共得到O（n·log n）。由于唯一必须缓慢的部分是在中序数组中搜索根节点，因此我猜我们甚至可以更多地优化树。
在最坏的情况下，我们对树中的每个节点进行一次递归，复杂度为O（n·n）。
示例：前序ABCDEF，中序FEDCBA，树：
+---+
| A |
++--+
|
+---+ |
| B +<--+
++--+
|
+---+ |
| C +<--+
++--+
|
+---+ |
| D +<--+
++--+
|
+---+ |
| E +<--+
++--+
|
+---+ |
| F +<--+
+---+
- Paŭlo Ebermann
5
0
这里提供了一种数学方法来以非常简单的方式实现以下内容：
所使用的语言：Java
`
/*
从给定的中序遍历和前序遍历构建二叉树的算法。
以下是使用的术语：
i：表示提供的中序数组
p：表示提供的前序数组
beg1：中序数组的起始索引
beg2：前序数组的起始索引
end1：中序数组的结束索引
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);
如果您需要更详细的代码解释，请在评论中提出。我很乐意帮助：）
- Ashish Jain
0
你可以使用我为同样的问题编写的以下代码。它对我有效。
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;
}
}
- ASingh
0
- Andre Artus
3
@AhmedAshour：我不同意...这不是一个仅有链接的答案。Andre已经给出了他的解决方案的[简短]描述，然后提供了一个代码示例的链接。仅仅因为一个答案很短，并且有一个链接，并不自动使它成为一个仅有链接的答案。请参见：http://meta.stackoverflow.com/questions/287563/youre-doing-it-wrong-a-plea-for-sanity-in-the-low-quality-posts-queue - gariepy
@AhmedAshour，链接指向SO上的一个页面。大多数“仅链接”的问题在于潜在的死链。如果该链接失效，则此页面也可能失效。 - Andre Artus
0
我使用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;
}
}
- Dungeon Hunter
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
O(n· log n)。最坏情况可能会是O(n²)（就像一个链表，即根节点总是在搜索中的最后一个）。 - Paŭlo Ebermann