括号表示法构造二叉树

创建树：

public void createBTree(String str) {
        Stack<BTNode> st = new Stack<>();
        BTNode p = null;
        char ch;
        boolean flag = true;//处理的是左子树
        int n = str.length();
        int i = 0;
        while (i < n) {
            ch = str.charAt(i);
            if (ch == '(') {
                st.push(p);
                flag = true;
            } else if (ch == ',') {
                flag = false;
            } else if (ch == ')') {
                st.pop();
            } else {//处理字符
                p = new BTNode(ch);
                if (root == null) {
                    root = p;
                } else {
                    if (!st.empty()) {
                        if (flag) {
                            st.peek().lchild = p;
                        } else {
                            st.peek().rchild = p;
                        }
                    }
                }

            }
            i++;
        }
    }
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

把构造出来的树，用括号表示

public String toString() {
        this.changeToString(root);
        return bstr;
    }

    private void changeToString(BTNode t) {
        if (t != null) {
            bstr += t.data;
            if (t.lchild != null || t.rchild != null) {
                //左子树和右子树
                bstr += '(';
                this.changeToString(t.lchild);
                bstr += ',';
                this.changeToString(t.rchild);
                bstr += ')';
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

实例：

import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        String str = "A(B(D(F,),E),C(,G))";
        BTree bt = new BTree();
        bt.createBTree(str);
        System.out.println("用括号表示法输出二叉树为：" + bt);
    }
}
class BTree {
    BTNode root;
    String bstr = "";

    public BTree() {
        root = null;
    }

    public void createBTree(String str) {
        Stack<BTNode> st = new Stack<>();
        BTNode p = null;
        char ch;
        boolean flag = true;//处理的是左子树
        int n = str.length();
        int i = 0;
        while (i < n) {
            ch = str.charAt(i);
            if (ch == '(') {
                st.push(p);
                flag = true;
            } else if (ch == ',') {
                flag = false;
            } else if (ch == ')') {
                st.pop();
            } else {//处理字符
                p = new BTNode(ch);
                if (root == null) {
                    root = p;
                } else {
                    if (!st.empty()) {
                        if (flag) {
                            st.peek().lchild = p;
                        } else {
                            st.peek().rchild = p;
                        }
                    }
                }
            }
            i++;
        }
    }

    public String toString() {
        this.changeToString(root);
        return bstr;
    }

    private void changeToString(BTNode t) {
        if (t != null) {
            bstr += t.data;
            if (t.lchild != null || t.rchild != null) {
                //左子树和右子树
                bstr += '(';
                this.changeToString(t.lchild);
                bstr += ',';
                this.changeToString(t.rchild);
                bstr += ')';
            }
        }
    }
}

class BTNode<E> {
    E data;
    BTNode lchild;
    BTNode rchild;

    public BTNode() {
    }

    public BTNode(E data) {
        this.data = data;
    }

    
}
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