文档章节

BinaryTree

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

粉丝 44
博文 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
二叉树前序、后序和后序遍历(非递归实现)

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

逆天96
06/29
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
二叉树的实现及其可视化

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
二叉树基本操作(下)

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

qq_38646470
01/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【挑战剑指offer】系列03:逆序打印单链表

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。 1. 【逆序打印单链表】原始题...

LinkedBear
5分钟前
0
0
Linux内存布局

今天这篇文章主要是我之前看Linux内核相关知识和博客Gustavo Duarte中。我主要是看了这篇博客,并且结合之前的知识,对内存管理的的理解又上升了一个档次。所以想通过这篇文章总结下。 我们先...

linuxprobe16
24分钟前
0
0
day94-20180921-英语流利阅读-待学习

记录死亡还是消费死者?自杀报道的媒体偏见 雪梨 2018-09-21 1.今日导读 自杀事件报道一直是新闻报道的重要部分,具有骇人听闻、吸引眼球的特点。可是在报道这些事件的时候,除了客观陈述事实...

飞鱼说编程
31分钟前
2
0
如何通过 J2Cache 实现分布式 session 存储

做 Java Web 开发的人多数都会需要使用到 session (会话),我们使用 session 来保存一些需要在两个不同的请求之间共享数据。一般 Java 的 Web 容器像 Tomcat、Resin、Jetty 等等,它们会在...

红薯
今天
3
0
C++ std::thread

C++11提供了std::thread类来表示一个多线程对象。 1,首先介绍一下std::this_thread命名空间: (1)std::this_thread::get_id():返回当前线程id (2)std::this_thread::yield():用户接口...

yepanl
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部