文档章节

面试2

尊少
 尊少
发布于 2014/08/18 14:11
字数 545
阅读 4
收藏 0
package com.tree;

import java.util.*;

/**
 * 实现对二叉树的遍历操作
 */
public class TreeOperate<T> {
    public static void main(String args[]) {
        TreeOperate<Integer> treeOperate = new TreeOperate<Integer>();
        TreeNode treeNode2 = treeOperate.addNode(null, 2, true);
        TreeNode treeNode3 = treeOperate.addNode(null, 3, false);

        TreeNode treeNode4 = treeOperate.addNode(treeNode2,4,true);
        treeOperate.addNode(treeNode2,8,false);

        treeOperate.addNode(treeNode3,6,true);
        treeOperate.addNode(treeNode3,12,false);

        treeOperate.addNode(treeNode4,7,true);
        treeOperate.addNode(treeNode4,9,false);
        List<TreeNode> treeNodeList = treeOperate.noInIterator();
        for (TreeNode treeNode : treeNodeList)
            System.out.print(treeNode + ",");
    }

    static class TreeNode {
        TreeNode parent;
        TreeNode left;
        TreeNode right;
        Object data;

        public TreeNode() {
        }

        public TreeNode(Object data) {
            this.data = data;
        }

        public TreeNode(TreeNode parent, TreeNode left, TreeNode right, Object data) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.data = data;
        }

        @Override
        public String toString() {
            return "" +
                    "data=" + data
                    ;
        }
    }

    public TreeOperate() {
        root = new TreeNode();
    }

    //为指定节点添加子节点
    public TreeNode addNode(TreeNode parent, T data, boolean isLeft) {
        if (parent == null)
            parent = root;
        TreeNode treeNode = new TreeNode(data);
        if (isLeft)
            parent.left = treeNode;
        else
            parent.right = treeNode;
        treeNode.parent = parent;
        return treeNode;
    }

    /**
     * ****************   非递归遍历*******************************
     */
    //非递归先序遍历
    public List<TreeNode> noPreIterator() {
        List<TreeNode> list = new ArrayList<TreeNode>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        stack.push(node);
        while (node!=null&&!stack.isEmpty())
        {
            TreeNode t = stack.pop();
            list.add(t);
            if (t.right!=null)
                stack.push(t.right);
            if (t.left!=null)
                stack.push(t.left);

        }
        return list;
    }

    //非递归中序遍历
    public List<TreeNode> noInIterator()
    {
        List<TreeNode> list = new ArrayList<TreeNode>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = root;

        while (treeNode!=null || !stack.isEmpty())
        {
            while (treeNode !=null)
            {
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            if (!stack.isEmpty())
            {
                treeNode = stack.pop();
                list.add(treeNode);
                treeNode = treeNode.right;
            }
        }
        return list;
    }
    // 非递归后序遍历
    public List<TreeNode> noPostIterator() {
        List<TreeNode> list = new ArrayList<TreeNode>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        TreeNode pre = root;
        while (node!=null||!stack.isEmpty())
        {

            //把左节点全部进行压栈
            while (node!=null)
            {
                stack.push(node);
                node = node.left;
            }
            if (stack.size()>0)
            {
                TreeNode temp = stack.peek().right;
                if (temp==null || temp==pre)
                {
                    node = stack.pop();
                    list.add(node);
                    pre = node;
                    node=null;
                }else
                {
                    node   = temp;
                }

            }

        }
        return list;
    }

    /**
     * ****************   递归遍历*******************************
     */
    private TreeNode root;

    //递归后序遍历
    public List<TreeNode> postIterator() {
        return postIterator(root);
    }

    private List<TreeNode> postIterator(TreeNode node) {
        List<TreeNode> list = new ArrayList<TreeNode>();

        //递归访问左子树
        if (node.left != null)
            list.addAll(postIterator(node.left));

        //递归访问右子树
        if (node.right != null)
            list.addAll(postIterator(node.right));
        //访问根节点
        list.add(node);
        return list;
    }

    //递归中序遍历
    public List<TreeNode> inIterator() {
        return inIterator(root);
    }

    private List<TreeNode> inIterator(TreeNode node) {
        List<TreeNode> list = new ArrayList<TreeNode>();

        //递归访问左子树
        if (node.left != null)
            list.addAll(inIterator(node.left));
        //访问根节点
        list.add(node);
        //递归访问右子树
        if (node.right != null)
            list.addAll(inIterator(node.right));
        return list;
    }

    ;

    //递归先序遍历
    public List<TreeNode> preIterator() {
        return preIterator(root);
    }

    private List<TreeNode> preIterator(TreeNode node) {

        List<TreeNode> list = new ArrayList<TreeNode>();
        //先访问根节点
        list.add(node);
        //递归访问左子树
        if (node.left != null)
            list.addAll(preIterator(node.left));
        //递归访问右子树
        if (node.right != null)
            list.addAll(preIterator(node.right));
        return list;
    }

}



