構建一個二叉樹考慮一個二叉樹具有以下屬性：如何從剛剛水平序遍歷字符串
樹上的級別順序遍歷將生成1和0的字符串（通過在訪問它們時在每個節點上打印奇怪值）。現在給這個字符串構造二叉樹並在樹上執行一個後序遍歷。帖子順序字符串應該是程序的輸出。
例如：輸入字符串是
111001000。從中創建一個二叉樹。然後在樹上，這將導致輸出進行後序遍歷：001001011
的「癥結」的問題是正好從平次序字符串創建二叉樹。我將如何做到這一點？
我覺得在概念上更簡單。
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<Node> list=new LinkedList();
list.add(root);
int i=0;
Queue<Node> nextList=new LinkedList<Node>();
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<Node>();
}
}
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"));
}
}
首先，我假設你的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<Integer> q = new ArrayDeque<Integer>();
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;
}
}
如果允許，我會用二元堆在這兒當幫手。在使用標準表實現的二進制堆中，給定元素索引，我們可以輕鬆計算其父索引：int parent = (index-1)/2;。知道這一點，我們需要從我們的表格開始處開始並執行以下操作：
在輸入流中的所有剩餘的元素：
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）。
這個算法在內存方面可能效率很低，但我希望它很容易理解。
以你的水平序遍歷的例子 - 111001000 樹將如下
A
/ \
B C
/\ /\
D E F G
/\
H I
的邏輯如下。
1）如果它的1（根） - 然後下一個2^1是該父項的子項的值，則取第一位。所以第二和第三位是A（根）的childern。
2）轉到下一位（B爲1），因爲它的值也是1，它也有2個孩子，然後是下一位（C代表1），它也有2個孩子。第二級結束，因爲我們有2 1的所以2^2接下來的比特是級別3.
3） 001000所以我們已經遍歷和接下來的4位是兒童在3級。第4位和第5位是0（D和E是葉節點，沒有孩子 - 這些將是B的孩子），然後F的位值爲1，所以1110010 （粗體數字）將是F.的第7位是0，所以G也是葉節點。
4）再次遍歷或嘗試recusion - 從第4，第5和第6和第7位只有一個位是1，因此未來2^1位將在一個新的水平和那些將F.
的孩子一旦樹形成，然後轉換爲PostFix很容易。
這是非常有用的，類似於我在找的東西。你可以看看這個問題http：// stackoverflow。com/q/37131759 – 33ted
的一種可能的解決方案（在不到一個小時）：
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<Node> nodeList = new ArrayList<Node>();
nodeList.add(root);
int pos = 0;
while (!nodeList.isEmpty()) {
List<Node> nextList = new ArrayList<Node>();
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));
}
}
這裏是一個非常簡單的解決方案。儘管如此，我並沒有真正使用
尊重內存，因爲我首先構建完整/完整樹
，然後標記我們的樹中實際存在哪些節點。所以這個
可以優化一點，我猜。
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<Integer, Node> mp = new HashMap<Integer, Node>();
String str = "110101000";
int sz = (int)Math.pow(2, str.length() + 1);
for (int i=0; i<sz; i++){
Node nd = new Node();
nd.id = i;
mp.put(nd.id, nd);
}
for (int i=0; i<sz; i++){
Node nd = mp.get(i);
if (2*i < sz) nd.left = mp.get(2*i + 1);
if (2*i + 1 < sz) nd.right = mp.get(2*i + 2);
}
Queue<Integer> visit = new LinkedList<Integer>();
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<sz; i++){
if (mp.get(i).exists){
System.out.println(i);
}
}
System.out.println();
System.out.println("EDGES:");
for (int i=0; i<sz; i++){
if (mp.get(i).exists){
if (mp.get(2 * i + 1).exists){
System.out.println(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<Integer> visit = new LinkedList<Integer>();
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<sz; i++){
if (exists[i]){
System.out.println(i);
}
}
System.out.println("");
System.out.println("EDGES:");
for (int i=0; i<sz; i++){
if (exists[i]){
if (exists[2*i+1]){
System.out.println(i + " --> " + (2*i+1));
}
if (exists[2*i+2]){
System.out.println(i + " --> " + (2*i+2));
}
}
}
}
}
只有1個孩子的非葉節點 - 它具有什麼值？ –
沒有隻有1個孩子的節點。它有兩個或沒有孩子。 – user3129550