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

首先:二叉树的建立

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

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

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

1366533767_1515.jpg

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

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

节点类的构建###

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();  
    }  
}  

创建二叉树###

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

递归执行三种遍历###

    /** 
         * 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() + " ");  
            }  
        }  

非递归遍历###

前序遍历
    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);  
            }  
        }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java沉淀

定时器Timer(迭代一)测试篇

14850
来自专栏个人随笔

论 ArrayList如何实现线程安全

一:使用synchronized关键字 二:使用Collections.synchronizedList();         假如你创建的代码如下:List<...

359140
来自专栏数据结构与算法

P3388 【模板】割点(割顶)

题目背景 割点 题目描述 给出一个n个点,m条边的无向图,求图的割点。 输入输出格式 输入格式: 第一行输入n,m 下面m行每行输入x,y表示x到y有一条边 输...

38070
来自专栏计算机视觉与深度学习基础

Leetcode 91 Decode Ways

A message containing letters from A-Z is being encoded to numbers using the fol...

22270
来自专栏决胜机器学习

PHP数据结构(一)——顺序结构线性表

PHP数据结构(一)——顺序结构线性表 (原创内容,转载请注明来源,谢谢) 线性表的要求:存在唯一的“第一个”元素与“最后一个”元素,每个元素最多一个前驱和一个...

58090
来自专栏尾尾部落

[剑指offer] 从上往下打印二叉树

就是二叉树的层序遍历。借助一个队列就可以实现。 使用两个队列一个存放节点,一个存放值。先将根节点加入到队列中,然后遍历队列中的元素,遍历过程中,访问该元素的左...

12110
来自专栏吾爱乐享

java之学习calendar类的综合案例分析及代码

14460
来自专栏数据结构与算法

多项式系数学习笔记

对于多项式$(x_1 + x_2 + x_3 + \dots + x_k) ^n$的展开式中$x_1^{d_1}x_2^{d_2}x_3^{d_3} \dots...

8220
来自专栏Janti

springboot之使用redistemplate优雅地操作redis

3.1K30
来自专栏社区的朋友们

理解 B+ 树算法

最近有接触到 b+ 树,花了点时间,顺便总结梳理下方便后续翻阅;时间仓促,且文中多是个人的理解,仅供参考。

1.1K00

扫码关注云+社区

领取腾讯云代金券