前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >java自定义构造二叉树及其遍历

java自定义构造二叉树及其遍历

作者头像
张俊怡
发布2018-04-24 14:13:53
9740
发布2018-04-24 14:13:53
举报
文章被收录于专栏:深度学习计算机视觉

首先:二叉树的建立

首先,我们采用广义表建立二叉树(关于广义表的概念,请查看百科的介绍:http://baike.baidu.com/view/203611.htm

我们建立一个字符串类型的广义表作为输入:

String expression = "A(B(D(,G)),C(E,F))";与该广义表对应的二叉树为

1366533767_1515.jpg

写代码前,我们通过观察二叉树和广义表,先得出一些结论:

代码语言:javascript
复制
每当遇到字母,将要创建节点
每当遇到“(”,表面要创建左孩子节点
每当遇到“,”,表明要创建又孩子节点
每当遇到“)”,表明要返回上一层节点   
广义表中“(”的数量正好是二叉树的层数

节点类的构建###

代码语言:javascript
复制
public class Node {  
  
    private char data;  
    private Node lchild;  
    private Node rchild;  
  
    public Node(){  
          
    }  
    public char getData() {  
        return data;  
    }  
  
    public void setData(char data) {  
        this.data = data;  
    }  
  
    public Node getRchild() {  
        return rchild;  
    }  
  
    public void setRchild(Node rchild) {  
        this.rchild = rchild;  
    }  
  
    public Node getLchild() {  
        return lchild;  
    }  
  
    public void setLchild(Node lchild) {  
        this.lchild = lchild;  
    }  
  
    public Node(char ch, Node rchild, Node lchild) {  
        this.data = ch;  
        this.rchild = rchild;  
        this.lchild = lchild;  
    }  
  
    public String toString() {  
        return "" + getData();  
    }  
}  

创建二叉树###

代码语言:javascript
复制
public Node createTree(String exp) {  
        Node[] nodes = new Node[3];  
        Node b, p = null;  
        int top = -1, k = 0, j = 0;  
        char[] exps = exp.toCharArray();  
        char data = exps[j];  
        b = null;  
        while (j < exps.length - 1) {  
            switch (data) {  
            case '(':  
                top++;  
                nodes[top] = p;  
                k = 1;  
                break;  
            case ')':  
                top--;  
                break;  
            case ',':  
                k = 2;  
                break;  
            default:  
                p = new Node(data, null, null);  
                if (b == null) {  
                    b = p;  
                } else {  
                    switch (k) {  
                    case 1:  
                        nodes[top].setLchild(p);  
                        break;  
                    case 2:  
                        nodes[top].setRchild(p);  
                        break;  
                    }  
                }  
            }  
            j++;  
            data = exps[j];  
        }  
        return b;
}  

递归执行三种遍历###

代码语言:javascript
复制
    /** 
         * pre order recursive 
         *  
         * @param node 
         */  
        public void PreOrder(Node node) {  
            if (node == null) {  
                return;  
            } else {  
                System.out.print(node.getData() + " ");  
                PreOrder(node.getLchild());  
                PreOrder(node.getRchild());  
      
            }  
        }  
      
        /** 
         * in order recursive 
         *  
         * @param node 
         */  
        public void InOrder(Node node) {  
            if (node == null) {  
                return;  
            } else {  
                InOrder(node.getLchild());  
                System.out.print(node.getData() + " ");  
                InOrder(node.getRchild());  
            }  
        }  
      
        /** 
         * post order recursive 
         *  
         * @param node 
         */  
        public void PostOrder(Node node) {  
            if (node == null) {  
                return;  
            } else {  
                PostOrder(node.getLchild());  
                PostOrder(node.getRchild());  
                System.out.print(node.getData() + " ");  
            }  
        }  

非递归遍历###

代码语言:javascript
复制
前序遍历
    public void PreOrderNoRecursive(Node node) {  
            Node nodes[] = new Node[CAPACITY];  
            Node p = null;  
            int top = -1;  
            if (node != null) {  
                top++;  
                nodes[top] = node;  
                while (top > -1) {  
                    p = nodes[top];  
                    top--;  
                    System.out.print(p.getData() + " ");  
                    if (p.getRchild() != null) {  
                        top++;  
                        nodes[top] = p.getRchild();  
                    }  
                    if (p.getLchild() != null) {  
                        top++;  
                        nodes[top] = p.getLchild();  
                    }  
                }  
            }  
        }  

中序遍历
    public void InOrderNoRecursive(Node node) {  
            Node nodes[] = new Node[CAPACITY];  
            Node p = null;  
            int top = -1;  
            if (node != null)  
                p = node;  
            while (p != null || top > -1) {  
                while (p != null) {  
                    top++;  
                    nodes[top] = p;  
                    p = p.getLchild();  
                }  
                if (top > -1) {  
                    p = nodes[top];  
                    top--;  
                    System.out.print(p.getData() + " ");  
                    p = p.getRchild();  
                }  
            }  
        }  

后序遍历
    public void PostOrderNoRecursive(Node node) {  
            Node[] nodes = new Node[CAPACITY];  
            Node p = null;  
            int flag = 0, top = -1;  
            if (node != null) {  
                do {  
                    while (node != null) {  
                        top++;  
                        nodes[top] = node;  
                        node = node.getLchild();  
                    }  
                    p = null;  
                    flag = 1;  
                    while (top != -1 && flag != 0) {  
                        node = nodes[top];  
                        if (node.getRchild() == p) {  
                            System.out.print(node.getData() + " ");  
                            top--;  
                            p = node;  
                        } else {  
                            node = node.getRchild();  
                            flag = 0;  
                        }  
                    }  
                } while (top != -1);  
            }  
        }  
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017.02.26 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 节点类的构建###
  • 创建二叉树###
  • 递归执行三种遍历###
  • 非递归遍历###
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档