二叉排序树的建立和遍历(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 条评论
登录 后参与评论

相关文章

来自专栏日常分享

Java 实现二叉树的构建以及3种遍历方法

大二下学期学习数据结构的时候用C介绍过二叉树,但是当时热衷于java就没有怎么鸟二叉树,但是对二叉树的构建及遍历一直耿耿于怀,今天又遇见这个问题了,所以花了一下...

771
来自专栏尾尾部落

[剑指offer] 平衡二叉树

遍历每个结点,借助一个获取树深度的递归函数,根据该结点的左右子树高度差判断是否平衡,然后递归地对左右子树进行判断。

643
来自专栏WD学习记录

Python数据结构与算法笔记(4)

前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。

772
来自专栏赵俊的Java专栏

用栈实现队列

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

BZOJ 3098: Hash Killer II(新生必做的水题)

3098: Hash Killer II Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge S...

2577
来自专栏青玉伏案

算法与数据结构(十) 二叉排序树的查找、插入与删除(Swift版)

在上一篇博客中,我们主要介绍了四种查找的方法,包括顺序查找、折半查找、插入查找以及Fibonacci查找。上面这几种查找方式都是基于线性表的查找方式,今天博客中...

1867
来自专栏云瓣

前端中常见数据结构小结

数据结构在开发中是一种编程思想的提炼,无关于用何种语言开发或者是哪种端开发。下列将笔者涉猎到的与前端相关的数据结构案例作如下总结:

411
来自专栏desperate633

LintCode 将二叉树拆成链表题目分析代码

将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说,用二叉树的 right 指针,来表示链表中的 next 指针。

533
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

2094
来自专栏郭耀华‘s Blog

LeetCode第二天&第三天

leetcode 第二天 2017年12月27日 4.(118)Pascal's Triangle ? JAVA class Solution { pu...

27212

扫码关注云+社区