如何从级别顺序遍历字符串构造二叉树
考虑具有以下属性的二叉树：
- 如果内部节点（非叶节点）有两个子节点，则其值为1。
- 叶节点的值为0，因为它没有子节点。
树上的级别顺序遍历将生成1和0的字符串（通过在访问每个节点时打印奇怪的值）。 现在给定此字符串构造二叉树并在树上执行post order遍历。 后订单字符串应该是程序的输出。
例如：输入字符串是
111001000。 从中创建二叉树。 然后在树上执行post order遍历，这将导致输出：001001011
问题的“症结”是仅从级别顺序字符串创建二叉树。 我该怎么办？
以您的级别顺序遍历为例 – 111001000树将如下所示
A / \ BC /\ /\ DEFG /\ HI
逻辑如下。
1）如果它的1（根） – 然后接下来的2 ^ 1是该父项的子项的值，则取第一位。 所以第2和第3位是A（根）的小孩。
2）转到下一位（B代表1），因为它的值也是1，它也有2个子节点，然后是下一位（C代表1），它也有2个子节点。 第二级结束，因为我们有2 1，所以2 ^ 2的下一位是3级。
3） 111 001000所以我们已遍历，接下来的4位是第3级的孩子。 第4和第5位为0（D和E是叶子节点并且没有子节点 – 这些将是B的子节点）然后F具有位值1，因此1110010 00 （粗体数字）将是F的子节点.7位是0所以G也将是叶节点。
4）再次循环或尝试重复 – 从第4，第5和第6和第7位只有一位是1所以接下来的2 ^ 1位将在下一级并且那些将是F的子级。
生成树后，转换为PostFix很容易。
一种可能的解决方案（在不到一小时内）：
import java.util.ArrayList; import java.util.List; public class Main { private static class Node { private Node left; private Node right; } private static Node buildTree(String input) { char chars[] = input.toCharArray(); if (chars.length == 0) { return null; } else { Node root = new Node(); List nodeList = new ArrayList (); nodeList.add(root); int pos = 0; while (!nodeList.isEmpty()) { List nextList = new ArrayList (); for (Node n: nodeList) { if (pos >= chars.length) { throw new RuntimeException("Invalid input string"); } char c = chars[pos++]; if (c == '1') { n.left = new Node(); n.right = new Node(); nextList.add(n.left); nextList.add(n.right); } else if (c != '0') { throw new RuntimeException("Invalid input string"); } } nodeList = nextList; } return root; } } private static String postTraverse(Node n) { if (n == null) { return ""; } else if (n.left == null && n.right == null) { return "0"; } else { return postTraverse(n.left) + postTraverse(n.right) + "1"; } } public static void main(String[] args) { Node tree = buildTree(args[0]); System.out.println(postTraverse(tree)); } }
如果允许，我会在这里使用二进制堆作为帮助器。 在使用标准表实现的二进制堆中，给定元素的索引，我们可以轻松地计算其父级索引： int parent = (index-1)/2; 。 知道了这一点，我们需要从表格的开头开始，然后进行以下操作：
- 将binaryHeap [0]设置为输入流中的第一个数字;
-
对于输入流中的所有剩余元素：
do{ binaryHeap[heapIndex] = -1; if (parent(heapIndex) = 1) binaryHeap[heapIndex] = nextElementFromTheInputStream; heapIndex++; } while(binaryHeap[heapIndex - 1] == 0);
所以基本上，我们通过我们的表。 我们将每个字段（根除0）初始化为-1，这意味着那里没有节点。 然后我们检查该字段的父级是否为1.如果是，则我们将输入流中的下一个元素放在堆中的当前索引（heapIndex）中。 如果当前字段的父级是0，我们就更进一步，因为这意味着我们的父级是一个叶子，不应该有任何子级。
然后我们可以在堆上运行后序算法（可能值得实现一些安全代码，因此输出流中不会放置带“-1”的元素。只需解释leftChild（heapIndex）== -1;或rightChild（heapIndex）== -1;为NULL）。
这种算法在内存方面可能效率很低，但我希望它很容易理解。
首先，我假设您的level order traversal基本上是BFS。
现在，让我们来看看字符串。 执行BFS，如果当前节点有两个儿子，我们打印“1”。 否则，它是一个叶子，我们打印0，终止当前分支的处理。
因此，在反向任务期间，我们可以记住开放分支的最后节点列表并将传入节点附加到那里。
让我们在一个例子中演示这种方法：
Level 1: Tree : 1 - id 0 Open branches : 0 0 (left and right son) Remaining string : 11001000 ********* Level 2: Tree : 1 1 1 Open branches : 1 1 2 2 Remaining string : 001000 ********* Level 3: Tree : 1 1 1 0 0 1 0 Open branches : 5 5 Remaining string : 00 Level 4: Tree : 1 1 1 0 0 1 0 0 0 No more input, we're done.
拥有树，后序遍历是微不足道的。
代码（它假定树非常密集，否则它的内存效率不高）：
import java.util.ArrayDeque; import java.util.Queue; public class Main { static final int MAX_CONST = 50; public static void main(String[] args) { String evilString = "111001000"; // Assuming this string is a correct input char[] treeRepr = new char[MAX_CONST]; Queue q = new ArrayDeque (); q.add(0); for (int i = 0; i < evilString.length(); ++i) { int index = q.remove(); char ch = evilString.charAt(i); if (ch == '1') { q.add(2*(index+1)-1); q.add(2*(index+1)); } treeRepr[index] = ch; // System.out.println(q.size()); } System.out.println(arrToString(treeRepr, 0, new StringBuilder())); } public static StringBuilder arrToString(char[] array, int index, StringBuilder sb) { if (array[index] == '1') { arrToString(array, 2*(index+1)-1, sb); arrToString(array, 2*(index+1), sb); } sb.append(array[index]); return sb; } }
这是一个非常简单的解决方案。 不是最佳的
尽管如此，因为我先建立一个完整/完整的树
然后我标记了树中实际存在的节点。 所以这
我想可以优化一下。
import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; class Node { public Node left; public Node right; public Integer id; public boolean exists; } public class Test32 { public static void main(String[] args) { HashMap mp = new HashMap(); String str = "110101000"; int sz = (int)Math.pow(2, str.length() + 1); for (int i=0; i visit = new LinkedList(); visit.add(0); // id = 0; int j = 0; int id = -1; while (!visit.isEmpty()){ id = visit.poll(); if (str.charAt(j) == '1'){ mp.get(id).exists = true; visit.add(2*id + 1); visit.add(2*id + 2); }else{ mp.get(id).exists = true; } j++; } System.out.println("NODES:"); for (int i=0; i " + (2*i+1)); } if (mp.get(2 * i + 2).exists){ System.out.println(i + " --> " + (2*i+2)); } } } } }
这里是同样的解决方案简化版。
没有树或地图，只是一个布尔数组。 如果是某个节点
k有孩子这些孩子是2 * k + 1和2 * k + 2。
在打印边缘的最后一个循环中，也可以
构造一个实际的二叉树。
import java.util.LinkedList; import java.util.Queue; public class Test32 { public static void main(String[] args) { String str = "110101000"; int sz = (int)Math.pow(2, str.length() + 1); boolean exists[] = new boolean[sz]; Queue visit = new LinkedList (); visit.add(0); // id = 0; if (str.charAt(0) == '1'){ exists[0] = true; } int j = 0; int id = -1; while (!visit.isEmpty()){ id = visit.poll(); if (str.charAt(j) == '1'){ exists[id] = true; visit.add(2*id + 1); visit.add(2*id + 2); }else{ exists[id] = true; } j++; } // System.out.println(""); System.out.println("NODES:"); for (int i=0; i " + (2*i+1)); } if (exists[2*i+2]){ System.out.println(i + " --> " + (2*i+2)); } } } } }
从概念上讲，我认为更简单。
import java.util.LinkedList; import java.util.Queue; class WeirdBinaryTree { static class Node { private Node right; private Node left; private int weirdValue; public void setWeirdValue(int value) { weirdValue=value; } } private static Node makeTree(String str)throws Exception { char[] array=str.toCharArray(); Node root=new Node(); Queue list=new LinkedList(); list.add(root); int i=0; Queue nextList=new LinkedList (); while(!list.isEmpty()) { if(array[i++]=='1') { Node temp=list.poll(); temp.left=new Node(); temp.right=new Node(); temp.setWeirdValue(1); nextList.add(temp.left); nextList.add(temp.right); } else { list.poll(); } if(list.isEmpty()) { list=nextList; nextList=new LinkedList (); } } return root; } private static void postTraversal(Node localRoot) { if(localRoot!=null) { postTraversal(localRoot.left); postTraversal(localRoot.right); System.out.print(localRoot.weirdValue); } } public static void main(String[] args)throws Exception { postTraversal(makeTree("111001000")); } }