© 著作权归作者所有

上一篇: 面试题目整理1
下一篇: 面试题目整理1
尊少
粉丝 1
博文 2
码字总数 1338
作品 0
贵阳
私信 提问
李士芬 2016-5-27工作日报

業務内容 8:00~12:00 1>回访昨天有意向的应聘者2人,1人约定下午面试,1人来公司面试 2>网上筛选5人进行联系,1人约定下午面试,3人约定30日面试,1人拨打 3次不在服务区 13;30:00~17:3...

李士芬
2016/05/27
1
0
李士芬 2016-5-26工作日报

業務内容 8:00~12:00 1>回访昨天有意向的应聘者10人 2>2人嫌远、放弃,2人已找到工作,2人约定下午面试,2人约定明天面试 1人拒绝,1人去外地 3>网上筛选4人进行联系,1人已找到工作,2人约...

李士芬
2016/05/26
1
0
2016-08当当面试总结

前两天去当当面试了,之前在乐视工作的时候,用到了当当的sharding-jdbc框架,那会儿感觉,当当虽然做的不行了,但是技术还是有点,抱着这样的心情,答应了给我推荐职位的猎头,但是面试完感...

小翼Eric
2016/08/17
146
0
如何打动面试官?

专栏 | 九章算法 网址 | www.jiuzhang.com 求职面试是向潜在雇主展示技能和推销自己的绝佳机会。 一次求职面试的时间一般都很简短,通常只有20到30分钟,你需要充分利用这段时间来展现自己。...

九章算法
2017/10/24
0
0
玩转算法面试:(一)什么是算法面试?

前言 对于面试中遇到的大多数问题 都能有一个合理的思考路径 沟通: 边界条件是怎样的? 数据范围如何? 某些术语是具体如何定义的? 基础数据结构 算法设计思想: 递归分治 贪心 动态规划 ...

天涯明月笙
2017/09/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

系列一、入门教程web端实现地图功能

废话不多说,社会我多多 实现步骤如下 第一步、在高德api注册账户 搜索高德api点击进入官网,自己注册一个账号,你懂得怎么注册撒 点击进入下图画框位置,来到官网api入门教程 第二步、按照以...

我叫小糖主
26分钟前
12
0
springboot统一校验validator实现

第一步: pom.xml需引入spring-boot-start-web依赖,其中包含validator框架包 <!--Spring Boot Web依赖--><dependency> <groupId>org.springframework.boot</groupId> <artifact......

zzx10
27分钟前
3
0
vue组件系列-预览、放大、缩小、旋转

这个用的是别人的,如果有问题,估计改起来会很纠结。 安装 npm install v-viewer --save 卸载 npm uninstall v-viewer 注册 在main.js中 // The Vue build version to load with the `impor...

轻轻的走过
29分钟前
3
0
Taro Input输入内容无法绑定state问题

在onInput事件中,返回内容,返回内容即是输入框内容 例如只能输入一个小数点: <Input type='digit' placeholder='带小数点的数字键盘' value={this.state.advance} onInput={ e => this.ch......

步步登高
30分钟前
2
0
Windows10远程连接CentOS7(搭建Xrdp服务器)

Windows10远程连接CentOS7(搭建Xrdp服务器) 听语音 浏览:0 | 更新:2018-02-11 12:56 1 2 3 4 5 6 7 分步阅读 通过VNC或Xdmcp的方式远程连接linux图形桌面,虽然都很方便,但有个缺点就是...

linjin200
30分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部