文档章节

BinaryTree

Sheamus
 Sheamus
发布于 2015/02/13 17:52
字数 670
阅读 84
收藏 2
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

粉丝 45
博文 213
码字总数 29920
作品 0
海淀
程序员
私信 提问
BinaryTree-学习二叉树的Python库

Binarytree: Python Library for Studying Binary Trees Introduction Are you studying binary trees for your next exam, assignment or technical interview? Binarytree is a Python lib......

wangxuwei
07/07
0
0
二叉树的实现及其可视化

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
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
153
2
二叉树前序、后序和后序遍历(非递归实现)

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

逆天96
06/29
0
0
二叉树基本操作(下)

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

qq_38646470
01/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

什么是自然语言处理技术

自然语言处理(NLP)是计算机科学,人工智能,语言学关注计算机和人类(自然)语言之间的相互作用的领域。自然语言处理是计算机科学领域与人工智能领域中的一个重要方向。它研究能实现人与计...

本宫没空2
27分钟前
2
0
移动端关闭虚拟键盘

那么document.activeElement.blur()为什么可以阻止虚拟键盘弹出呢?原因是:当你点击input的时候,document.activeElement获得了DOM中被聚焦的元素,也就是你点击的input,而调用.blur()方法...

niuhongxia
28分钟前
5
0
Ubuntu18.04安装RabbitMQ(正确安装)

1、安装erlang 由于rabbitMq需要erlang语言的支持,在安装rabbitMq之前需要安装erlang sudo apt-get install erlang-nox 2、安装Rabbitmq 更新源 sudo apt-get update 安装 sudo apt-get ins...

hansonwong
37分钟前
2
0
如何在以太坊开发发行自己的ERC-20数字货币

今天我将向你展示如何在以太坊区块链上开发你自己的加密货币并将其出售!我将向你展示如何使用以太坊智能合约逐步创建自己的ERC-20代币和众筹销售,如何测试智能合约,如何将智能合约部署到以...

geek12345
37分钟前
4
0
Vlock用于有多个用户访问控制台的共享 Linux 系统

当你在共享的系统上工作时,你可能不希望其他用户偷窥你的控制台中看你在做什么。如果是这样,我知道有个简单的技巧来锁定自己的会话,同时仍然允许其他用户在其他虚拟控制台上使用该系统。 ...

linuxprobe16
38分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部