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

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

树节点定义:

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;
    }
}

建立二叉排序树

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;
    }

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

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函数:

public static void main(String[] args) {
        int[] data = {3,1,2,5,0,7,9,8};
        TreeNode root = Main.buildBST(data);
        Main.preOrder(root);
    }

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CNN

Tensorflow MobileNet移植到Android

在柯林斯原始网络中使用函数tf.nn.top_k电子杂志概率最大的3类,函数将tf.nn.top_k作为网络中的一个计算节点。

2765
来自专栏Java帮帮-微信公众号-技术文章全总结

数据结构基础(2) --顺序查找 ; 二分查找

顺序查找 适用范围: 没有进行排序的数据序列 缺点: 速度非常慢, 效率为O(N) //实现 template <typename Type> Ty...

3226
来自专栏郭耀华‘s Blog

剑指offer 第十二天

58.对称的二叉树 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。 /* public clas...

2885
来自专栏尾尾部落

[剑指offer] 二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

671
来自专栏Java技术栈

二叉树实战 22 题,速度收藏吧!

深刻的理解这些题的解法思路,在面试中的二叉树题目就应该没有什么问题,甚至可以怒他,哈哈。

623
来自专栏desperate633

LintCode 二叉树的层次遍历 II题目代码

给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)

804
来自专栏Java爬坑系列

【Java入门提高篇】Day25 史上最详细的HashMap红黑树解析

  当当当当当当当,好久不见,最近又是换工作,又是换房子,忙的不可开交,断更了一小段时间,最重要的一篇迟迟出不来,每次都犹抱琵琶半遮面,想要把它用通俗易懂的方式...

1024
来自专栏杂七杂八

Pandas数据分析包

Pandas是面板数据(Panel Data)的简写。它是Python最强大的数据分析和探索工具,因金融数据分析工具而开发,支持类似SQL的数据增删改查,支持...

3546
来自专栏小樱的经验随笔

CodeM美团点评编程大赛初赛B轮 黑白树【DFS深搜+暴力】

[编程题] 黑白树 时间限制:1秒 空间限制:32768K 一棵n个点的有根树,1号点为根,相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个...

2333
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第5章 pandas入门5.1 pandas的数据结构介绍5.2 基本功能5.3 汇总和计算描述统计5.4 总结

pandas是本书后续内容的首选库。它含有使数据清洗和分析工作变得更快更简单的数据结构和操作工具。pandas经常和其它工具一同使用,如数值计算工具NumPy和...

4247

扫码关注云+社区