文档章节

BinaryTree

Sheamus
 Sheamus
发布于 2015/02/13 17:52
字数 670
阅读 81
收藏 2
点赞 0
评论 0
import java.io.IOException;
import java.util.Stack;
 
public class BinaryTree {
 
    private char root;
    private BinaryTree left;
    private BinaryTree right;
    private int height;
 
    /*
     * Internal a binaryTree by one element
     * 
     * @param element the required
     */
    BinaryTree(char element) {
        this(element, null, null);
    }
 
    /*
     * Internal a binaryTree by three element
     * 
     * @param element the root element
     * 
     * @param lt the left subtree
     * 
     * @param rt the right subtree
     */
    BinaryTree(char element, BinaryTree lt, BinaryTree rt) {
        root = element;
        left = lt;
        right = rt;
    }
 
    /*
     * Internal the method to insert into a binaryTree
     * 
     * @param element the insert element
     * 
     * @param bt the tree needed to insert
     */
    private BinaryTree insert(char element, BinaryTree bt) {
        if (bt == null)
            return new BinaryTree(element);
 
        int compareResult = element - bt.root;
        if (compareResult > 0) {
            bt.right = insert(element, bt.right);
        }
        if (compareResult < 0) {
            bt.left = insert(element, bt.left);
        } else
            ;
        bt.height = Math.max(height(bt.left), height(bt.right)) + 1;
        return bt;
    }
 
    /*
     * Return the height of node t, or -1, if null.
     */
 
    private int height(BinaryTree t) {
        return t == null ? -1 : t.height;
    }
 
    private void PreTravel(BinaryTree k1)// travel a tree by pre-order
    {
        if (k1 == null)
            return;
        else {
            System.out.print(k1.root);
            PreTravel(k1.left);
            PreTravel(k1.right);
        }
    }
 
    private void MidTravel(BinaryTree k1)// travel a tree by mid-order
    {
        if (k1 == null)
            return;
        else {
            MidTravel(k1.left);
            System.out.print(k1.root);
            MidTravel(k1.right);
        }
    }
 
    private void SufTravel(BinaryTree k1)// travel a tree by suf-order
    {
        if (k1 == null)
            return;
        else {
            SufTravel(k1.left);
            SufTravel(k1.right);
            System.out.print(k1.root);
        }
    }
 
    /*
     * Internal method to travel a tree without recursion
     * 
     * @param k1 the tree to be traveled
     */
    private void PreSTravel(BinaryTree k1) {
        Stack<BinaryTree> s = new Stack<BinaryTree>();
        if (k1 == null)
            return;
        else {
            System.out.print(k1.root);
            s.push(k1.right);
            s.push(k1.left);
        }
        while (!s.empty()) {
            BinaryTree bt = s.pop();
            if (bt != null) {
                System.out.print(bt.root);
                s.push(bt.right);
                s.push(bt.left);
            }
        }
    }
 
    /*
     * Internal method to travel a tree by cursion in mid
     * 
     * @param k1 the tree to be traveled
     */
    private void MidSTravel(BinaryTree k1) {
        Stack<BinaryTree> s = new Stack<BinaryTree>();
        BinaryTree bt = k1;
        while (bt != null || !s.empty()) {
            while (bt != null) {//先把左子树都压入栈
                s.push(bt);
                bt = bt.left;
            }
            if (!s.empty()) {
                bt = s.pop();//弹出栈顶
                System.out.print(bt.root);
                bt = bt.right;
            }
        }
    }
 
    /*
     * Internal method to travel a tree without crusion in suf
     * 
     * @param k1 the tree to be traveled
     */
    private void SufSTravel(BinaryTree k1) {//后序遍历算法,先遍历当前节点的左孩子,右孩子,最后访问当前节点
        Stack<BinaryTree> s = new Stack<BinaryTree>();
        BinaryTree cur;
        BinaryTree pre = null;
        s.push(k1);
        while (!s.empty()) {
            cur = s.peek();
            if ((cur.left == null && cur.right == null) //当前节点为叶子节点或者孩子节点都已经被访问过了
                    || (pre != null && (pre == cur.left || pre == cur.right))) {
                System.out.print(cur.root); //访问当前节点
                s.pop();
                pre = cur; //用来判断访问和下一次访问是否相同
            } else {//如果不是,则将左孩子压入栈,去看左孩子是否有孩子或者是否遍历过
                if (cur.right != null)
                    s.push(cur.right);
                if (cur.left != null)
                    s.push(cur.left);
            }
        }
    }
 
