多叉树的输出

之前做课程设计时写过二叉树的输出，最近，写 SNL 语言的编译程序的语法分析器，需要输出语法树，而语法树是多叉树，与二叉树的输出有点不一样。

二叉树的文本模式输出

输出二叉树的思想：

非递归进行中根遍历，遍历过程中确定每个结点的坐标（即其距离左边的偏移）
层次遍历依次输出每一层

为什么此方法不适合多叉树： 其实只要得到了每个结点的坐标，那么层次遍历时的处理是一样的，但问题是结点坐标需要中根遍历，但是多叉树有先序遍历、后序遍历，一般都没有定义中序遍历啊。因为不确定每个结点有几个子孩子，因此中根遍历的顺序『左孩子-根-右孩子』便不确定。那多叉树可以怎么形式化地输出呢？横的不行，来竖的吧！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17



 Syntax Tree for source code: hello.snl(by Recursive Descent)
 Program_ProgramHead_program
       |           |_ProgramName_sd
       |_DeclarePart_TypeDecPart_Пе
       |           |_VarDecPart_Пе
       |           |_ProcDecpart_Пе
       |_ProgramBody_begin
       |           |_StmList_Stm_OutputStm_write
       |           |       |             |_(
       |           |       |             |_Exp_Term_Factor_1
       |           |       |             |   |    |_OtherFactor_Пе
       |           |       |             |   |_OtherTerm_Пе
       |           |       |             |_)
       |           |       |_StmMore_Пе
       |           |_end
       |_.

竖版的输出树使用的是先根遍历，因此我们可以用栈来实现（层次遍历用队列）。 通用的先根遍历过程：

根结点入栈；
- 当栈非空：
- - 弹出一个结点，访问之，同时其子结点入栈；

但是我们需要形象地输出一棵树，因此还需要加上修饰的连接符号，空格，竖线，下划线等。为了方便，我还设置了

一个标记 isLineHead 记录当前结点是否为每行的第一个结点；
一个列表用来记录每行还有子孩子没有输出的结点。

1
2
3
4
5



root_a_b
   | |_c
   |_d_e
     |_f

设置1.的作用是，非行首结点的处理很简单，输出连接号下划线再输出自身结点值就行了(如上图 a, b 等)，而行首结点需要输出更多内容（竖线）（如上图 c, d 等）。

设置2.的作用是，并不是处理每个行首结点时，都需要在每个行首处画竖线，如上图 f, 并不要在 root 之下画竖线，因为 root 的所有子孩子都已输出。

- 访问结点时，如果当前结点不是行首：
- - 输出 _值
- 否则，当前结点是行首结点：
- - 遍历列表（上面定义的），
  - 如果当前要输出结点是当前遍历结点的子孩子，则输出足够的空格和竖线及下划线和结点值如上图输出 d 时。
  - 如果当前要输出结点不是当前遍历列表结点的子孩子则只需输出足够多的空格和竖线。

如上图的 c 输出时，遍历的列表是 [root, a, b] 遍历到 root 时，只需输出 root 的宽度个空格和一个竖线。遍历到 a 时才是空格（a的宽度个）竖线下划线 c 的值。说得很明白了吧，下面是完整代码：首先是结点的定义：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


/**
 * Created by lin on 2016-05-28-028.
 * 语法树节点
 */
public class TreeNode {
    private TreeNode[] children;
    private String value;
    private int width;
    private boolean printed;

    public TreeNode(String value) {
        this(null, value);
    }

    private TreeNode(TreeNode[] children, String value) {
        this.children = children;
        setValue(value);
    }

    boolean hasChild() {
        if (children == null) return false;
        for (TreeNode n : children)
            if (n != null)
                return true;
        return false;
    }

    boolean hasChildNotPrinted() {
        if (children == null) return false;
        for (TreeNode n : children)
            if (n != null)
                if (!n.printed)
                    return true;
        return false;
    }

    TreeNode[] getChildren() {
        return children;
    }

    public void setChildren(TreeNode... nodes) {
        this.children = nodes;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
        width = value.length();
    }

    int getWidth() {
        return width;
    }

    void setPrinted(boolean printed) {
        this.printed = printed;
    }

    @Override
    public String toString() {
        return "[TreeNode value=" + value + "]";
    }
}

然后是语法树的输出：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92


    /**
     * 使用栈进行非递归的前序遍历，竖版输出
     */
    public static void print(TreeNode root, PrintStream out, String msg, int offset) {
        if (root == null) return;
        for (int i = 0; i <= offset; i++) out.print(" ");
        out.println(msg);
        for (int i = 0; i < offset; i++) out.print(" ");
        out.print(" " + root.getValue());
        boolean isLineHead = false;
        int index = 0;
        List<TreeNode> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        list.add(root);
        TreeNode node, temp;
        pushChild(stack, root);
        while (!stack.empty()) {
            node = stack.pop();
            if (!isLineHead) {
                out.print("_" + node.getValue());
                node.setPrinted(true);
                if (node.hasChild()) {
                    insert(list, node, ++index);
                    pushChild(stack, node);
                    isLineHead = false;
                } else {
                    isLineHead = true;
                    index = 0;
                    out.println();
                    for (int i = 0; i < offset; i++) out.print(" ");
                }
            } else {
                for (int i = 0; i < list.size(); i++) {
                    temp = list.get(i);
                    index = i;
                    if (isChildOf(node, temp)) {
                        for (int j = 0; j < temp.getWidth(); j++) out.print(" ");
                        out.print("|_" + node.getValue());
                        node.setPrinted(true);
                        if (node.hasChild()) {
                            insert(list, node, ++index);
                            pushChild(stack, node);
                            isLineHead = false;
                        } else {
                            out.println();
                            for (int j = 0; j < offset; j++) out.print(" ");
                            index = 0;
                            isLineHead = true;
                        }
                        break;//跳出for
                    } else {
                        if (temp.hasChildNotPrinted()) {
                            for (int j = 0; j < temp.getWidth(); j++) out.print(" ");
                            out.print("|");
                        } else {
                            for (int j = 0; j <= temp.getWidth(); j++) out.print(" ");
                        }
                    }
                }
            }
        }
    }

    public static void print(TreeNode root, PrintStream out) {
        print(root, out, "", 0);
    }

    private static void insert(List<TreeNode> list, TreeNode node, int index) {
        if (list.size() <= index)
            list.add(node);
        else
            list.set(index, node);
    }

    private static void pushChild(Stack<TreeNode> stack, TreeNode node) {
        if (node.hasChild() && stack != null) {
            TreeNode temp;
            for (int i = node.getChildren().length - 1; i >= 0; i--) {
                temp = node.getChildren()[i];
                if (temp != null)
                    stack.push(temp);
            }
        }
    }

    private static boolean isChildOf(TreeNode node, TreeNode parent) {
        if (parent == null) return false;
        if (parent.getChildren() != null)
            for (TreeNode n : parent.getChildren())
                if (n == node) return true;
        return false;
    }

你可以在 Github 上找到完整的 SNL 词法分析与语法分析程序，其中包含了语法树的输出代码。

#多叉树 #编译原理 #语法树

3 comments