前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二叉排序树的建立和遍历(java)

二叉排序树的建立和遍历(java)

作者头像
GavinZhou
发布2018-01-02 16:33:18
1.6K0
发布2018-01-02 16:33:18
举报
文章被收录于专栏:机器学习实践二三事

也是个经典的面试题,要求建立二叉排序树同时实现树的遍历,其实不难,直接上代码吧

树节点定义:

代码语言:javascript
复制
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(){

    }

    TreeNode(int value){
        this.val = value;
        this.left = null;
        this.right = null;
    }

    TreeNode(int value, TreeNode left, TreeNode right){
        this.val = value;
        this.left = left;
        this.right = right;
    }
}

建立二叉排序树

代码语言:javascript
复制
public static TreeNode buildBST(int[] data){
        //建立二叉排序树
        //假设data中的数字是互不相同的
        TreeNode root = new TreeNode(data[0]);
        for(int i = 1; i < data.length; i++){
            insert(root, data[i]);
        }

        return root;
    }

    private static TreeNode insert(TreeNode root, int value) {
        //二叉排序树插入节点
        if(root == null){
            root = new TreeNode(value);
        }else{
            if(value <= root.val){
                //插入到左子树
                root.left = insert(root.left, value);
            }else{
                //插入到右子树
                root.right = insert(root.right, value);
            }
        }

        return root;
    }

遍历验证下: 更多的树的遍历方法,参考二叉树的多种遍历方法

代码语言:javascript
复制
public static void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        if(root.left != null){
            preOrder(root.left);
        }
        if(root.right != null){
            preOrder(root.right);
        }
    }

main函数:

代码语言:javascript
复制
public static void main(String[] args) {
        int[] data = {3,1,2,5,0,7,9,8};
        TreeNode root = Main.buildBST(data);
        Main.preOrder(root);
    }

当然这样生成的二叉树不是高度最小的二叉树,不过对于面试到这基本也就可以了

这篇博客说了如何建立高度最小的二叉排序树,大家参考下

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-04-17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
数据库
云数据库为企业提供了完善的关系型数据库、非关系型数据库、分析型数据库和数据库生态工具。您可以通过产品选择和组合搭建,轻松实现高可靠、高可用性、高性能等数据库需求。云数据库服务也可大幅减少您的运维工作量,更专注于业务发展,让企业一站式享受数据上云及分布式架构的技术红利!
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档