    /*
     * Internal the method to describe a tree
     * 
     * @param bt the tree needed to be describe
     */
    private void display(BinaryTree bt) {
        if (bt != null) {
            System.out.print(bt.root);
            if (bt.left != null) {
                System.out.print("(");
                display(bt.left);
            }
            if (bt.right != null) {
                System.out.print(",");
                display(bt.right);
                System.out.print(")");
            }
        }
    }
 
    public static void main(String[] args) {
        String test = "749358";
        // TODO Auto-generated method stub
        char ch = 0;
        try {
            ch = (char) System.in.read();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        BinaryTree bt = new BinaryTree(ch);
        try {
            ch = (char) System.in.read();
            while (ch != '#') {
                bt.insert(ch, bt);
                ch = (char) System.in.read();
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
 
        System.out.println(bt.height);
        System.out.print("树的结构为: ");
        bt.display(bt);
        System.out.println();
        System.out.print("前序遍历<递归>: ");
        bt.PreTravel(bt);
        System.out.println();
        System.out.print("前序遍历<栈>: ");
        bt.PreSTravel(bt);
        System.out.println();
        System.out.print("中序遍历<递归>: ");
        bt.MidTravel(bt);
        System.out.println();
        System.out.print("中序遍历<栈>: ");
        bt.MidSTravel(bt);
        System.out.println();
        System.out.print("后序遍历<递归>: ");
        bt.SufTravel(bt);
        System.out.println();
        System.out.print("后序遍历<栈>: ");
        bt.SufSTravel(bt);
    }
 
}

© 著作权归作者所有

共有 人打赏支持
Sheamus

Sheamus

粉丝 42
博文 211
码字总数 29920
作品 0
海淀
程序员
为什么只能输出5个数

package com.BinaryTree; public class BinaryTreeDemo { private Node root; public void addNode(int data){ if(root==null) root = new Node(data); else{ root.add(data); } } public vo......

酷呐么踏踏 ⋅ 2016/03/01 ⋅ 2

二叉树的实现及其可视化

BinaryTree.java package com.binarytree.test; import java.util.*; public class BinaryTree>{ private TreeNode root; private int size=0; public BinaryTree() { } public BinaryTree(E......

sohu1990 ⋅ 2012/08/05 ⋅ 0

二叉树前序、后序和后序遍历(非递归实现)

二叉树前序、后序和后序遍历(非递归实现) (1)前序 我们知道,前序遍历的顺序是根左右,当根节点不为空时,该节点才可以被打印。目前书上常见对树的遍历都是采用递归的方法实现的,我们知...

逆天96 ⋅ 2017/04/18 ⋅ 0

二叉树基本操作(下)

二叉树基本操作  1. 求二叉树的高度  2. 求二叉树叶子结点的个数  3. 求二叉树结点的个数  4. 求二叉树第K层结点的个数  5. 判断一个节点是否在一棵二叉树中  6. 获取一个节点的双亲结...

qq_38646470 ⋅ 01/22 ⋅ 0

Dotfuscator类重命名方法解析

Dotfuscator是专业的.NET程序代码混淆工具,拥有重命名、字符串加密、流程模糊、自定义规则和水印等功能,倍受开发人员喜爱。其中类重命名的使用方法非常普遍,涉及到既要保护代码信息,又要...

kouxunli1 ⋅ 2013/09/16 ⋅ 0

【算法和数据结构】二叉树的定义和封装(C++实现)

首先给出个人对于二叉树的理解:一个有限的节点集合,集合可以为空,或者仅含有根节点,又或者由一个根节点r和称为左右子树的两个不想交的二叉树构成。在这里,对于二叉树的理解用了递归的方...

qq_28869927 ⋅ 2017/02/23 ⋅ 0

Java-比较器(Comparable、Comparator)

原文:http://blog.csdn.net/itmyhome1990/article/details/8952722 Comparable接口的作用 之前Arrays类中存在sort()方法,此方法可以直接对对象数组进行排序。 Comparable接口 可以直接使用...

u013063153 ⋅ 2017/11/05 ⋅ 0

二叉树的层次遍历(队列) and 二叉搜索树的后序遍历序列

(一)从上往下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。【层次遍历】 从上到下打印二叉树的规律:每一次打印一个节点的时候,如果该节点有子节点,则把该节点的子节点...

passionfly ⋅ 2014/11/16 ⋅ 0

Tommy Yang/BinaryTree

二叉树(Binary Tree)定义: 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 二...

Tommy Yang ⋅ 2017/03/31 ⋅ 0

Dojo扩展--DojoX

DojoX 是 Dojo 主功能的一个扩展区,可以说是新功能和新想法孵化器。在这里,可以找到很多最新奇的功能组件。 目前 DojoX 项目主要扩展了数据结构与算法、数据处理与通信、实用工具、图形 AP...

匿名 ⋅ 2009/12/02 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

10个免费的服务器监控工具

监控你的WEB服务器或者WEB主机运行是否正常与健康是非常重要的。你要确保用户始终可以打开你的网站并且网速不慢。服务器监控工具允许你收集和分析有关你的Web服务器的数据。 有许多非常好的服...

李朝强 ⋅ 31分钟前 ⋅ 0

压缩工具之zip-tar

zip 支持目录压缩。使用yum安装zip包,使用yum安装unzip包 zip 1.txt.zip 1.txt #将1.txt文件压缩,新生成的压缩文件为1.txt.zip,原文件保留 zip -r 123.zip 123/ #-r对目录操作。将123/目录...

ZHENG-JY ⋅ 32分钟前 ⋅ 0

Dubbo @Activate注解使用和实现解析

Activate注解标识一个扩展是否被激活和使用,可以放在定义的类上和方法上,dubbo用它在SPI扩张类定义上,标识这个扩展实现激活的条件和时机,先看下定义: /** * Activate * <p/> * ...

哲别0 ⋅ 38分钟前 ⋅ 0

6.5 zip压缩工具 tar打包 打包并压缩

1.tar tar命令格式 [-zjxcvfpP] filename tar -z:表示同时用gzip压缩。 -j:表示同时用bzip2压缩。 -J:表示同时用xz压缩。 -x:表示解包或者解压缩。 -t:表示查看tar包里的文件。 -c:表示建...

oschina130111 ⋅ 40分钟前 ⋅ 0

Linux系统工程狮养成记

如今的社会,随着时代的发展,出现了很多职业,像电子类,计算机类的专业,出现了各种各样的工程师,有算法工程师,java工程师,前端工程师,后台工程师,Linux工程师,运维工程师等等,不同...

六库科技 ⋅ 47分钟前 ⋅ 0

Linux 机器的渗透测试命令备忘表

如下是一份 Linux 机器的渗透测试备忘录,是在后期开发期间或者执行命令注入等操作时的一些典型命令,设计为测试人员进行本地枚举检查之用。 此外,你还可以从这儿(https://gbhackers.com/c...

寰宇01 ⋅ 48分钟前 ⋅ 0

windows 安装java开发环境,配置jdk

下载jdk安装文件 链接:https://pan.baidu.com/s/1UEKPjnAdMqNj612B39Pfsg 密码:ipqx 如果javac无法使用 1,检查环境变量名称中是否有空格。。。,去除后即可 2,将JAVA_HOME替换为原始路径...

阿豪boy ⋅ 50分钟前 ⋅ 0

简析log4j的实现方式

刚加入新公司,对日志的要求比较严格,对此特意花了几天时间看了一下log4j的源码,大概了解了一下log4j的实现方式,总结如下: log4j的实现分为两个步骤:log4j.xml的加载,logger的使用 这里...

zdatbit ⋅ 今天 ⋅ 0

win环境下jdk7与jdk8共存配置

1.jdk安装包 jdk安装包 安装步骤略 2.jdk等配置文件修改 在安装JDK1.8时(本机先安装jdk1.7再安装的jdk1.8),会将java.exe、javaw.exe、javaws.exe三个文件copy到了C:\Windows\System32,这...

泉天下 ⋅ 今天 ⋅ 0

windows profesional 2017 build problem

.net framework .... https://stackoverflow.com/questions/43330915/could-not-load-file-or-assembly-microsoft-build-frameworkvs-2017...

机油战士 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部