文档章节

二叉树——BinaryTree 非递归遍历算法(Java)

Jagery
 Jagery
发布于 2016/07/05 22:46
字数 450
阅读 51
收藏 4

1. 结点类BinaryNode

public class BinaryNode<T> {
    public T data;
    public BinaryNode<T> left ,right;

    public BinaryNode(T data, BinaryNode<T> left,BinaryNode<T> right){
        this.data = data;
        this.left = left;
        this.right = right;
    }
    public BinaryNode(T data){
        this(data,null,null);
    }
    public BinaryNode(){this(null,null,null);};

    @Override
    public String toString() {
        return data.toString();
    }
}

2. 二叉树实现类BinaryTree

import java.util.Deque;
import java.util.LinkedList;

/**
 * Created by jagery on 7/5/16.
 */
public class BinaryTree<T> implements BinaryTTree<T> {

    public BinaryNode<T> root;
    public BinaryTree(){this.root = null;}
    //递归前根
    public void preOrder() {

        System.out.print("pre order:");
        preOrder(root);
        System.out.println();
    }
    //非递归前根
    public void preOrderTraverse(BinaryNode<T> p){
        Deque<BinaryNode<T>> stack = new LinkedList<BinaryNode<T>>();
        BinaryNode<T> q = p;
        System.out.print("pre Order Traverse: ");
        while(q!=null || !stack.isEmpty()){
            if(q!=null){
                System.out.print(q.data.toString()+" ");
                if(q.right!=null){
                    stack.push(q.right);
                }
                q = q.left;
            }else{
                q = stack.pop();
            }
        }
        System.out.println();
    }
    private void preOrder(BinaryNode<T> p){
        if(p!=null){
            System.out.print(p.data.toString()+" ");
            preOrder(p.left);
            preOrder(p.right);
        }
    }
    //递归中根
    public void inOrder() {

        System.out.print("in order:");
        inOrder(root);
        System.out.println();
    }
    private void inOrder(BinaryNode<T> p){
        if(p!=null){
            inOrder(p.left);
            System.out.print(p.data.toString()+" ");
            inOrder(p.right);
        }
    }
    //非递归中根
    public void inOrderTraverse(BinaryNode<T> p){
        Deque<BinaryNode<T>> stack = new LinkedList<BinaryNode<T>>();
        BinaryNode<T> q = p;
        System.out.print("in Order Traverse: ");
        while(q!=null || !stack.isEmpty()){
            if(q!=null){
                stack.push(q);
                q = q.left;
            }else{
                q = stack.pop();
                System.out.print(q.data.toString()+" ");
                q = q.right;
            }
        }
        System.out.println();
    }
    //递归后根
    public void postOrder() {

        System.out.print("post order:");
        postOrder(root);
        System.out.println();
    }
    //非递归后根
    public void postOrderTraverse(BinaryNode<T> p) {
        Deque<BinaryNode<T>> stack = new LinkedList<BinaryNode<T>>();
        BinaryNode<T> q = p;
        BinaryNode<T> s = null;
        System.out.print("post Order Traverse: ");
        while(q!=null || !stack.isEmpty()){
            if(q!=null){
                stack.push(q);
                q = q.left;
            }else{
                q = stack.peek();
                if(q.right!=null && q.right!=s ){
                    q = q.right;
                }else{
                    q = stack.pop();
                    System.out.print(q.data.toString()+" ");
                    s = q;
                    q = null;
                }
            }
        }
        System.out.println();
    }
    private void postOrder(BinaryNode<T> p){
        if(p!=null){
            postOrder(p.left);
            postOrder(p.right);
            System.out.print(p.data.toString()+" ");
        }
    }
}

3. 测试类

public class BinaryTree_make {
    public static BinaryTree<String> make(){
        BinaryTree<String> bitree = new BinaryTree<String>();
        BinaryNode<String> child_f,child_d,child_b,child_c;
        child_d = new BinaryNode<String>("D",new BinaryNode<String>("J"),new BinaryNode<String>("G"));
        child_b = new BinaryNode<String>("B",child_d,new BinaryNode<String>("K"));
        child_f = new BinaryNode<String>("F",new BinaryNode<String>("H"),null);
        child_c = new BinaryNode<String>("C",new BinaryNode<String>("E"),child_f);
        bitree.root = new BinaryNode<String>("A",child_b,child_c);
        return bitree;
    }
    public static void main(String args[]){
        BinaryTree<String> bitree = make();
        bitree.preOrder();
        bitree.inOrder();
        bitree.postOrder();        

        bitree.inOrderTraverse(bitree.root);
        bitree.preOrderTraverse(bitree.root);
        bitree.postOrderTraverse(bitree.root);

    }
}

 

© 著作权归作者所有

Jagery
粉丝 3
博文 23
码字总数 11583
作品 0
玉林
程序员
私信 提问
最全BAT算法面试100题:阿里、百度、腾讯、京东、美团、今日头条

第一:复杂度估算和排序算法(上) 1) 时间复杂度和空间复杂度 2)认识对数器 3)冒泡排序 4)选择排序 5)插入排序 6)如何分析递归过程的时间复杂度 7)归并排序 8)小和问题 第二:复杂度...

编程SHA
昨天
0
0
Java学习资料-Java常用算法-二叉树算法

二叉树算法的数据结构: 二叉树结点Node实现与c中的区别是,c中采用的是结构体,而java中是用类来实现,而在c++的教材中,类是一种自定义数据结构。 二叉树的leftchild和rightchild在c中是利...

晓阳
2015/01/28
0
0
学习笔记——二叉树相关算法的实现(Java语言版)

二叉树遍历概念和算法 遍历(Traverse):   所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。   从二叉树的递归定义可知,一棵非空的二叉树由根结...

殇灬央
03/14
0
0
【面试必备】手撕代码,你怕不怕?

Part 1.生产者-消费者问题 这绝对是属于重点了,不管是考察对于该重要模型的理解还是考察代码能力,这都是一道很好的考题,所以很有必要的,我们先来回顾一下什么是生产者-消费者问题; 问题...

编程SHA
01/10
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
2018/09/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Feign Retryer的默认重试策略测试

1、Feign配置 @Configurationpublic class FeignConfig { @Value("${coupon_service.url:http://localhost:8081}") private String couponServiceUrl; @Bean publ......

moon888
14分钟前
1
0
关于不同域名下的session共享问题

如果登录,首页,分类,列表,产品都在不同的二级域名下,主域名不变,一定要保证里面的版本问题,不能为了更新而更新,这样哪个下面的session都访问不了。

dragon_tech
16分钟前
1
0
iOS 中文拼音互转(好东西记录一下)

PinYin4Objc

_____1____
24分钟前
1
0
fabric private data实战

Hyperledger Fabric private data是1.2版本引入的新特性,fabric private data是利用旁支数据库(SideDB)来保存若干个通道成员之间的私有数据,从而在通道之上又提供了一层更灵活的数据保护...

汇智网教程
24分钟前
1
0
es之聚合查询汇总

记录一下最近用到的es聚合查询,感觉常见的应该多遇上了,下午抽空更新

我真是小菜鸡
25分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部