栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

(java)关于用括号表示法直接创建二叉树的算法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

(java)关于用括号表示法直接创建二叉树的算法

有的时候 我们会得到一个二叉树的括号表示法(以字母为例)

例如 A(B(DE(H))C(FG))

如何通过这个括号表示法构造出二叉树?

若是一个一个加入左 或者右边 效率不佳 我设计了一个算法 可以自动把 二叉树的字母表示变成一个二叉树(仍是以字母为例)

思路

1.创建出一Object对象

2.先把括号表示法 A(B(DE(H))C(FG))    第一个节点(这里为A)单独拿出来作为根节点 入栈

3.扫描给的String(    A(B(DE(H))C(FG))   )

4.如果是左括号  直接入栈

5.如果是一个字母 那么封装成一个节点 再入栈

6.如果是右括号 不入栈 弹出栈前面至多两个节点 弹出左括号 把一个或者两个节点分别赋给左括号前面的节点(默认只有一个节点时优先挂在右节点)

7.3到6循环 知道扫描到括号表示法尾部

8.返回根节点

详细代码如下

public static Node creatbt(String s){
        Stack stack = new Stack();  //用栈来存储数据
        Node root = null;
        int i = 1;                               //从s的下标为1处开始遍历(除去根节点)
        //根节点单独拿出来
        root = new Node(s.charAt(0));
        stack.add(root);
        while (i < s.length()){
            char c = s.charAt(i);
            if (c == '('){                        //左括号直接入栈
                stack.add(c);
            }if (c == ')'){                         //如果是一个右括号 那么就弹出一个或两个节点 成为栈中前一个节点的左节点或者右节点
                Node n1 = null;
                Node n2 = null;
                if (!String.valueOf(stack.peek()).equals("(") ){
                    n1 =(Node)stack.pop();
                    if (!String.valueOf(stack.peek()).equals("(")  ){
                        n2 = (Node)stack.pop();
                    }
                }
                stack.pop();
                Node n = (Node)stack.peek();
                n.left = n2;
                n.right = n1;
            }if (c >= 65 && c <= 90 ){               //如果是一个字母 则封装成节点 入栈
                Node node = new Node(c);
                stack.add(node);
            }
            i++;
        }
        return root;
    }

转载请注明:文章转载自 www.mshxw.com
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号