二叉树的广度优先遍历

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    
    // 构造树的节点
    static class TreeNode {
        char data;
        TreeNode left;
        TreeNode right;
    }
    //初始化先序遍历数组
    static char pre[] = new char[50];
    //初始化中序遍历数组
    static char in[] = new char[50];
    //初始化后序遍历数组
    static char post[] = new char[50];

    // 本题中是根据中序和后序的遍历来构造
    static TreeNode creat(int postL, int postR, int inL, int inR) {
        // 后序遍历中找到根节点
        if (postL > postR) {
            return null;
        }
        TreeNode root = new TreeNode();
        root.data = post[postR];

        int k = 0;
        for (int j = inL; j <=inR; j++) {
            if (in[j] == post[postR]) {
                k = j;
                break;
            }
        }
        //中序遍历记录下标记录根节点root在中序遍历中的下标
        int cha = k - inL;
        // 遍历左子树
        root.left = creat(postL, postL + cha - 1, inL, k - 1);
        // 遍历右子树
        root.right = creat(postL + cha, postR - 1, k + 1, inR);

        return root;
    }

    // 层次遍历用BFS方法
    static void bfs(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode v = queue.remove();
            System.out.print(v.data);
            if (v.left != null) {
                queue.add(v.left);
            }
            if (v.right != null) {
                queue.add(v.right);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String s1 = input.split(" ")[0];
        String s2 = input.split(" ")[1];
        // 获取输入结点个数
        int number = s1.length();


        for (int i = 0; i < number; i++) {
            post[i] = s1.charAt(i);
            in[i] = s2.charAt(i);
        }

        // 建树
        TreeNode root = creat(0, number - 1, 0, number - 1);

        // 层次遍历输出结点data
        bfs(root);
    }
}
 

class TreeNode:
    def __init__(self,value):
        self.left = None
        self.right = None
        self.value = value
        
def TreeFunc(pStr,qStr):
    if len(pStr) == 0:
        return None
    t = TreeNode(pStr[-1])
    i = qStr.index(pStr[-1])
    
    qRight = qStr[i+1:]
    qLeft = qStr[:i]
    pLeft = pStr[:len(qLeft)]
    pRight = pStr[len(pLeft):-1]
    
    t.right = TreeFunc(pRight, qRight)
    t.left = TreeFunc(pLeft, qLeft)
    return t

if __name__ == '__main__':
    inputStr = input().strip()
    inputList = inputStr.split()
    pStr = inputList[0]
    qStr = inputList[1]
    t = TreeFunc(pStr, qStr)
    
    temStr = ''
    temList = []
    temList.append(t)
    while (len(temList)>0):
        t = temList[0]
        temList.pop(0)
        if (t is not None):
            temStr += t.value
            temList.append(t.left)
            temList.append(t.right)
    print(temStr)