数据结构&算法篇（1）--二叉树的构建与遍历_括号表示法构造二叉树

作者：繁依Fanyi0 | 2024-03-14 10:21:00

踩

括号表示法构造二叉树

这一篇我们主要是通过二叉树的括号表示法来构建一颗二叉树

1、二叉树的构建（括号表示法）

在这里插入图片描述

1）、使用demo

 @Test
    public void stackBinaryTree()
    {
        StackBinaryTree stackBinaryTree = new StackBinaryTree("A(B(D(,G)),C(E,F))");
//        StackBinaryTree.Node<Character> node = stackBinaryTree.findNode('B');
//        System.out.println(node.getLeft() == null ? "null" : node.getLeft().getValue());
//        System.out.println(node.getRight() == null ? "" : node.getRight().getValue());
        System.out.println(stackBinaryTree.traversPrint());
        System.out.println("------pre--------");
        System.out.println(stackBinaryTree.preTraversStr());
        System.out.println("------in--------");
        System.out.println(stackBinaryTree.inTraversStr());
        System.out.println("------after--------");
        System.out.println(stackBinaryTree.afterTraversStr());
        System.out.println("------gradation--------");
        System.out.println(stackBinaryTree.gradationTraversStr());
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

A(B(D(,G)),C(E,F))
------pre--------
ABDGCEF
------in--------
DGBAECF
------after--------
GDBEFCA
------gradation--------
ABCDEFG
1
2
3
4
5
6
7
8
9

2）、树的节点

public class Node<E>
    {
        private E value;

        private Node left;

        private Node right;

        public Node(E value) {
            this.value = value;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        public E getValue() {
            return 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

3）、树的构建

  /**
     *
     * @param treeExpression    <code>A(B(D(,G)),C(E,F))</code>
     */
    public StackBinaryTree(String treeExpression)
    {
        this.buildTreeByExpression(treeExpression);
    }

    //通过括号表示法,构建当前节点树
    private void buildTreeByExpression(String treeExpression)
    {
        //使用栈结构
        Stack<Node<Character>> nodeStack = new Stack<>();
        int length = treeExpression.length();
        Node<Character> nowNode = null;
        int flag = 1;
        for (int i = 0; i < length; i++) {
            Character nowChar = treeExpression.charAt(i);
            //  第2步、当遇到 '(' 表示 表示又需要遍历当前节点nowNode(C)的子节点(E,F)了，
            // 例如C(E,F)，所以需要清空前面的标记，并且将当前节点nowNode入栈
            if (nowChar == '(')
            {
                flag = 1;
                nodeStack.push(nowNode);
            }
            //  第4步、表示会存在下一颗右子树，将标记记为2表示
            else if (nowChar == ',')
            {
                flag = 2;
            }
            //  第5步、表示本次的树建立已经完成，可以将当前的节点(父节点出栈)，例如C(E,F)，在前面的过程为：
            //  首先是构建nowNode(C)
            //  遇到 '('    表示接下来会遇到nowNode(C)的子节点，所以先将nowNode(C)入栈，
            //  遇到E   构建Node，出栈获取Node(C),将其设置为left节点
            //  遇到','，设置flag=2
            //  遇到'F'，由于flag=2，所以出栈获取Node(C)，将其设置为right节点
            //  遇到')'，表示当前这颗小子树( Node(C)以及他的两个子节点 )构建完成，将`Node(C)`出栈
            else if (nowChar == ')')
            {
                nodeStack.pop();
            }
            else
            {
                //  第1、3步：当前节点的值处理创建当前处理的节点nowNode(C)
                nowNode = new Node(nowChar);
                if (Objects.isNull(parent))
                {
                    parent = nowNode;
                }
                else if (flag == 1)
                {
                    //为了形象说明出栈、入栈，这里使用pop，而不使用peek
//                    Node parentNode = nodeStack.peek();
                    Node parentNode = nodeStack.pop();
                    parentNode.left = nowNode;
                    nodeStack.push(parentNode);
                }
                else
                {
                    Node parentNode = nodeStack.pop();
                    parentNode.right = nowNode;
                    nodeStack.push(parentNode);
                }
            }
        }
    }
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

这里主要是使用了栈结构的先进后出。

4）、树的再次遍历打印

/**
 * 遍历
 * @return
 */
public String traversPrint()
{
    if (Objects.isNull(parent))
    {
        return null;
    }
    StringBuffer buffer = new StringBuffer();
    travers(parent,buffer);
    return buffer.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

public void travers(Node node,StringBuffer buffer)
{
    if (Objects.isNull(node))
    {
        return;
    }
    //先打印父节点
    if (Objects.nonNull(node))
    {
        buffer.append(node.value);
    }
    //都不为空，表示该节点有子节点
    if (Objects.nonNull(node.left) || Objects.nonNull(node.right))
    {
        //就通过   '('、','、')'构建表示子节点
        buffer.append("(");
        //递归left节点
        travers(node.left,buffer);
        if (Objects.nonNull(node.right))
        {
            buffer.append(",");
        }
        //递归right节点
        travers(node.right,buffer);
        buffer.append(")");
    }
}
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

返回结果：

A(B(D(,G)),C(E,F))
1

5）、树的查找

public Node findNode(Character e)
{
    return findNode(parent,e);
}

public Node findNode(Node node,Character e)
{
    if (node == null)
    {
        return null;
    }
    if (node.value.equals(e))
    {
        return node;
    }
    Node leftNode = findNode(node.left, e);
    if(leftNode == null)
    {
        return findNode(node.right,e);
    }
    return leftNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

6）、树的先序遍历

//先序遍历
public String preTraversStr()
{
    StringBuffer buffer = new StringBuffer();
    preTravers(parent,buffer);
    return buffer.toString();
}

public void preTravers(Node node,StringBuffer buffer)
{
    if (Objects.isNull(node))
    {
        return;
    }
    buffer.append(node.value);
    preTravers(node.left,buffer);
    preTravers(node.right,buffer);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这里主要是使用的递归：

------pre--------
ABDGCEF
1
2

7）、树的中序遍历

/**
 * 中序遍历，这种方式其实就是将整颗树摊平，如果是二叉排序树，其就是按顺序打印
 * @return
 */
public String inTraversStr()
{
    StringBuffer buffer = new StringBuffer();
    inTravers(parent,buffer);
    return buffer.toString();
}

public void inTravers(Node node,StringBuffer buffer)
{
    if (Objects.isNull(node))
    {
        return;
    }
    inTravers(node.left,buffer);
    buffer.append(node.value);
    inTravers(node.right,buffer);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

------in--------
DGBAECF
1
2

8）、树的后序遍历

/**
 * 后序遍历
 * @return
 */
public String afterTraversStr()
{
    StringBuffer buffer = new StringBuffer();
    afterTravers(parent,buffer);
    return buffer.toString();
}

public void afterTravers(Node node,StringBuffer buffer)
{
    if (Objects.isNull(node))
    {
        return;
    }
    afterTravers(node.left,buffer);
    afterTravers(node.right,buffer);
    buffer.append(node.value);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

------after--------
GDBEFCA
1
2

9）、树的层次遍历

public String gradationTraversStr()
{
    if (parent == null)
    {
        return "";
    }
    ArrayDeque<Node> deque = new ArrayDeque<>();
    StringBuffer buffer = new StringBuffer();
    deque.add(parent);
    /**
     * 这里利用队列先进先出
     * 1、首先是A出栈(打印)
     * 2、添加A的左右节点B、C
     * 3、再次while
     * 4、打印B ，再将B的子节点添加到队列\
     * 5、再次遍历
     * 6、打印C、添加C的子节点
     * 7、再次遍历
     * 8按上面2-7再次操作父节点以及子节点
     */
    while (!deque.isEmpty())
    {
        Node node = deque.pop();
        buffer.append(node.value);
        if (Objects.nonNull(node.left))
        {
            deque.add(node.left);
        }
        if (Objects.nonNull(node.right))
        {
            deque.add(node.right);
        }
    }
    return buffer.toString();
}
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

这里主要是利用队列先进先出的特性：

------gradation--------
ABCDEFG
1
2

10）、整体代码

public class StackBinaryTree {

    private Node<Character> parent;


    /**
     *
     * @param treeExpression    <code>A(B(D(,G)),C(E,F))</code>
     */
    public StackBinaryTree(String treeExpression)
    {
        this.buildTreeByExpression(treeExpression);
    }

    //通过括号表示法,构建当前节点树
    private void buildTreeByExpression(String treeExpression)
    {
        //使用栈结构
        Stack<Node<Character>> nodeStack = new Stack<>();
        int length = treeExpression.length();
        Node<Character> nowNode = null;
        int flag = 1;
        for (int i = 0; i < length; i++) {
            Character nowChar = treeExpression.charAt(i);
            //  第2步、当遇到 '(' 表示 表示又需要遍历当前节点nowNode(C)的子节点(E,F)了，
            // 例如C(E,F)，所以需要清空前面的标记，并且将当前节点nowNode入栈
            if (nowChar == '(')
            {
                flag = 1;
                nodeStack.push(nowNode);
            }
            //  第4步、表示会存在下一颗右子树，将标记记为2表示
            else if (nowChar == ',')
            {
                flag = 2;
            }
            //  第5步、表示本次的树建立已经完成，可以将当前的节点(父节点出栈)，例如C(E,F)，在前面的过程为：
            //  首先是构建nowNode(C)
            //  遇到 '('    表示接下来会遇到nowNode(C)的子节点，所以先将nowNode(C)入栈，
            //  遇到E   构建Node，出栈获取Node(C),将其设置为left节点
            //  遇到','，设置flag=2
            //  遇到'F'，由于flag=2，所以出栈获取Node(C)，将其设置为right节点
            //  遇到')'，表示当前这颗小子树( Node(C)以及他的两个子节点 )构建完成，将`Node(C)`出栈
            else if (nowChar == ')')
            {
                nodeStack.pop();
            }
            else
            {
                //  第1、3步：当前节点的值处理创建当前处理的节点nowNode(C)
                nowNode = new Node(nowChar);
                if (Objects.isNull(parent))
                {
                    parent = nowNode;
                }
                else if (flag == 1)
                {
                    //为了形象说明出栈、入栈，这里使用pop，而不使用peek
//                    Node parentNode = nodeStack.peek();
                    Node parentNode = nodeStack.pop();
                    parentNode.left = nowNode;
                    nodeStack.push(parentNode);
                }
                else
                {
                    Node parentNode = nodeStack.pop();
                    parentNode.right = nowNode;
                    nodeStack.push(parentNode);
                }
            }
        }
    }

    public Node findNode(Character e)
    {
        return findNode(parent,e);
    }

    public Node findNode(Node node,Character e)
    {
        if (node == null)
        {
            return null;
        }
        if (node.value.equals(e))
        {
            return node;
        }
        Node leftNode = findNode(node.left, e);
        if(leftNode == null)
        {
            return findNode(node.right,e);
        }
        return leftNode;
    }

    //先序遍历
    public String preTraversStr()
    {
        StringBuffer buffer = new StringBuffer();
        preTravers(parent,buffer);
        return buffer.toString();
    }

    public void preTravers(Node node,StringBuffer buffer)
    {
        if (Objects.isNull(node))
        {
            return;
        }
        buffer.append(node.value);
        preTravers(node.left,buffer);
        preTravers(node.right,buffer);
    }

    public String gradationTraversStr()
    {
        if (parent == null)
        {
            return "";
        }
        ArrayDeque<Node> deque = new ArrayDeque<>();
        StringBuffer buffer = new StringBuffer();
        deque.add(parent);
        /**
         * 这里利用队列先进先出
         * 1、首先是A出栈(打印)
         * 2、添加A的左右节点B、C
         * 3、再次while
         * 4、打印B ，再将B的子节点添加到队列\
         * 5、再次遍历
         * 6、打印C、添加C的子节点
         * 7、再次遍历
         * 8按上面2-7再次操作父节点以及子节点
         */
        while (!deque.isEmpty())
        {
            Node node = deque.pop();
            buffer.append(node.value);
            if (Objects.nonNull(node.left))
            {
                deque.add(node.left);
            }
            if (Objects.nonNull(node.right))
            {
                deque.add(node.right);
            }
        }
        return buffer.toString();
    }

    /**
     * 后序遍历
     * @return
     */
    public String afterTraversStr()
    {
        StringBuffer buffer = new StringBuffer();
        afterTravers(parent,buffer);
        return buffer.toString();
    }

    public void afterTravers(Node node,StringBuffer buffer)
    {
        if (Objects.isNull(node))
        {
            return;
        }
        afterTravers(node.left,buffer);
        afterTravers(node.right,buffer);
        buffer.append(node.value);
    }

    /**
     * 中序遍历，这种方式其实就是将整颗树摊平，如果是二叉排序树，其就是按顺序打印
     * @return
     */
    public String inTraversStr()
    {
        StringBuffer buffer = new StringBuffer();
        inTravers(parent,buffer);
        return buffer.toString();
    }

    public void inTravers(Node node,StringBuffer buffer)
    {
        if (Objects.isNull(node))
        {
            return;
        }
        inTravers(node.left,buffer);
        buffer.append(node.value);
        inTravers(node.right,buffer);
    }

    /**
     * 遍历
     * @return
     */
    public String traversPrint()
    {
        if (Objects.isNull(parent))
        {
            return null;
        }
        StringBuffer buffer = new StringBuffer();
        travers(parent,buffer);
        return buffer.toString();
    }

    public void travers(Node node,StringBuffer buffer)
    {
        if (Objects.isNull(node))
        {
            return;
        }
        //先打印父节点
        if (Objects.nonNull(node))
        {
            buffer.append(node.value);
        }
        //都不为空，表示该节点有子节点
        if (Objects.nonNull(node.left) || Objects.nonNull(node.right))
        {
            //就通过   '('、','、')'构建表示子节点
            buffer.append("(");
            //递归left节点
            travers(node.left,buffer);
            if (Objects.nonNull(node.right))
            {
                buffer.append(",");
            }
            //递归right节点
            travers(node.right,buffer);
            buffer.append(")");
        }
    }

    public class Node<E>
    {
        private E value;

        private Node left;

        private Node right;

        public Node(E value) {
            this.value = value;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        public E getValue() {
            return value;
        }
    }

    public Node getParent()
    {
        return parent;
    }

}
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/233318